Reversibility of Markov chains with applications tostorage models―

Hideo Osawa
abstract
This paper documents some results on reversibility of Markov chains and their applications to―queueing and storage models according to the Osawaʼs papers. His research on reversibility started
from the 1980ʼs and has been continued to the present. At first, reversibility conditions for Markovchains with general state space were proposed and they were applied to variable Markov models, forexample, queueing processes, queueing networks, Markov storage models and so on. Many results
have been obtained about these problems, some of them are reviewed in this paper.
Keywords : reversibility, time-reversibility, Markov chain, Markov increment process, quasireversibility, queue, queueing network, storage model.

1. Introduction
This paper reviews some results on reversibility of Markov chains and itʼs applications to―

storage processes according to the Osawaʼs papers. He has studied this theme since 1985.
―First, Osawa ([2], [5], [6]) investigated reversibility of Markov chains with general state spaceand obtained the necessary and sufficient conditions that the Markov chain is reversible. Using these―

results, reversibility of queueing processes was studied by Osawa ([2], [3], [6], [12], [13]). Moreover，―

Osawa made research on reversibility of autoregressive processes ([4], [15]), Markov increment
processes ([16], [18]) and Markovian storage models ([5], [6], [14]).
In 1970ʼs, Kelly took the leader in developing applications to the wide range of models in
operations research, particularly queues and queueing networks, see [1]. He also proposed quasireversibility as the property that brings the product-form solution for queueing networks in the―same way as reversibility. Osawa studied quasi-reversibility for storage processes in discrete-time ([7],[8], [9], [10], [11], [14], [17], [19]). The results obtained in the above papers are collected in this paper.

−1−

RESEARCH BULLETIN

No.86

2. Reversibility
We consider a Markov chain X  { X n , n  Z} with the state space S where Z is the set of allintegers. In this paper, "Markov chain" means "Markov process in discrete-time". Let ( S , F , P) be aprobability space and assume that X has transition probabilities P(x, A), i.e.,		P ( x , A)  P[ X n 1  A | X n  x ], for x  S and A  F .

In this section, we describe the conditions under that a Markov chain X is reversible in―accordance with Osawa ([2], [6]).
2.1 Definition
If there exists a measure  satisfying that		ò  ( dx ) P ( x, B ) = ò  ( dx ) P ( x, A), for any A, B Î F ,(Rev1)

AB

then a Markov chain X is said to be reversible and  is called a reversible measure.
Remark 2.1 Consider the Markov chain X on the real line R with transition densitiesp( x , y ), x , y Î R,i.e., P ( x , A) = ò p( x , y )dy.		

AThen (Rev 1) is rewritten as		p( x ) p( x , y ) = p( y ) p( y, x ), for any x , y Î R,

where p(×) is a measurable function on R.
Remark 2.2 Consider the Markov chain X on Z with transition probabilitiesp( i, j ), i, j Î Z , i.e., P ( x , A) = å p( i, j ).		
jÎ AThen (Rev 1) is rewritten as		pi p( i, j ) = p j p( j , i ), for any i, j Î Z ,where { pi } is a measurable function on Z.
In this section, we describe the conditions under that a Markov chain X is reversible―

inaccordance with Osawa ([2], [6]). Let B( S ) be the set of real-valued F-measurable bounded functions
defined on S, then the following notations are used:		   f = òS ( dx ) f ( x ),		Pf ( x ) = ò P ( x , dy ) f ( y ),S

for any measurable functions f (×) on S.
―Lemma 2.1 (Osawa [2], [6]) We have followings.
(1) (Rev1) is equivalent to		 ( f1 Pf2 ) =  ( f2 Pf1 ), for any f1 , f2 Î B( S ).

(2) For a reversible Markov chain, the reversible measure  is invariant, i.e.,−2−―

Reversibility of Markov chains with applications to storage models（Osawa）

ò  ( dx ) P ( x, A) =  ( A), for any A Î F .		

S

