# Some Limit Properties of the Harmonic Mean of Transition Probabilities for Markov Chains in Markovian Environments Indexed by Cayley's Trees

Authors: Huilin Huang
Journal: International Journal of Stochastic Analysis
 (2013)

---

## Abstract

We prove some limit properties of the harmonic mean of a random transition probability for finite Markov chains indexed by a homogeneous tree in a nonhomogeneous Markovian environment with finite state space. In particular, we extend the method to study the tree-indexed processes in deterministic environments to the case of random enviroments.


---

## Body

## 1. Introduction

A treeTis a graph which is connected and doesn't contain any circuits. Given any two verticesα≠β∈T, letαβ¯be the unique path connectingαandβ. Define the graph distanced(α,β)to be the number of edges contained in the pathαβ¯.LetTbe an infinite tree with root0. The set of all vertices with distancenfrom the root is called thenth generation ofT, which is denoted byLn. We denote byT(n)the union of the firstngenerations ofT. For each vertext, there is a unique path from0tot and|t|for the number of edges on this path. We denote the first predecessor oftby 1t. The degree of a vertex is defined to be the number of neighbors of it. If every vertex of the tree has degreed+1, we say it is Cayley’s tree, which is denoted byTC,d. Thus, the root vertex hasd+1neighbors in the first generation and every other vertex hasdneighbors in the next generation. For any two verticess and tof treeT, writes≤tifsis on the unique path from the root0tot. We denote bys∧tthe farthest vertex from0satisfyings∧t≤sands∧t≤t. We use the notationXA={Xt,t∈A}and denote by|A|the number of vertices ofA.In the following, we always letTdenote the Cayley treeTC,d.A tree-indexed Markov chain is the particular case of a Markov random field on a tree. Kemeny et al. [1] and Spitzer [2] introduced two special finite tree-indexed Markov chains with finite transition matrix which is assumed to be positive and reversible to its stationary distribution, and these tree-indexed Markov chains ensure that the cylinder probabilities are independent of the direction we travel along a path. In this paper, we omit such assumption and adopt another version of the definition of tree-indexed Markov chains which is put forward by Benjamini and Peres [3]. Yang and Ye[4] extended it to the case of nonhomogeneous Markov chains indexed by infinite Cayley’s tree and we restate it here as follows.Definition 1 (T-indexed nonhomogeneous Markov chains (see [4])).
LetTbe an infinite Cayley tree, 𝒳a finite state space, and{Xt,t∈T}a stochastic process defined on probability space(Ω,F,P), which takes values in the finite set𝒳. Let
(1)p={p(i),i∈𝒳}
be a distribution on𝒳 and
(2)Pt=(Pt(j∣i)),i,j∈𝒳,
a transition probability matrix on𝒳2. If, for any vertext,
(3)P(Xt=j∣X1t=i,Xs=xsfort∧s≤1t)=P(Xt=j∣X1t=i)=Pt(j∣i),∀i,j∈𝒳,(4)P(X0=i)=p(i)∀i∈𝒳,
then{Xt,t∈T}will be called 𝒳-valued nonhomogeneous Markov chains indexed by infinite Cayley’s tree with initial distribution (1) and transition probability matrices{Pt,t∈T}.The subject of tree-indexed processes has been deeply studied and made abundant achievements. Benjamini and Peres [3] have given the notion of the tree-indexed Markov chains and studied the recurrence and ray-recurrence for them. Berger and Ye [5] have studied the existence of entropy rate for some stationary random fields on a homogeneous tree. Ye and Berger [6, 7], by using Pemantle's result [8] and a combinatorial approach, have studied the Shannon-McMillan theorem with convergence in probability for a PPG-invariant and ergodic random field on a homogeneous tree. Yang and Liu [9] and Yang [10] have studied a strong law of large numbers for Markov chains fields on a homogeneous tree (a particular case of tree-indexed Markov chains and PPG-invariant random fields). Yang and Ye [4] have established the Shannon-McMillan theorem for nonhomogeneous Markov chains on a homogeneous tree. Huang and Yang [11] has studied the strong law of large numbers for finite homogeneous Markov chains indexed by a uniformly bounded infinite tree.The previous results are all about tree-indexed processes in deterministic environments. Recently, we are interested in random fields indexed by trees in random environments. In the rest of this paper we formulate a model of Markov chain indexed by trees in random environment especially in Markovian environment and study some limit properties of the harmonic mean of random transition probability for finite Markov chains indexed by a homogeneous tree in a nonhomogeneous Markovian environment. We are also interested in the strong law of large numbers of Markov chains indexed by trees in random environments which we will prepare for in another paper.Definition 2.
LetTbe an infinite Cayley tree,𝒳andΘtwo finite state spaces. Suppose that{ξt,t∈T}is aΘ-valued random field indexed byT, if, for any vertext∈T,
(5)P(Xt=j∣X1t=i,Xs=xs,fort∧s≤1t;ξr,r∈T)=Pξ1t(i,j),a.s.,(6)P(X0=i∣ξr,r∈T)=P(i∣ξ0)∀i∈𝒳
for eachi,j∈𝒳, where Px=(Px(i,j))i,j∈𝒳, x∈Θis a family of stochastic matrices. Then we call{Xt,t∈T}a Markov chain indexed by treeTin a random environment{ξt,t∈T}. Theξt′sare called the environmental process or control process indexed by tree T. Moreover, if{ξt,t∈T}is a T-indexed Markov chain with initial distributionμ={μ(θ),θ∈Θ}and one-step transition probability matricesKt={Kt(α,β),α,β∈Θ,t∈T}, we call{Xt,t∈T}a Markov chain indexed by treeTin a nonhomogeneous Markovian environment.Remark 3.
If every vertex has degree two, then our model of Markov chain indexed by homogeneous tree with Markovian environments is reduced to the model of Markov chain in Markovian environments which was introduced by Cogburn [12] in spirit.Remark 4.
We also point out that our model is different from the tree-valued random walk in random environment (RWRE) that is studied by Pemantle and Peres [13] and Hu and Shi [14]. For the model of RWRE on the trees that they studied, the random environment processω:=(ω(x,·),x,y∈T)is a family of i.i.d nondegenerate random vectors and the processX={Xn,n∈Z+}is a nearest-neighbor walk satisfying some conditions. But in our model,our environmental processξ={ξt,t∈T}can be any Markov chain indexed by trees. Givenξ, the process{Xt,t∈T}is another Markov chain indexed by trees with the lawPξ.In this paper we assume that{ξt,t∈T}is a nonhomogeneousT-indexed Markov chain on state spaceΘ. The probability of going fromitojin one step in theθth environment is denoted byPθ(i,j). We also suppose that the one-step transition probability of going fromαtoβfor nonhomogeneousT-indexed Markov chain{ξt,t∈T}isKt(α,β). In this case,{ξt,Xt,t∈T}is a Markov chain indexed byTwith initial distributionq=(q(θ,i))and one-step transition onΘ×𝒳 determined by
(7)Pt(α,i;β,j)=Kt(α,β)Pα(i,j),
whereq(θ,i)=P(ξ0=θ,X0=i). Then{ξt,Xt,t∈T}will be called the bichain indexed by treeT. Obviously, we have
(8)P(ξT(n)=αT(n),XT(n)=xT(n))=q(α0,x0)∏t∈T(n)∖{0}‍Pt(α1t,x1t;αt,xt).


