# On the Study of Transience and Recurrence of the Markov Chain Defined by Directed Weighted Circuits Associated with a Random Walk in Fixed Environment

Authors: Chrysoula Ganatsiou
Journal: Journal of Probability and Statistics
 (2013)

---

## Abstract

By using the cycle representation theory of Markov processes, we investigate proper criterions regarding transience and recurrence of the corresponding Markov chain represented uniquely by directed cycles (especially by directed circuits) and weights of a random walk with jumps in a fixed environment.


---

## Body

## 1. Introduction

A systematic research has been developed (Kalpazidou [1], MacQueen [2], Minping and Min [3], Zemanian [4], and others) in order to investigate representations of the finite-dimensional distributions of Markov processes (with discrete or continuous parameter) having an invariant measure, as decompositions in terms of the cycle (or circuit) passage functions:
(1)Jc^(i,j)=1,ifi,jareconsecutivestatesofc^,=0,otherwise,
for any directed sequence c^=(i1,i2,…,ir) (or c=(i1,i2,…,ir,i1)) of states called a cycle (or a circuit), r>1, of the corresponding Markov process. The representations are called cycle (or circuit) representationswhile the corresponding discrete parameter Markov processes generated by directed circuits c=(i1,i2,…,ir,i1), r>1, are called circuit chains.Following the context of the theory of Markov processes’ cycle-circuit representation, the present work arises as an attempt to investigate proper criterions regarding the properties of transience and recurrence of the corresponding Markov chain represented uniquely by directed cycles (especially by directed circuits) and weights of a random walk with jumps (having one elastic left barrier) in a fixed ergodic environment (Kalpazidou [1], Derriennic [5]).The paper is organized as follows. In Section2, we give a brief account of certain concepts of cycle representation theory of Markov processes that we will need throughout the paper. In Section 3, we present some auxiliary results in order to make the presentation of the paper more comprehensible. In particular, in Section 3, a random walk with jumps (having one elastic left barrier) in a fixed ergodic environment is considered, and the unique representations by directed cycles (especially by directed circuits) and weights of the corresponding Markov chain are investigated. These representations will give us the possibility to study proper criterions regarding transience and recurrence of the abovementioned Markov chain, as it is described in Section 4.Throughout the paper, we will need the following notations:(2)ℵ={0,1,2,…},ℵ*={1,2,…},Z={…,-1,0,1,…}.


## 2. Preliminaries

