Some Limit Properties of Random Transition Probability for Second-Order Nonhomogeneous Markov Chains Indexed by a Tree

Volume 2009, Article ID 503203,10pages doi:10.1155/2009/503203

Research Article

Some Limit Properties of Random Transition Probability for Second-Order Nonhomogeneous Markov Chains Indexed by a Tree

Zhiyan Shi and Weiguo Yang

Faculty of Science, Jiangsu University, Zhenjiang 212013, China

Correspondence should be addressed to Zhiyan Shi,[email protected] Received 1 September 2009; Accepted 24 November 2009

Recommended by Andrei Volodin

We study some limit properties of the harmonic mean of random transition probability for a second-order nonhomogeneous Markov chain and a nonhomogeneous Markov chain indexed by a tree. As corollary, we obtain the property of the harmonic mean of random transition probability for a nonhomogeneous Markov chain.

Copyrightq2009 Z. Shi and W. Yang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

A tree is a graph G {T, E} which is connected and contains no circuits. Given any two verticesσ, tσ /t∈T, letσtbe the unique path connectingσandt. Define the graph distance dσ, tto be the number of edges contained in the pathσt.

LetT_obe an arbitrary infinite tree that is partially finitei.e., it has infinite vertices, and each vertex connects with finite verticesand has a rooto. Meanwhile, we consider another kind of double root tree T; that is, it is formed with the root o of T_o connecting with an arbitrary point denoted by the root−1. For a better explanation of the double root tree T, we take Cayley treeTC,N for example. It is a special case of the treeTo, the rootoof Cayley tree hasNneighbors, and all the other vertices of it haveN1 neighbors each. The double root treeT_C,N seeFigure 1is formed with rootoof treeT_C,N connecting with another root

−1.

Letσ,tbe vertices of the double root treeT. Writet≤σσ, t / −1iftis on the unique path connectingotoσ, and|σ|for the number of edges on this path. For any two verticesσ, tσ, t / −1of the treeT, denote byσ∧tthe vertex farthest fromosatisfyingσ∧t ≤σand σ∧t≤t.

Level 3 Level 2 Level 1

Level 0 Level−1

t 1t

2_t

Rooto Root−1

Figure 1: Double root treeT_C,2 .

The set of all vertices with distance nfrom rooto is called thenth generation ofT, which is denoted byL_n. We say thatL_nis the set of all vertices on levelnand especially root

−1 is on the−1st level on treeT. We denote byTⁿ the subtree of the treeT containing the vertices from level−1 the root−1to levelnand denote byT_oⁿ the subtree of the treeT_o containing the vertices from level 0the roototo leveln. Lett/o,−1be a vertex of the tree T. We denote the first predecessor oftby 1t, the second predecessor oftby 2t, and denote by n_tthenth predecessor oft. LetX^A {Xt, t∈A}, and letx^Abe a realization ofX^Aand denote by|A|the number of vertices ofA.

Definition 1.1. LetG{1,2, . . . , N}andPz|y, xbe nonnegative functions onG³. Let

P

P

z|y, x , P

z|y, x

≥0, x, y, z∈G. 1.1

If

z∈G

P

z|y, x

1, 1.2

thenPis called a second-order transition matrix.

Definition 1.2. LetT be double root tree and letG {1,2, . . . , N}be a finite state space, and let{Xt, t∈T}be a collection ofG-valued random variables defined on the probability space Ω,F, P. Let

P

p x, y

, x, y∈G 1.3

be a distribution onG², and

P_t P_t

z|y, x

, x, y, z∈G, t∈T\ {o}{−1} 1.4

be a collection of second-order transition matrices. For any vertex tt /o,−1, if P

X_tz|X_1ty, X_2t x, X_σ forσ∧t≤1_t P

X_tz|X_1ty, X_2tx P_t

z|y, x

∀x, y, z∈G, P

X₋₁x, Xoy p

x, y

, x, y∈G,

1.5

then{Xt, t∈T}is called aG-value second-order nonhomogeneous Markov chain indexed by a treeT with the initial distribution1.3and second-order transition matrices1.4, or called aT-indexed second-order nonhomogeneous Markov chain.

Remark 1.3. Benjamini and Peres 1 have given the definition of the tree-indexed homogeneous Markov chains. Here we improve their definition and give the definition of the tree-indexed second-order nonhomogeneous Markov chains in a similar way. We also give the following definitionDefinition 2.3of tree-indexed nonhomogeneous Markov chains.

There have been some works on limit theorems for tree-indexed stochastic processes.

