Reversiblity of a storage process in discrete-time withcontinuous componentsŌSAWA, Hideo

Abstract
We consider a simple storage process in discrete-time with the continuous components. The
process is described by the equation Xn+1 = Xn+An−Bn+1 where Xn is the system state at time n, Anand Bn+1 the infow from outside at the start of n-th time slot and the outflow at the end of n-th timeslot, respectively.
We assume that An is independent of any other element in the system, and Bn+1 depends only on
the system state at the start of n-th time slot, Xn+An. Such a storage process is applied to discretetime queue, fluid queues and so on. For a stationary process of the above system, we investigate thereversibility in time.
Keywords: Quasi-reversibility, discrete-time storage model, time-reversed process.
Ⅰ

Introduction

In this paper, we consider a discrete-time storage process with the continuous components. The
model is composed of two kinds of flows, inflow and outflow. At the start of each time slot, thesystem has the inflow from outside. The amount of inflow is independent of any other element in thesystem. On the other hand, at the end of time slot there is the outflow whose size depends only on
the system state, the system state at that time plus the inflow just after the time slot.
For queues and queueing networks, such models with discrete states were considered by severalauthors. Walrand（1983）and Ōsawa（1989）studied discrete-time queues with Poisson arrivals andnegative binomial arrivals, respectively. They showed their models have quasi-reversibility. Ōsawa（1994）showed that these results hold for queues with the general arrivals. Further, he determined
the form of the departure rule under the system has the quasi-reversibility. These results weregeneralized by Miyazawa（1994）,（1995）. Time-reversibility and quasi-reversibility have been dealt− 19 −RESEARCH BULLETIN

No.80

with precisely in Kelly（1979）and Walrand（1988）.
In this paper, we consider the model with the continuous state space. The mathematical model isintroduced in section 2, precisely. We define three processes for the system state. In section 3, wedeal with the relationship among three processes for the system state. We study the time-reversed
properties of the process.
ⅡThe model

Consider a discrete-time storage model with two kinds of flows, inflow and outflow. Let An be theamount of inflow just after time n and Bn+1 be the amount of outflow at the end of n th time slot.
Then the system state Xn at time n is defined byXn+1 = Xn + An − Bn+1,n ∈ Z,

where Z is the set of all integers.
Assume that An ; n ∈ Z are independent and identical random variables which are independentof any other elements, and moreover,P［An ≤ y|Xi , Bi ,（i ≤ n）,Aj ,（j < n）］= A（y）.
We also assume that Bn+1 depends only on Xn + An, that is,P［Bn+1 ≤ y|Xi, Ai, Bi,（i ≤ n）］= P［Bn+1 ≤ y|Xn + An］.
The outflows from the system are determined by conditional distribution functions
P［Bn+1 ≤ y|Xn + An = x］= B（x, y）,
for x, y ≥ 0 and n = 0, 1,…. For these distributions, we make assumptions that A（x）and B（x, y）are
absolutely continuous on R+ with probability density functions（p. d. f.）（a y）and （b x, y）for each x ≥ 0,that is,∞0（ ） = 1,∞0（ , ） = 1.

Under the above conditions, we consider three stochastic processes:
χ = （Bn, Xn, An）: n ∈ Z ,χA = （Xn, An）: n ∈ Z ,χB = （Xn, Bn）: n ∈ Z .
It is clear that these are homogeneous Markov chains. Throughout the paper, these processes are instationary. In the rest of this paper, we focus on reversibility and relations among these processes.

− 20 −

Reversiblity of a storage process in discrete-time with continuous components（ŌSAWA）

Ⅲ

Reversed properties for processes

In this section, we investigate relations for three processes defined in the previous section. In
particular, we are interested in time-reversed properties. For our purpose, assume that the outflow iscontrolled by（x, y）= （bc x）α（x−y）
β（y）,x, y > 0,
where α（x）,β（x）and （c x）are continuous and integrable functions on R+ satisfying that
（ ）
=0α
（ − ）
β（）

−1

= α ＊β（ ）−1 .

3.1. Process χLet R+ be the set of all real numbers that are positive, then the process χ is a Markov chain withthe state space R3+ . For two states x =（u, x, s）and y =（v, y, t）∈R3+ , its transition probability
density is given by（x, y）= bp（x + s, v）（t）1（x,ay）Qα=（c x + s）
（x + s−v）β（v）a（t）1（x,y）
Q
where 1（x,y）is an indicator function for a set Q =（x, y）: x + s = y + v ;Q
1（ , ）=1, （ , ）∈ ,0, otherwise .

We now get the following theorem on the stationary distribution for the process χ.
Theorem 1.
Assume that β（y）= κa（y）for any positive constantκ, then following statements hold.
（1）The process χ has a stationary distribution given by the probability density functionαν（x）= Ca（u）（x）（s）, x =（u, x, s）∈R3+ ,awhere C is the normalizing constant.
（2）The process χ− = （An, Xn, Bn）: n ∈ Z is reversed in time for χ.
Proof （1）By direct calculation, we get− 21 −RESEARCH BULLETIN