Let us consider a denumerable set S. Then the directed sequencec=(i1,i2,…,ir,i1) modulo the cyclic permutations, where i1,i2,…,ir∈S, r>1, completely defines a directed circuit in S. The ordered sequence c^=(i1,i2,…,ir) associated with the given directed c is called a directed cycle in S.A directed circuit may be considered asc=(c(r),c(r+1),…,c(r+v-1),c(r+v)), if there exists an r∈Z, such that i1=c(r+0), i2=c(r+1),…,iv=c(r+v-1), i1=c(r+v), where c is a periodic function from Z to S.The corresponding directed cycle is defined by the ordered sequencec^=(c(r),c(r+1),…,c(r+v-1)). The values c(k) are the points of c, while the directed pairs (c(k),c(k+1)), k∈Z, are the directed edges of c.The smallest integerp≡p(c)≥1 satisfying the equation c(r+p)=c(r), for all r∈Z, is the periodof c. A directed circuit c such that p(c)=1 is called a loop. (In the present work we will use directed circuits with distinct point elements.)Let us also consider a directed circuitc (or a directed cycle c^) with period p(c)>1. Then we may define by
(3)Jc(n)(i,j)=1,ifthereexistsanr∈ZsuchthatJc(n)(i,j)=1,i=c(r),j=c(r+n),=0,otherwise,
the n-step passage function associated with the directed circuit c, for any i,j∈S, n≥1.Furthermore we may define by(4)Jc(i)=1,ifthereexistsanr∈Zsuchthati=c(r),=0,otherwise,
the passage function associated with the directed circuit c, for any i∈S. The above definitions are due to MacQueen [2] and Kalpazidou [1].Given a denumerable setS and an infinite denumerable class C of overlapping directed circuits (or directed cycles) with distinct points (except for the terminals) in S such that all the points of S can be reached from one another following paths of circuit edges; that is, for each two distinct points i and j of S there exists a finite sequence c1,…,ck, k≥1, of circuits (or cycles) of C such that i lies on c1 and j lies on ck, and any pair of consecutive circuits (cn,cn+1) have at least one point in common. Generally we may assume that the class C contains, among its elements, circuits (or cycles) with period greater or equal to 2.With each directed circuit (or directed cycle)c∈C let us associate a strictlypositive weightwc which must be independent of the choice of the representative of c, that is, it must satisfy the consistency condition wcotk=wc, k∈Z, where tk is the translation of length k (that  is, tk(n)≡n+k, n∈Z, for any fixed k∈Z).For a given classC of overlapping directed circuits (or cycles) and for a given sequence (wc)c∈C of weights we may define by
(5)pij=∑c∈Cwc·Jc(1)(i,j)∑c∈Cwc·Jc(i)
the elements of a Markov transition matrix on S, if and only if ∑c∈Cwc·Jc(i)<∞, for any i∈S. This means that a given Markov transition matrix P=(pij), i,j∈S, can be represented by directed circuits (or cycles) and weights if and only if there exists a class of overlapping directed circuits (or cycles) C and a sequence of positive weights (wc)c∈C such that the formula (5) holds. In this case, the Markov transition matrix P has a unique stationary distribution p which is a solution of pP=p and is defined by
(6)p(i)=∑c∈Cwc·Jc(i),i∈S.It is known that the following classes of Markov chains may be represented uniquely by circuits (or cycles) and weights:(i)
the recurrent Markov chains (Minping and Min [3]),(ii)
the reversible Markov chains.


## 3. Auxiliary Results