Benjamini and Peres1have given the notion of the tree-indexed Markov chains and studied the recurrence and ray-recurrence for them. Berger and Ye 2 have studied the existence of entropy rate for some stationary random fields on a homogeneous tree. Ye and Berger see 3, 4, by using Pemantle’s result 5 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 Liu6have studied a strong law of large numbers for the frequency of occurrence of states for Markov chains field on a homogeneous treea particular case of tree-indexed Markov chains field and PPG-invariant random fields. Yang see7 has studied the strong law of large numbers for frequency of occurrence of state and Shannon-McMillan theorem for homogeneous Markov chains indexed by a homogeneous tree. Recently, Yangsee8has studied the strong law of large numbers and Shannon-McMillan theorem for nonhomogeneous Markov chains indexed by a homogeneous tree. Huang and Yang see9 have also studied the strong law of large numbers for Markov chains indexed by an infinite tree with uniformly bounded degree.

LetPtxt | x1t, x2t PtXt xt | X1t x1t, X2t x2t. ThenPtXt |X1t, X2tis called the random transition probability of a T-indexed second-order nonhomogeneous Markov chain. Liu 10has studied a strong limit theorem for the harmonic mean of the random transition probability of finite nonhomogeneous Markov chains. In this paper, we study some limit properties of the harmonic mean of random transition probability for a second-order nonhomogeneous Markov chain and a nonhomogeneous Markov chain indexed by a tree.

As corollary, we obtain the results of10,11.

2. Main Results

Lemma 2.1. Let{Xt, t∈T}be aT-indexed second-order nonhomogeneous Markov chain with state spaceGdefined as inDefinition 1.2, and let{gtx, y, z, t∈T}be a collection of functions defined on G³. LetL₋₁{−1},L₀{o}, andFnσX^Tn. Set

t_nλ, ω e^{λt∈Tn\{o}{−1}gtX2t,X1t,Xt}

t∈Tⁿ\{o}{−1}E

e^{λgtX2t,X1t,Xt}|X1t, X2t

, 2.1 whereλis a real number. Then{tnλ, ω,Fn, n≥1}is a nonnegative martingale.

Proof. Obviously, whenn≥1, we have

P x^Tn

P X^Tn x^Tn

PX−1x₋₁, X_ox_o

t∈Tⁿ\{o}{−1}

P_txt|x_1t, x_2t. 2.2

Hence

P X^Ln x^Ln |X^Tn−1x^Tn−1

P x^Tn P

x^Tn−1

t∈Ln

Ptxt|x1t, x2t. 2.3

Then

E

e^{λt∈LngtX2t,X1t,Xt}| F_n−1

x^Ln∈G^Ln

e^{λt∈LngtX2t,X1t,xt}P X^Ln x^Ln |X^Tn−1

x^Ln∈G^Ln

e^{λt∈LngtX2t,X1t,xt}

t∈Ln

P_txt|X_1t, X_2t

t∈Ln

xt∈G

e^{λgtX2t,X1t,xt}P_txt|X_1t, X_2t

t∈Ln

E

e^{λgtX2t,X1t,Xt}|X_1t, X_2t a.e.

2.4

On the other hand, we also have

tnλ, ω t_n−1λ, ω e^{λt∈LngtX2t,X1t,Xt}

t∈LnE

e^{λgtX2t,X1t,Xt}|X_1t, X_2t. 2.5

Combining2.4and2.5, we arrive at

Etnλ, ω| F_n−1 t_n−1λ, ω a.e., 2.6

Thus the lemma is proved.

Theorem 2.2. Let{Xt, t∈T}be aT-indexed second-order nonhomogeneous Markov chain with state spaceG defined as inDefinition 1.2, and its initial distribution and probability transition collection satisfying

PX₋₁x₋₁, X_ox_o P x, y

>0, ∀x, y∈G, Pt

z|y, x

>0, ∀x, y, z∈G, t∈T\ {o}{−1}, 2.7

respectively. Let

b_tmin P_t

z|y, x

, x, y, z∈G

, t∈T\ {o}{−1}. 2.8

If there existsa>0such that

lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

e^a/btM <∞, 2.9

then the harmonic mean of the random conditional probability{PtXt|X1t, X2t, t∈Tⁿ\ {o}{−1}}

converges to 1/Na.e., that is,

nlim→ ∞

Tⁿ

t∈Tⁿ\{o}{−1}PtXt|X1t, X2t⁻¹ 1

N a.e. 2.10

Proof. Letg_tx, y, z P_tz|y, x⁻¹inLemma 2.1. Then it follows fromLemma 2.1that

t_nλ, ω e^{λt∈Tn\{o}{−1}PtXt|X1t,X2t−1}

t∈Tⁿ\{o}{−1}E

e^{λPtXt|X1t,X2t−1} |X1t, X2t

2.11