2.2 Time-reversibility
For a stochastic process {Yn , n Î Z} , if the time-reversed process {Y-n , n Î Z} has the sameprobabilistic law, that is,		(Yn1 ,Yn2 ,,Ynk ) = (Ym-n1 ,Ym-n2 ,,Ym-nk ) with probability 1,for any integers m, n1 < n2 <  < nk , then {Yn } is said to be time-reversible. lt is clear that the timereversible process is stationary (see Kelly [1]). We have a following theorem on time-reversibility ofMarkov chains X.
―Theorem 2.2(Osawa [2], [6]) A stationary Markov chain X is time-reversible if and only if X isreversible with the bounded measure  . And then the probability measure ( A) =		 ( A) (S)is the stationary distribution of X.
2.3 Markov chains with atoms
Let  be a state such that		P ( x ,{ }) > 0, for some x Î S ,then  is said to be an atom. ln this section, we describe reversibility of Markov chains with atoms.
―Theorem 2.3 (Osawa [2], [6]) Suppose that a Markov chain X has an atom such as
P ( x , { }) > 0, for any x Î S º S - { }.		

Then X is reversible if and only if the transition probability P satisfies
P ( f1 P ( f2 P1 )( ) = P ( f2 P ( f1 P1 )( ),(Rev2)

for any f1 , f2 Î B( S ) where 1 is the indicator of { } .
In the above theorem, a reversible measure is given by  ( dx ) =		P ( , dx ), x Î S.
P ( x ,{ })Thus if   is bounded, X is time-reversible.
Remark 2.3

If the Markov chain X in Remark 2.1 has an atom  in Theorem 2.3, then (Rev 2) isrewritten as		p( , x ) p( x , y ) P ( y,{ }) = p( , y ) p( y, x ) P ( x ,{ }), x , y Î S .

We now consider the Markov chain with several atoms. Let  i be the atoms and denote theset of all atoms by  , that is,−3−

RESEARCH BULLETIN		

No.86

 = { 1 , 2 ,, m }.
―Theorem 2.4(Osawa [2], [6]) Suppose that a Markov chain X has the set of atoms as above and thetransition probability P satisfying
P ( x ,{ i }) > 0, x Î S - { i } , i = 1,2,, m.		

Then X is reversible if and only if there exists constants ci > 0 such that		ci P ( f1 P ( f2 P1 j )( i ) = c j P ( f2 P ( f1 P1 i )( j ),for any i, j = 1, 2,  , m, and f1 , f2 Î B( S ) .
Remark 2.4

Consider the Markov chain X in Remark 2.2 having a state such that p( i, ) > 0 for

any i Î Z . Then X is reversible under the condition;		

p( , i ) p( i, j ) p( j , ) = p( , j ) p( j , i ) p( i, ), i, j Î Z .

3 Markov increment processes
Let {U n , n Î Z} be a sequence of independent identically distributed (i.i.d.) random variables.
Consider a stochastic process { X n , n Î Z} defined by		

X n+1 = g( X n + U n ), n Î Z ,where g( x ) is a measurable function on the measurable space ( S , F ) . Clearly, the process { X n } is a
Markov chain and said to be a Markov increment process (MIP).
3.1 MIP on the real line
Suppose that the state space is the real line, S = R , or itʼs subset and {U n } has a distributionfunction U(x) with a density function u(x). We make following assumptions;●u(x) is continuous at x = 0.

●u(x) is differentiable at x = 0 from the right and the left.

ln this paper, we describe time-reversibility of following processes.
(C1) Markov Additive Process (MAP)*）

Consider the function g( x ) = x , then the process { X n } , defined by

X n+1 = X n + U n , is called the Markov additive process (MAP).
*）

It has transition densities p( x , y ) = u( y - x ), i, j Î R .

(C2) Lindley Process (LP)*）

The Lindley process is a kind of MIP defined by the function		g( x ) = max(0, x ).

−4−

―

Reversibility of Markov chains with applications to storage models（Osawa）*）

The state space is R0 = [0, ¥) and the state 0 is only one atom.

*)

Transition probabilities are given by
p.d. f . p( x , y ) = u( y - x ), x ³ 0, y > 0,P ( x ,{0}) = U (-x ), x ³ 0.		

(C3) Bounded Lindley Process (BLP)*)		Let K be a positive constant and consider the functiong( x ) = min(max(0, x ), K ).

*)The state space is RB = [0, K ] and there are two atoms, 0 and K.

*)

Suppose that u(x)=0 for x > K .

*)Transition probabilities are given by
p.d. f . p( x , y ) = u( y - x ),0£ x £ K,0< y < K,P ( x ,{0}) = U (-x ),0 £ x < K,P ( x ,{K }) = 1 - U ( K - x ), 0 £ x £ K .		

We have followings for reversibility of the above processes.
Theorem 3.1―(1) ( Osawa [2], [6])LP process is reversible if and only if U(x) is the two-sided exponential

distribution given byìïc exp( ax ),x < 0,u( x ) = ïíïcbxxexp(),
³ 0.
ïî		