3+ν
（ ）
（ , ）

==No.80

（ ）
（ ）
（）
（ + ）
（ + − ）
κ（ ）（ ）1（ , ）
αα

3+∞
0（ ）

=ν
（ ）

（ + ）

+0α（ ）
κ（ +− ）α（ ）（）（）

for any y ∈ R3+ . This means the stationary distribution for the process χ is given by
ν（x）: x ∈R3+ .
（2）For two processes χ and χ− , denote system states at time n by Xn =（Bn, Xn, An）and X−n =（An, Xn, Bn）respectively. Moreover, define a state x− =（s, x, u）for x =（u, x, s）,we then haveαα（x + s−v）κa（v）a（t）
ν（x）（x, y）= Cap（u）（x）（s）
a（c x + s）
1（x,y）Qαα（y + v−x）κa（s）a（u）1（x,= Ca（v）（y）（t）
a（c y + v）y）
Q=ν（y−）（y−, x−）pfor x =（u, x, s）and y =（v, y, t）∈ R3+. This means that the joint events（Xn, Xn+1）and（X−n+1, X−n）
have the same probabilistic law. Thus the second statement of Theorem holds.
RemarkThe property shown in（2）of Theorem 1 is known as quasi-reversibility.
3.2. ProcessesχA andχB
By virtue of Theorem 1, we can have the relations between processesχA andχB.
The process χA is a Markov chain with transition probabilities given byp（x,y）= b（x + s, x + s−y）a（t）,x =（x, s）,y =（y, t）∈ R2+.
AIn the same way, the process χB is a Markov chain with transition probabilities given byp（x,y）= a（y + v − x）
（y + v, v）,x =（x, u）,y =（y, v）∈ R2+.
b
B
Theorem 2.
Under the same condition of Theorem 1, processes χA and χB are time-reversed each other.
Proof

From Theorem 1, χA and χB have the same stationary distribution given by

π（x）= Cα（x）（s）for x =（x, s）
a. We now haveπ（x）p（x,y）= Cα（x）（s）a（c x + s）α（y）κa（x + s − y）a（t）
A= Cα（y）（t）
a（x + s − y）
a（c x + s）α（x）κa（s）=π（y）
p（y,x）
B− 22 −

Reversiblity of a storage process in discrete-time with continuous components（ŌSAWA）

for x =（x, s）and y =（y, t）∈ R2+. Thus this theorem has been proved.
3.3. Process for the system stateConsider the process Xn : n ∈ Z that describes the system state. This process is a Markov chain
with transition probabilities given by∞−（ , ）=∞
0（ + ,+ − ）（）,> ,（ + ,+ − ）
（）,

≤ ,

for x, y ∈ R+. Then we obtain the following theorem.
Theorem 3.
Under the same condition of Theorem 1, the process Xn is time-reversible.
Proof

From Theorem 1, the process Xn has the stationary distribution given by π（x）= Cα（x）

for x ∈ R+ . For y > x, we then haveπ（ ）（ , ）=α（ ）

=α（ ）

0∞
−∞

（ + ）
α（）
κ（ + − ）
（）
（ + ）
α（ ）
κ（ + − ）（）= π（ ）（ , ）for y > x > 0. This means that Xn is time-reversible.
ⅣAn example for queues

Consider the GI/G/1 queueing storage model in discrete-time. At time n, a customer arrives at thesystem and he/she needs the service time An whose size has a p.d.f. （x）
f . Let Bn+1 be the amount ofwork in the system during times n and n + 1 and suppose that Bn+1 has a p.d.f. b（x, y）under thecondition that the total work road is x at the beginning of n-th time slot. Then the system state Xn isdefined by
Xn+1 = Xn + An−Bn+1, n ∈ Z.
If b（x, y） = （c x）α（x−y）（y）
f, then the process

Xn : n ∈ Z

is time-reversible. From quasi-reversibility in Theorem 1, the inflow process An and the outflow process Bn are independent
each other and have the same probabilistic movements.
− 23 −RESEARCH BULLETIN

No.80

For example, in the case of （x）
f=μe−μx, i.e., M/G/1 storage model, the system has quasireversibility for any function α（x）
. This means that we can select the outflow rule to control thesystem state.
References
Kelly, F. P.（1979）Reversibility and Stochastic Networks, Wiley.
Miyazawa, M. （1994） On the characterization of departure rules for discrete time queueing networks with batch
movements and its applications, QUESTA, 18, 149-166.
Miyazawa, M.（1995）A note on my paper: On the characterization of departure rules for discrete time queueing
networks with batch movements and its applications, QUESTA, 19, 445-448.
Ōsawa, H. （1989） Discrete-time storage models with negative binomial inflow, Journal of the Operations ResearchSociety of Japan, 32, 218-232.
Ōsawa, H.（1995）Quasi-reversibility of a discrete-time queue and related models, QUESTA, 18, 133-148.
Walrand, J.（1983）A discrete-time queueing network, Journal of Applied probability, 20, 903-909.
Walrand, J.（1988）An Introduction to Queueing Networks, Prentice Hall.

− 24 −