## 2. Main Results

For every finiten∈N, let{Xt,t∈T}be a Markov chain indexed by an infinite Cayley treeTin Markovian environment{ξt,t∈T}, which is defined as in Definition 2. Now we suppose thatgt(α,i,β,j)are functions defined onΘ×𝒳×Θ×𝒳. Letλbe a real number, L0={0},ℱn=σ(ξT(n),XT(n)); now we define a stochastic sequence as follows:
(9)φn(λ,ω)=eλ∑t∈T(n)∖{0}gt(ξ1t,X1t,ξt,Xt)∏t∈T(n)∖{0}E[eλgt(ξ1t,X1t,ξt,Xt)∣ξ1t,X1t].
At first we come to prove the following fact.Lemma 5.
{
φ
n
(
λ
,
ω
)
,
ℱ
n
,
n
≥
1
}is a nonnegative martingale.Proof of Lemma5.
Obviously, we have(10)P(ξLn=αLn,XLn=xLn∣ξT(n-1)11=αT(n-1),XT(n-1)=xT(n-1))=P(ξT(n)=αT(n),XT(n)=xT(n))P(ξT(n-1)=αT(n-1),XT(n-1)=xT(n-1))=∏t∈Ln‍P(ξt=αt,Xt=xt∣ξ1t=α1t,X1t=x1t).
Here, the second equation holds because of the fact that{ξt,Xt,t∈T}is a bichain indexed by treeTand (8) is being used. Furthermore, we have
(11)E[eλ∑t∈Lngt(ξ1t,X1t,ξt,Xt)∣ℱn-1]=∑αLn,xLn‍eλ∑t∈Lngt(ξ1t,X1t,αt,xt)ggggg×P(ξLn=αLn,XLn=xLn∣ξT(n-1),XT(n-1))=∑αLn,xLn‍∏t∈Ln‍eλgt(ξ1t,X1t,αt,xt)ggggg×P(ξt=αt,Xt=xt∣ξ1t,X1t)=∏t∈Ln‍∑(αt,xt)∈Θ×𝒳‍eλgt(ξ1t,X1t,αt,xt)×P(ξt=αt,Xt=xt∣ξ1t,X1t)=∏t∈Ln‍E[eλgt(ξ1t,X1t,ξt,Xt)∣ξ1t,X1t]a.s.
On the other hand, we also have
(12)φn(λ,ω)=φn-1(λ,ω)×eλ∑t∈Lngt(ξ1t,X1t,ξt,Xt)∏t∈LnE[eλgt(ξ1t,X1t,ξt,Xt)∣ξ1t,X1t].
Combining (11) and (12), we get
(13)E[φn(λ,ω)∣ℱn-1]=φn-1(λ,ω)a.s.
Thus, we complete the proof of Lemma 5.Theorem 6.
Let{Xt,t∈T}be a Markov chain indexed by an infinite Cayley treeTin a nonhomogeneous Markovian environment{ξt,t∈T}. Suppose that the initial distribution and the transition probability functions satisfy
(14)q(α0,x0)>0,Pt(α,i;θ,j)>0,fffor∀α0,α,θ∈Θ;x0,i,j∈𝒳,at=min{Pt(α,i;θ,j),α,θ∈Θ;i,j∈𝒳},t∈T∖{0},
if there exist two positive constantscandmsuch that
(15)limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍ec/at=m<∞.
Denote|Θ|=M, |𝒳|=N, and
(16)Pt(ξ1t,X1t;ξt,Xt)=Pt(ξt,Xt∣ξ1t,X1t);
then we have
(17)limn→∞|T(n)|∑t∈T(n)∖{0}Pt(ξ1t,X1t;ξt,Xt)-1=1MNa.s.Proof.
By Lemma5, we have known that{φn(λ,ω),ℱn,n≥1}is a nonnegative martingale. According to Doob martingale convergence theorem, we have
(18)limnφn(λ,ω)=φ(λ,ω)<∞a.s.,
so that
(19)limn→∞lnφn(λ,ω)|T(n)|=0a.s.,
which implies that
(20)limsupn→∞lnφn(λ,ω)|T(n)|≤0a.s.
We arrive at
(21)limsupn→∞1|T(n)|×∑t∈T(n)∖{0}‍{λgt(ξ1t,X1t,ξt,Xt)eλgt(ξ1t,X1t,ξt,Xt)hhhhhhhfk.h-ln[E[eλgt(ξ1t,X1t,ξt,Xt)∣ξ1t,X1t]]}≤0a.s.
Combining (20) with the inequalitieslnx≤x-1(x>0)and0≤ex-1-x≤2-1x2e|x| and takinggt(ξ1t,X1t,ξt,Xt)=Pt(ξ1t,X1t;ξt,Xt)-1, it follows that
(22)limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍[Pt(ξ1t,X1t;ξt,Xt)-1λ-λMN]≤limsupn→∞1|T(n)|×∑t∈T(n)∖{0}‍{ln[E[eλPt(ξ1t,X1t;ξt,Xt)-1∣ξ1t,X1t]]gggggggggg.[E[eλPt(ξ1t,X1t;ξt,Xt)-1∣ξ1t,X1t]]-λMN}≤limsupn→∞1|T(n)|×∑t∈T(n)∖{0}‍{E[eλPt(ξ1t,X1t;ξt,Xt)-1∣ξ1t,X1t]hhhhhhhhhhhh[eλPt(ξ1t,X1t;ξt,Xt)-1∣ξ1t,X1t]-1-λMN}≤limsupn→∞1|T(n)|×∑t∈T(n)∖{0}‍∑α∈Θ‍∑i∈𝒳‍Pt(ξ1t,X1t;α,i)×[eλ/Pt(ξ1t,X1t;α,i)-1-λPt(ξ1t,X1t;α,i)]≤λ22limsupn→∞1|T(n)|×∑t∈T(n)∖{0}‍∑α∈Θ‍∑i∈𝒳‍1Pt(ξ1t,X1t;α,i)e|λ|/Pt(ξ1t,X1t;α,i)≤λ2MN2limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍1ate|λ|/ata.s.
Note that the following elementary fact holds:
(23)maxx>0{xγx}=-e-1lnγ,0<γ<1.
Let0<λ<c. It follows from (15), (22), and (23) that
(24)limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍[Pt(ξ1t,X1t;ξt,Xt)-1-MN]≤λMN2limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍1ateλ/at=λMN2limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍1at(eλ-c)1/atec/at≤λMN2e(c-λ)ma.s.
Here, the second equation holds because by lettingλ→0+in inequality (24), we get
(25)limsupn→∞1|T(n)|×∑t∈T(n)∖{0}‍[Pt(ξ1t,X1t;ξt,Xt)-1-MN]≤0a.s.
If-c<λ<0, similar to the analysis of inequality (24), by using (15), (22), and (23) again, we can arrive at
(26)liminfn→∞1|T(n)|∑t∈T(n)∖{0}‍[Pt(ξ1t,X1t;ξt,Xt)-1-MN]≥λMN2limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍1ate-λ/at≥λMN2limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍1at(e-λec)1/atec/at≥λMN2e(λ+c)ma.s.
Lettingλ→0-in inequality (26), we get
(27)liminfn→∞1|T(n)|×∑t∈T(n)∖{0}‍[Pt(ξ1t,X1t;ξt,Xt)-1-MN]≥0a.s.
Combining (25) and (27), we obtain that our assertion (17) is true.Corollary 7.
Let{Xt,t∈T}be a nonhomogeneous Markov chain indexed by an infinite Cayley treeT. Suppose that the initial distribution and the transition probability functions satisfy
(28)p(x0)>0,Pt(i,j)>0,at=min{Pt(i,j),i,j∈𝒳},t∈T∖{0},
if there exist two positive constantscandmsuch that
(29)limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍ec/at=m<∞.
Denote|𝒳|=N; then we have
(30)limn→∞|T(n)|∑t∈T(n)∖{0}Pt(Xt∣X1t)-1=1Na.s.Proof.
If we takeΘ={θ}, that is,|Θ|=1, then the model of Markov chain indexed by treeTin Markovian environment reduces to the formulation of a nonhomogeneous Markov chain indexed by treeT. Then we arrive at our conclusion (30) directly from Theorem 6.Corollary 8 (see [15]).
Let{Xn,n≥0}be a Markov chain in a nonhomogeneous Markovian environment{ξn,n≥0}. Suppose that the initial distribution and the transition probability functions satisfy
(31)q(α0,x0)>0,Pn(α,i;θ,j)>0,an=min{Pn(α,i;θ,j),α,θ∈Θ;i,j∈𝒳},n≥1,
if there exist two positive constantscandmsuch that
(32)limsupn→∞1n∑k=1n‍ec/ak=m<∞.
Denote|Θ|=M, |𝒳|=N, and
(33)Pk(ξk-1,Xk-1;ξk,Xk)=Pk(ξk,Xk∣ξk-1,Xk-1);
then we have
(34)limn→∞n∑k=1nPk(ξk-1,Xk-1;ξk,Xk)-1=1MNa.s.Proof.
If every vertex of the treeThas degree2, then the nonhomogeneous Markov chain indexed by treeTdegenerates into the nonhomogeneous Markov chain on line; thus, this corollary can be obtained from Theorem 6 directly.



---

*Source: 961571-2013-12-05.xml*