Let us consider a Markov chain(Xn)n≥0 on ℵ with transitions k→(k+1), k→(k-1), and k→k whose the elements of the corresponding Markov transition matrix are defined by
(7)P(Xn+1=0/Xn=0)=r0,P(Xn+1=1/Xn=0)=p0,p0=1-r0,P(Xn+1=k+1/Xn=k)=pk,k≥1,P(Xn+1=k/Xn=k)=rk,k≥1,P(Xn+1=k-1/Xn=k)=qk,k≥1,
such that pk+qk+rk=1, 0≤pk, rk≤1, for every k≥1, as it is shown in (Figure 1).Figure 1Assume that(pk)k≥0 and (rk)k≥0 are arbitrary fixed sequences with 0≤p0=1-r0≤1, 0≤pk, rk≤1, for every k>1. If we consider the directed circuits ck=(k,k+1,k), ck′=(k,k),k≥0, and the collections of weights (wck)k≥0 and (wck′)k≥0, respectively, then we may obtain that
(8)pk=wckwck-1+wck+wck′,foreveryk≥1,
with
(9)p0=wc0wc0+wc0′.Here the classC(k) contains the directed circuits ck=(k,k+1,k), ck-1=(k-1,k,k-1), and ck′=(k,k). Furthermore we may define
(10)qk=wck-1wck-1+wck+wck′,foreveryk≥1
and rk=wck′/(wck-1+wck+wck′), such that pk+qk+rk=1, for every k≥1,  with r0=1-p0=wc0′/(wc0+wc0′).The transition matrixP=(pij) with
(11)pij=∑k=0∞wck·Jck(1)(i,j)∑k=0∞[wck·Jck(i)+wck′·Jck′(i)],fori≠j,(12)pii=∑k=0∞wc′k·Jck′(1)(i,i)∑k=0∞[wck·Jck(i)+wck′·Jck′(i)],
where Jck(1)(i,j)=1,  if  i, j  are consecutive points of the circuit ck, Jck(i)=1, if   i  is a point of the circuit ck, and Jck′(i)=1, if  i  is a point of the circuit ck′, expresses the representation of the Markov chain (Xn)n≥0 by directed cycles (especially by directed circuits) and weights.Furthermore we consider also the “adjoint” Markov chain (Xn′)n≥0 on ℵ whose elements of the corresponding Markov transition matrix are defined by
(13)P(Xn+1′=0/Xn′=0)=r0′,P(Xn+1′=1/Xn′=0)=q0′,q0′=1-r0′,P(Xn+1′=k-1/Xn′=k)=pk′,k≥1,P(Xn+1′=k/Xn′=k)=rk′,k≥1,P(Xn+1′=k+1/Xn′=k)=qk′,k≥1,
such that pk′+qk′+rk′=1, 0<pk′,qk′,rk′≤1, for every k≥1, as it is shown in (Figure 2).Figure 2Assume that(qk′)k≥0 and (rk′)k≥0 are arbitrary fixed sequences with 0≤q′0=1-r0′≤1, 0≤qk′, rk′≤1, for every k≥1. If we consider the directed circuits ck′′=(k+1,k,k+1), ck′′′=(k,k), k≥0, and the collections of weights (wck′′)k≥0, and (wck′′′)k≥0 respectively, then we may have
(14)qk′=wck′′wck-1′′+wck′′+wck′′′,foreveryk≥1,
with
(15)q0′=wc0′′wc0′′+wc0′′′.Here the classC′(k) contains the directed circuits ck′′=(k+1,k,k+1), ck-1′′=(k,k-1,k), and ck′′′=(k,k). Furthermore we may define
(16)pk′=wck-1′′wck-1′′+wck′′+wck′′′,foreveryk≥1,rk′=wck′′′wck-1′′+wck′′+wck′′′,
such that pk′+qk′+rk′=1, for every k≥1, with
(17)r0′=1-q0′=wc0′′′wc0′′+wc0′′′.So the transition matrixP′=(pij′) with elements equivalent to that given by the above-mentioned formulas (11), (12) expresses also the representation of the “adjoint” Markov chain (Xn′)n≥0 by directed cycles (especially by directed circuits) and weights.Consequently we have the following.Proposition 1.
The Markov chain(Xn)n≥0 defined as above has a unique representation by directed cycles (especially by directed circuits) and weights.Proof.
Let us consider the set of directed circuitsck=(k,k+1,k) and ck′=(k,k), for every k≥0, since only the transitions from k to k+1, k to k-1, and k to k are possible. There are three circuits through each point k≥1, ck-1, ck, and ck′ and two circuits through 0: c0, c0′.
The problem we have to manage is the definition of the weights. We may symbolize bywk the weight wck of the circuit ck and by wk′ the weight wck′ of the circuit ck′, for any k≥0. The sequences (wk)k≥0,  (wk′)k≥0  must be a solution of
(18)pk=wkwk-1+wk+wk′,k≥1withp0=w0w0+w′0,rk=wk′wk-1+wk+wk′,k≥1withr0=w0′w0+w0′,qk=1-pk-rk,k≥1.
Let us take bybk=wk/wk-1, γk=wk′/wk-1′,   k≥1.
As a consequence we may have(19)bk=pkqk=pk1-pk-rk,γk=rkrk-1pk-1pkbk,foreveryk≥1.
Given the sequences(pk)k≥0 and (rk)k≥0, it is clear that the above sequences (bk)k≥1 and (γk)k≥1 exist and are unique. This means that the sequences (wk)k≥0 and (wk′)k≥0 are defined uniquely, up to multiplicative constant factors, by
(20)wk=w0·b1⋯bk,wk′=w0′·γ1⋯γk.
(The unicity is understood up to the constant factorsw0, w0′.)Proposition 2.
The “adjoint” Markov chain(Xn′)n≥0 defined as above has a unique representation by directed cycles (especially by directed circuits) and weights.Proof.
Following an analogous way of that given in the proof of Proposition1 the problem we have also to manage here is the definition of the weights. To this direction we may symbolize by wk′′ the weight wck′′ of the circuit ck′′ and by wk′′′ the weight wck′′′ of the circuit ck′′′, for every k≥0. The sequences (wk′′)k≥0 and  (wk′′′)k≥0 must be solutions of
(21)qk′=wk′′wk-1′′+wk′′+wk′′′,k≥1withq0′=w0′′w0′′+w0′′′,rk′=wk′′′wk-1′′+wk′′+wk′′′,k≥1withr0′=w0′′′w0′′+w0′′′,pk′=1-q′k-r′k,k≥1.
By considering the sequences(sk)k and (tk)k where sk=wk-1′′/wk′′, tk=wk′′′/wk-1′′′, k≥1, we may obtain that
(22)sk=1-qk′-rk′qk′,tk=rk′rk-1′·qk′qk-1′·sk,foreveryk≥1.
For given sequences(qk′)k≥0, (rk′)k≥0 it is obvious that (sk)k≥1, (tk)k≥1 exist and are unique for those sequences, that is, the sequences (wk′′)k≥0, (wk′′′)k≥0 are defined uniquely, up to multiplicative constant factors, by
(23)wk′′=w0′′s1·s2⋯sk,wk′′′=w0′′′·t1,t2⋯tk.
(The unicity is based to the constant factorsw0′′, w0′′′.)