where a, b > 0 and c =ab. Moreover, if a < b then LP is time-reversible.
a+b―(2) ( Osawa and Doi [16]) BLP process is time-reversible if and only if U(x) is the two-sided
exponential distribution with barriers given byìïc exp( ax ), -K < x < 0,u( x ) = ïíïïîc exp(-bx ), 0 £ x < K ,cU (-K ) = exp(-aK ),ac
U ( K ) = exp(-bK ),b		where a, b > 0 and c =Remark 3.1

ab.
a+bIf u(x) is the symmetric probability density with respect to x = 0, then the MIP process

is reversible but not time-reversible. Thus there are not time-reversible MIP processes.

−5−

RESEARCH BULLETIN

No.86

3.2 MIP with discrete-states
Suppose that the state space is the set of all integers or itʼs subset andfunction

has a probability. ln this section, we describe time-reversibility of following processes.

(D1) Markov Additive Process（*)）

Consider the function, then the process, defined by, is written as DMAP process.
*)

It has transition functions,(D2) Lindley Process（DLP）*)		

The Lindley process is a kind of MIP defined by the functiong( x ) = max(0, x ).

*)The state space is the set of all non-negative integers*)

Transition probabilities are given by.

i Î N 0 , j > 0,ïìïu j-i ,ïïip( i, j ) = íïïU (-i ) = å uk , i Î N 0 , j = 0.
ïïîk=-¥

		(D3) Bounded Lindley Process（DBL）*)		

Let

be a positive integer and consider the functiong( x ) = min(max(0, x ), J ).
*)The state space is*)Suppose that*)

Transition probabilities are given by.
for.

i Î N B , j Î N B - {0},ïìïu j-i ,ïïip( i, j ) = íïïU (-i ) = å uk , i Î N B , j = 0.
ïïîk=- J		Theorem 3.2――(1) (Osawa [2], [6], Osawa and Shima [12]) DLP process is reversible if and only if
is the two-sided geometric distribution given by		ìïap k-1 , k = 1,2,,ïïuk = ïíc,k = 0,
ïï -k-1
ïïbq, k = -1,-2,,
î−6−

―

Reversibility of Markov chains with applications to storage models（Osawa）

where,andsatisfyab+c+= 1 and aq = bp.
1- p
1- q

Moreover, ifthen DLP is time-reversible.

―(2) (Osawa and Zhang [18]) DBLP process is time-reversible if and only if

is thedistribution given byìïap k-1 , k = 1,2,, J - 1,
ïï
uk = ïíc,k = 0,
ïï -k-1
ïïbq, k = -1,-2,, - J + 1,
îb J -1
u- J = U (-J ) =q ,1- q
auJ = U ( J ) =p J -1 ,1- p		

where,

satisfy

ab+c+= 1.
1- p
1- q		
Remark 3.2and―(Osawa and Zhang [18]) In DBLP process, if

Moreover, in the case of

the process is time-reversible.

the process is time-reversible if and only if the following relations

holds;		
Remark 3.3

u1 ( u1 + u2 )u-2 = u2 ( u-1 + u-2 )u-1 .

Ifis the symmetric distribution with respect to, then DMAP process

is reversible but not time-reversible. Thus there are not time-reversible DMAP processes.
4. Reversibility of queueing processes
In this section, we describe reversibility of following queueing processes.
[1] Waiting-time process in the ordinary queue
Consider the single server queue. Let

be the interarrival time between n th andbe the service time of n th customer andth customers. Assume thatis asequence of i.i.d. random variables with the common distribution function. Andis also asequence of i.i.d. random variables with the common distribution function. Let,

then the waiting-time process is formulated by thethe waiting-time process inprocess. Applying Theorem 3.1(1) yields thatis reversible if and only if both−7−andare exponential

RESEARCH BULLETIN

No.86―distributions, that is,(Osawa [2], [6]).

[2] Waiting-time process in the discrete-time queue
Consider the discrete-time queue
customer has a distribution
customers. Assume that the service time
, and the interarrival time between n th andhas a distribution

is described by. By letting, that is,th, the waiting-time process. And we have the following.

For the waiting-time process in the discrete-time
for theof n thqueues, the reversible one is only―

andare geometric distributions (Osawa [12], [13]).

[3] Quasi-reversibility
In the above systems, we can see the property that the departure process is the sameprobability law as the arrival process. This is called the quasi-reversibility. This property has theessential role that the system has the product-form solution in queueing networks with timereversible nodes.
5. Quasi-reversibility
In the above sections, we found that there are few systems having time-reversibility. However,―