is a nonnegative martingale. According to Doob martingale convergence theorem, we have

nlim→ ∞t_nλ, ω tλ, ω<∞ a.e. 2.12

Thus

lim sup

n→ ∞

T1ⁿlnt_nλ, ω≤0 a.e. 2.13

It follows from2.11and2.13that

lim sup

n→ ∞

T1ⁿ

⎧⎨

⎩λ

t∈Tⁿ\{o}{−1}

P_tXt|X_1t, X_2t⁻¹

−

t∈Tⁿ\{o}{−1}

lnE

e^{λPtXt|X1t,X2t−1} |X_1t, X_2t⎫

⎬

⎭≤0 a.e.

2.14

By2.14and the inequalities lnx≤x−1x >0, and 0≤e^x−1−x≤x²/2e^|x|, we have

lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

λP_tXt|X_1t, X_2t⁻¹−λN

≤lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

lnE

e^{λPtXt|X1t,X2t−1} |X1t, X2t

−λN

≤lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

E

e^{λPtXt|X1t,X2t−1}|X1t, X2t

−1−λN

lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

xt∈G

Ptxt|X1t, X2t

e^{λPtxt|X1t,X2t−1}−1−λPtxt|X1t, X2t⁻¹

≤ λ²

2lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

xt∈G

P_txt|X_1t, X_2t⁻¹e^{|λ|Ptxt|X1t,X2t−1}

≤ λ²

2lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

xt∈G

1 b_te^|λ|/bt

≤ λ²N

2 lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

1 bt

e^|λ|/bt a.e.

2.15 It is easy to see that

max0<λ<1{xλ^x, x >0}−e⁻¹

lnλ. 2.16

Let 0< λ < a, by2.15,2.16,2.8, and2.9we have

lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

PtXt|X1t, X2t⁻¹−N

≤ λN

2 lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

1 b_te^λ/bt

λN

2 lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

1 b_t

e^λ e^a

1/bt

e^a/bt

≤ λN

2a−λelim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

e^a/bt

λN 2a−λeM,

2.17

Lettingλ → 0, by2.17, we have

lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

PtXt|X1t, X2t⁻¹−N

≤0 a.e. 2.18

Let−a < λ <0, by2.15,2.8, and2.9we have

lim inf

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

P_tXt|X_1t, X_2t⁻¹−N

≥ λN

2 lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

1 b_te^−λ/bt

λN

2 lim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

1 b_t

e^−λ e^a

_1/bt e^a/bt

≥ λN

2aλelim sup

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

e^a/bt

λN 2aλeM.

2.19

Lettingλ → 0⁻, by2.19, we have

lim inf

n→ ∞

T1ⁿ

t∈Tⁿ\{o}{−1}

P_tXt|X_1t, X_2t⁻¹−N

≥0 a.e. 2.20

Combining2.18and2.20, we obtain2.10directly.

From the definition above, we know that the difference between T_o and T lies in whether the rootois connected with another root−1. In the following, we will investigate some properties of the harmonic mean of the transition probability of nonhomogeneous Markov chains on the treeTo. First, we give the definition of nonhomogeneous Markov chains on the treeT_o.

Definition 2.3. LetTobe an arbitrary tree that is partly finite, letG {1,2, . . . , N}be a finite state space, and let{Xt, t∈To}be a collection ofG-valued random variables defined on the probability spaceΩ,F, P. Let

P

px

, x∈G 2.21

be a distribution onG, and

Pt Pt

y|x

, x, y∈G, t∈To\ {o} 2.22

be a collection of transition matrices. For any vertextt /o, if

P

Xty|X1tx, Xσ forσ∧t≤1t

P

Xty|X1tx Pt

y|x

, ∀x, y∈G, PXox px, x∈G,

2.23

then {Xt, t ∈ To} is called a G-value nonhomogeneous Markov chain indexed by a tree T_o with the initial distribution2.21and transition matrices 2.22, or called a T_o-indexed nonhomogeneous Markov chain.

Let P_txt | x_1t P_tXt x_t | X_1t x_1t. Then P_tXt | X_1tis called the random transition probability of aT_o-indexed nonhomogeneous Markov chain. Since a Markov chain is a special case of a second-order Markov chain, we may regard the nonhomogeneous Markov chain onToto be a special case of the second-order nonhomogeneous Markov chain onTwhen we do not take the difference ofT_oandTon the root−1 into consideration. Thus for the nonhomogeneous Markov chain on the treeTo, we can get the results similar toLemma 2.1 andTheorem 2.2.

Lemma 2.4. Let{Xt, t∈T_o}be aT_o-indexed second-order nonhomogeneous Markov chain with state spaceGdefined as inDefinition 2.3, and let{gtx, y, t ∈To}be a collection of functions defined on G². LetL₀{o}andFnσX^Ton. Set