## 4. Recurrence and Transience of the Markov Chains(Xn)n≥0 and (Xn′)n≥0

We have that for the Markov chain(Xn)n≥0, there  is a unique invariant measure up to a multiplicative constant factor μk=wk-1+wk+wk′,   k≥1,μ0=w0+w0′, while for the Markov chain (Xn′)n≥0, μk′=wk-1′′+wk′′+wk′′′, k≥1 with μ0′=w0′′+w0′′′. In the case that an irreducible chain is recurrent there is only one invariant measure (finite or not), so we may obtain the following.Proposition 3.
(i) The Markov chain(Xn)n≥0 defined as above is positive recurrent if and only if
(24)∑k=1∞b1·b2⋯bk<+∞(or1w0·∑k=1∞wk<+∞),∑k=1∞γ1·γ2⋯γκ<+∞(or1w0′·∑k=1∞wk′<+∞).
(ii) The Markov chain(Xn′)n≥0 defined as above is positive recurrent if and only if
(25)∑k=1∞1s1·s2⋯sk<+∞(or1w0′′·∑k=1∞wk′′<+∞),∑k=1∞t1·t2⋯tk=+∞(or1w0′′′·∑k=1∞wk′′′=+∞).In order to obtain recurrence and transience criterions for the Markov chains(Xn)n≥0 and (Xn′)n≥0 we shall need the following proposition (Karlin and Taylor [6]).Proposition 4.
Let us consider a Markov chain onℵ which is irreducible. Then if there exists a strictly increasing function that is harmonic on the complement of a finite interval and that is bounded, then the chain is transient. In the case that there exists such a function which is unbounded then the chain is recurrent.Following this direction, we shall use a well-known method-theorem based on the Foster-Kendall theorem (Karlin and Taylor [6]) by considering the harmonic function g=(gk,k≥1). For the Markov chain (Xn)n≥0 this is a solution of
(26)p0·g1+r0·g0=g0,pk·gk+1+qk·gk-1+rk·gk=gk,k≥1.SinceΔgk=gk-gk-1, for every k≥1, we obtain that
(27)pk·gk+1+qk·gk-qk·gk+qk·gk-1+rk·gk=gk,pk·(Δgk+1+gk)+qk·gk-qk·gk+qk·gk-1+rk·gk=gkpk·Δgk+1+(pk+qk+rk)·gk-qk·gk+qk·gk-1=gkpk·Δgk+1-qk·(gk-gk-1)=0pk·Δgk+1=qk·Δgk.If we putmk=Δgk/Δgk+1, we get mk=pk/qk (with pk=1-qk-rk), k≥1, which is the equation of definition of the sequences (sk)k≥1 and (tk)k≥1 (as a multiplicative factor of the (sk)k≥1) for the Markov chain (Xn′)n≥0 such that qk′=qk, rk′=rk, for every k≥1. This means that the strictly increasing harmonic functions of the Markov chain (Xn)n≥0 are in correspondence with the weight representations of the Markov chain (Xn′)n≥0 such that
(28)qk′=P(Xn+1′=k+1/Xn′=k)=P(Xn+1=k-1/Xn=k)=qk,rk′=P(Xn+1′=k/Xn′=k)=P(Xn+1=k/Xn=k)=rk,pk′=1-qk′-rk′=1-qk-rk=pk,foreveryk≥1.To express this kind of duality we will call the Markov chain(Xn′)n≥0, the adjoint of the Markov chain (Xn)n≥0 and reciprocally in the case that the relation (28) is satisfied.Equivalently for the Markov chain(Xn′)n≥0, the harmonic function g′=(gk′, k≥1)  satisfies the equation
(29)r0′·g0′+q0′·g1′=g0′,qk′·gk+1′+pk′·gk-1′+rk′·gk′=gk′,k≥1.SinceΔgk′=gk′-gk-1′, for every k≥1, we have
(30)qk′·(Δgk+1′+gk′)+pk′·gk′-pk′·gk′+pk′·gk-1′+rk′·gk′=gk′,(pk′+qk′+rk′)·gk′+qk′·Δgk+1′-pk′·gk′+pk′·gk-1′=gk′,qk′·Δgk+1′=pk′·(gk′-gk-1′)=pk′·Δgk′.If we putℓk=Δgk+1′/Δgk′, we get ℓk=pk′/qk′ (with qk′=1-pk′-rk′), k≥1, which is the equation of the definition of the sequences (bk)k≥1 and (γk)k≥1 (as a multiplicative factor of the (bk)k≥1) for the Markov chain (Xn)n≥0 such that pk′=pk, rk′=rk, for every k≥1. By considering a similar approximation of that given before for the Markov chain (Xn)n≥0, we may say that the strictly increasing harmonic functions of the Markov chain (Xn′)n≥0 are in correspondence with the weight representations of the Markov chain (Xn)n≥0 such that equivalent equations of (28) are satisfied.So we may have the following.Proposition 5.
The Markov chain(Xn)n≥0 defined as above is transient if and only if the adjoint Markov chain (Xn′)n≥0 is positive recurrent and reciprocally. Moreover the adjoint Markov chains (Xn)n≥0 and  (Xn′)n≥0  are null recurrent simultaneously.
In particular(i)
the Markov chain(Xn)n≥0defined as above is transient if and only if(1/w0′′)·∑k=1∞wk′′<+∞and(1/w0′′′)·∑k=1∞wk′′′=+∞;(ii)
the Markov chain(Xn′)n≥0defined as above is transient if and only if(1/w0)·∑k=1∞wk<+∞and(1/w0′)·∑k=1∞wk′<+∞;(iii)
the adjoint Markov chains(Xn)n≥0and(Xn′)n≥0are null recurrent if(31)1w0·∑k=1∞wk=1w0′′·∑k=1∞wk′′=+∞,1w0′·∑k=1∞wk′=1w0′′′·∑k=1∞wk′′′=+∞.Proof.
The proof of Proposition5 is an application mainly of Proposition 4 as well as of Proposition 3.



---

*Source: 424601-2013-06-06.xml*