it is known that there are many systems having quasi-reversibility (Osawa [6], [7], [8], [10], [17], [19]).
Consider the discrete-time storage model with discrete states as follows. Let
number of arriving items just after time n, andth slot. Then the system states		

be the number of departures at the end of n, the number of items at n th time epoch, is defined by

X n+1 = X n + An - Dn+1

Suppose that

depends only on the system state just after n th time epoch, i.e.,,P[ Dn+1 = j | X m , Am , Dm , m £ n]		= P[ Dn+1 = j | X n + An = i]
= D( i, j ), 0 £ j £ i, i ³ 0.

Consider the departure rule		whereD( i, j ) = c( i )r ( i - j ) ( j ), 0 £ j £ i, i ³ 0,

are non-negative real-valued functions and-1		

be theïì iïüc( i ) = ïíå r ( i - j ) ( j )ïý , i ³ 0.
ïï j = 0
ïï
îþ

−8−

is determined by―

Reversibility of Markov chains with applications to storage models（Osawa）

Further, we assume thatforand. This departure rule is called

D-rule. Then we have the following.
―Theorem 5.1   (Osawa [9], [19]) The discrete-time storage model with D-rule has the●the past of the departure process

is independent of the present state●the future of the arrival process

is independent of the present state●the departureand the arrival,,

have the same distribution.

The system having the properties in Theorem 5.1 is said to be quasi-reversible, see Kelly [1].
Moreover, we have the following.
―Theorem 5.2 (Osawa [9], [19]) The discrete-time storage model has quasi-reversibility if and only if thedeparture rule is D-rule.
6. Comments
This paper reviewed some results on reversibility of Markov chains with applications toMarkov models, queues, queueing networks, storage models, and so on. Further, some new results
are introduced and these works are in preparation. The research on this theme has been continuing.
References[1] Kelly, F. P. (1979), Wiley.
―,[2] Osawa, H. (1985) Reversibility of Markov chains with applications to storage models,
22, No. 1, 123-137.
―[3] Osawa, H. (1985) 待ち行列過程の時間的可逆性について，「京都大学数理解析研究所講究録」，564, 222-235, (inJapanese).
―, 28,[4] Osawa, H. (1988) Reversibility of ﬁrst-order autoregressive processes,
No. 1, 61-69.
―[5] Osawa, H. (1988) Reversibility of Markovian storage models,「情報ネットワークのトラフィック評価に関する基礎的研究」, 40-46.
―, Doctoral Thesis, Tokyo Institute of Technology.
[6] Osawa, H. (1989)―[7] Osawa, H. (1989) Discrete-time storage models with negative binomial inﬂow,, 32, No. 2, 218-232.
―[8] Osawa, H. (1988) Quasi-reversibility of a discrete-time storage model,「情報・通信ネットワークに関する性能評価モデルの総合的研究」, 243-251.
―, 18, No. 2, 133[9] Osawa, H. (1994) Quasi-reversibility of a discrete-time queue and related models,148.
―[10] Osawa, H. (1995) On a discrete-time storage model with quasi-reversibility,「情報・通信ネットワークに関する性能評価モデルの総合的研究」, 135-144．
―[11] Osawa, H. (1996) On a discrete-time storage process with general state space,「情報・通信ネットワークに関する性能評価モデルの総合的研究」, 103-113.
―[12] Osawa, H. and Shima, C. (1999) Reversibility of Lindley processes with discrete states,−9−RESEARCH BULLETIN

No.86, 44, 1-8.
―
[13] Osawa, H. and Shima, C. (2005) Time-reversibility of stationary Markov chains and queueing processes,, 5, No. 1, 239-249.
―[14] Osawa, H. (2010) Time reversibility of a storage model, Research Bulletin, Liberal Arts, Nihon University College ofEconomics, 63, 59-63.
―[15] Osawa, H. (2013) Reversibility of some autoregressive processes,, 73, 39-47.
―[16] Osawa, H. and Doi, M. (2014) Reversibility of a Markov increment process on the real line,, 79-86.
―[17] Osawa, H. (2016) Reversibility of a storage process in discrete-time with continuous components,, 80, 19-24.
―.
[18] Osawa, H. and Zhang, X. (2018) Reversibility of Markov increment process with ﬁnite states,―.
[19] Osawa, H. (2018) On discrete-time storage models with batch movement,− 10 −