t_nλ, ω e^λ

t∈Tn

o \{o}gtX1t,Xt

t∈Toⁿ\{o}E

e^λgtX1t,Xt|X_1t, 2.24

whereλis a real number. Then{tnλ, ω,Fn, n≥1}is a nonnegative martingale.

Theorem 2.5. Let{Xt, t ∈ To}be aTo-indexed nonhomogeneous Markov chain with state spaceG defined as inDefinition 2.3, and its initial distribution and probability transition collection satisfying

PXox px>0, ∀x∈G, P_t

y|x

>0, ∀x, y∈G, t∈T_o\ {o}, 2.25

respectively. Let

btmin Pt

y|x

, x, y∈G

, t∈To\ {o}. 2.26

If there existsa>0such that

lim sup

n→ ∞

1 T_oⁿ

t∈Toⁿ\{o}

e^a/btM <∞, 2.27

then the harmonic mean of the random conditional probability {PtXt | X_1t, t ∈ T_oⁿ \ {o}}

converges to 1/Na.e., that is

nlim→ ∞

Toⁿ

t∈Toⁿ\{o}PtXt|X1t⁻¹ 1

N a.e. 2.28

If the successor of each vertex of the tree T_o has only one vertex, then the nonhomogeneous Markov chains on the treeTodegenerate into the general nonhomogeneous Markov chains. Thus we obtain the results in10,11.

Corollary 2.6see10,11. Let{Xn, n≥0}be a nonhomogeneous Markov chain with state space G, and its initial distribution and probability transition sequence satisfying

pi>0, i∈G, Pk

i, j

>0, i, j∈G, k1,2, . . . , 2.29 respectively. Let

a_kmin P_k

i, j

, i, j∈G

, k1,2, . . . . 2.30

If there existsa>0such that

lim sup

n→ ∞

1 n

n k1

e^a/ak M <∞, 2.31

then

nlim→ ∞

_n n

k1PkXk|X_k−1⁻¹ 1

N a.e. 2.32

Proof. When the successor of each vertex of the tree To has only one vertex, the nonhomogeneous Markov chains on the treeT_odegenerate into the general nonhomogeneous Markov chains, the corollary follows directly fromTheorem 2.5.

Acknowledgments

This work is supported by the National Natural Science Foundation of China10571076, and the Postgraduate Innovation Project of Jiangsu University no. CX09B 13XZ and the Student’s Research Foundation of Jiangsu Universityno. 08A175.

References

1 I. Benjamini and Y. Peres, “Markov chains indexed by trees,” The Annals of Probability, vol. 22, no. 1, pp. 219–243, 1994.

2 T. Berger and Z. X. Ye, “Entropic aspects of random fields on trees,” IEEE Transactions on Information Theory, vol. 36, no. 5, pp. 1006–1018, 1990.

3 Z. Ye and T. Berger, “Ergodicity, regularity and asymptotic equipartition property of random fields on trees,” Journal of Combinatorics, Information & System Sciences, vol. 21, no. 2, pp. 157–184, 1996.

4 Z. Ye and T. Berger, Information Measures for Discrete Random Fields, Science Press, Beijing, China, 1998.

5 R. Pemantle, “Automorphism invariant measures on trees,” The Annals of Probability, vol. 20, no. 3, pp. 1549–1566, 1992.

6 W. Yang and W. Liu, “Strong law of large numbers for Markov chains field on a Bethe tree,” Statistics

& Probability Letters, vol. 49, no. 3, pp. 245–250, 2000.

7 W. Yang, “Some limit properties for Markov chains indexed by a homogeneous tree,” Statistics &

Probability Letters, vol. 65, no. 3, pp. 241–250, 2003.

8 W. Yang and Z. Ye, “The asymptotic equipartition property for nonhomogeneous Markov chains indexed by a homogeneous tree,” IEEE Transactions on Information Theory, vol. 53, no. 9, pp. 3275–

3280, 2007.

9 H. Huang and W. Yang, “Strong law of large numbers for Markov chains indexed by an infinite tree with uniformly bounded degree,” Science in China, vol. 51, no. 2, pp. 195–202, 2008.

10 W. Liu, “A strong limit theorem for the harmonic mean of the random transition probabilities of finite nonhomogeneous Markov chains,” Acta Mathematica Scientia, vol. 20, no. 1, pp. 81–84, 2000Chinese.

11 W. Liu, “A limit property of random conditional probabilities and an approach of conditional moment generating function,” Acta Mathematicae Applicatae Sinica, vol. 23, no. 2, pp. 275–279, 2000Chinese.