Tree-Indexed Markov Chains in Random Environment and Some of Their Strong Limit Properties?

Zhiyan SHI Bei WANG Weiguo YANG Zhongzhi WANG

Abstract In this paper, the authors first introduce the tree-indexed Markov chains in random environment, which takes values on a general state space. Then, they prove the existence of this stochastic process, and develop a class of its equivalent forms. Based on this property,some strong limit theorems including conditional entropy density are studied for the tree-indexed Markov chains in random environment.

Keywords Random environment, Tree-indexed Markov chains, Strong limit theorem, Conditional entropy density

1 Introduction

Tree-indexed random process is one subfield of probability theory developed recently. Benjamini and Peres[3]gave the definition of tree-indexed Markov chains and studied the recurrence and the ray-recurrence of them. Berger and Ye[4]studied the existence of entropy rate for some stationary random fields on a homogenous tree. Ye and Berger [33–34], by using Pemantle’s result(see [23])and a combinational approach,obtained Shannon-McMillan theorem in probability for a PPG-invariant and ergodic random field on a homogenous tree. Yang and Liu [31]studied the strong law of large numbers and Shannon-McMillan theorem for Markov chain fields on trees (a particular case of tree-indexed Markov chains and PPG-invariant random fields).Yang [30] obtained the strong law of large numbers and the Shannon-McMillan theorem for tree-indexed Markov chains. Huang and Yang [17]studied the strong law of large numbers and Shannon-McMillian theorem for Markov chains indexed by a uniformly bounded tree. Dong,Yang and Bai[14]studied the strong law of large numbers and the Shannon-McMillan theorem for nonhomogeneous Markov chains indexed by a Cayley tree. Dembo, Mrters and Sheffield[13] studied large deviations of Markov chains indexed by random trees. Guyon [15] gave the definition of homogeneous bifurcating Markov chains indexed by a binary tree taking values in general state space which is the generalization of bifurcating autoregressive model and studied their limit theorems, and applied these results to detect cellular aging. Delmas and Marsalle[12] studied asymptotic results for bifurcating Markov chains indexed by Galton-Watson tree instead of a regular tree. Dang, Yang and Shi [11] studied the equivalent properties of discrete form of nonhomogeneous bifurcating Markov chains indexed by a binary tree, meanwhile the strong law of large numbers and the Shannon-McMillan theorem were studied for these Markov chains with finite state space. Peng, Yang and Shi [24] studied the strong law of large numbers and Shannon-McMillan theorem with a.e. convergence for finite Markov chains indexed by a spherically symmetric tree. Yang and Yang [29] established the generalized entropy ergodic theorem for nonhomogeneous Markov chains indexed by a Cayley tree. Shi and Yang [27] gave the definition of tree-indexed Markov chains in discrete random environment. Shi, Zhong and Fan [28] studied the strong law of large numbers and Shannon-McMillan theorem for Markov chains indexed by a Cayley tree in a Markovian environment on discrete state space. Shi,Wang et al. [26] have studied the generalized entropy ergodic theorem for non-homogeneous bifurcating Markov chains indexed by abbinary tree.

The research on Markov chains in random environment has a quite long history. Nawrotzki[21–22] established its theoretical foundations. Cogburn [8–10] constructed a Hopf-chain, and used Hopf-chain theorem to develop a series of theorems for Markov chains in random environment which contains ergodic theorem, central limit theorem, periodic relationship between direct convergence and transfer functions and the existence of invariant probability measure.Hu and Hu [16] studied the equivalence theorems of Markov processes in random environment with continuous time parameter. Liu and Li et al. [18] investigated the strong limit theorems for the conditional entropy density for Markov chain in a bi-infinite random environment by constructing a nonnegative martingale.

In this paper, the definition of tree-indexed Markov chains in random environment is proposed,where the state of random environment takes values in a general state space. Meanwhile,we give certain equivalent form of tree-indexed Markov chains in random environment,and verify the existence of this stochastic process on some probability space. Finally,some strong limit properties including a strong limit theorem of conditional entropy density are studied for the tree-indexed Markov chains in random environment.

The rest of this paper is organized as follows. In Section 2, we describes some preliminaries, some concepts and properties of tree-indexed Markov chains in random environment are provided. In Section 3, we provide some equivalent properties and existence for tree-indexed Markov chains in random environment. In Section 4, we present some strong limit theorems for tree-indexed Markov chains in random environment. Finally, the proofs of some theorems(Theorems 3.1–3.2 and 4.1) are provided in Section 5.

2 Preliminaries

Let T be a locally finite and infinite tree, and for any two vertices σt ∈T, there exists a unique path σ =z1,z2,··· ,zm=t from σ to t, where z1,z2,··· ,zmare distinct and zi,zi+1are adjacent vertices. Thus the distance from σ to t is defined as m ?1, namely, the number of edges in the path connecting σ and t. In order to label the tree T, we select a vertex as root o.For any two vertices σ and t of tree T, we write σ ≤t if σ is on the unique path from root o to t. Let σ ∧t be the vertex satisfying σ ∧t ≤t and σ ∧t ≤σ.

Let t be any vertex of T and we write |t| as the distance from o to t. The expression|t|=n indicates that vertex t is on the nth level of T. Let Lndenote the set containing all the vertices on the nth level, anddenote the set of all the vertices from level m to level n. We denote the subtree of tree T by T(n), which contains the vertices from level 0 (the root o) to level n. If the root of a tree has N neighboring vertices and other vertices have N +1 neighboring vertices, we call this type of tree a Cayley tree and denote it by TC,N. That is, for any vertex t of Cayley tree TC,N, it has N neighboring vertices on the next level (see Figure 1). For any vertex t of T,we denote the predecessor of t by 1t,t is called the son of 1t. Let σ be any vertex,if σ ∧t ≤1t, we say σ is in the front of t. Let Tt={σ |σ ∧t ≤1t}denote the set of all vertices that are in front of t (see Figure 2).

Let (?,F,P) be a probability space, and T be any tree, {Xt,t ∈T} be a tree-indexed stochastic process defined on(?,F,P). Consider a subgraph A of T,denote XA={Xt,t ∈A},let xAbe the realization of XA, and denote by |A| the number of vertices of A.

Figure 1 Cayley tree TC,2.

Figure 2 The vertices of Tt.

We first introduce the definition of Markov chain indexed by tree as follows.

Definition 2.1(see [14]) Let T be a locally finite and infinite tree, and χ ={1,2,···} be a discrete state space. Suppose that {Xt,t ∈T} is a collection of random variables defined on probability space(?,F,P) taking values in χ. Let p={p(x),x ∈χ} be a probability distribution on χ and {Pt=pt(x,y),t ∈T} be a collection of transition matrices. If for any t ∈T{o},

and

{Xt,t ∈T} will be called the tree-indexed nonhomogeneous Markov chains with initial distribution p and transition matrices {Pt,t ∈T} taking values in χ, or called nonhomogeneous Markov chains indexed by a tree with initial distribution p and transition matrices {Pt,t ∈T}taking values in χ. If Pthave nothing to do with t, {Xt,t ∈T} will be called the tree-indexed homogeneous Markov chains with initial distribution p and transition matrix {Pt=P,t ∈T}.

Remark 2.1If we select a suitable regular conditional probability,(2.1)can be represented as follows:

Remark 2.2Above definition is a natural generalization of the definition of homogenous Markov chains indexed by trees (see [3]).

Let χ={1,2,···},A be σ-field produced by all subsets of χ, and (Θ,B) be a metric space,where B is Borel σ-field. Let ξT={ξt,t ∈T}and XT={Xt,t ∈T}be a collections of random variables on probability space (?,F,P) taking values in Θ and χ, respectively. Suppose pθ={p(θ;x),x ∈χ},θ ∈Θ, is a distribution with parameter θ and Pθ={p(θ;x,y),x,y ∈χ},θ ∈Θ,is a transition matrices with parameter θ defined on χ2. We assume that p(θ;x)are measurable on B for fixed x and p(θ;x,y) are also measurable on B for fixed x,y.

In the following, we will provide the definition of tree-indexed Markov chains in random environment,which is closely related to the definition of Markov chains indexed by a tree defined by Definition 2.1 and the definition of Markov chains in single infinite random environment.Before doing this, we first review the definition of Markov chains in single infinite random environment.

Definition 2.2(see [8]) Let= {Xn,n ≥0} and= {ξn,n ≥0} be two sequences of random variables taking values in χ and Θ, respectively. If

and

Similar to the definition of Markov chains in single infinite random environment and the definition of tree-indexed Markov chains, we will give the definition of tree-indexed Markov chains in random environment as follows.

Definition 2.3Let ξT={ξt,t ∈T}and XT={Xt,t ∈T}be double tree-indexed stochastic processes on probability space (?,F,P) taking values in Θ and χ, respectively. If

and

XTwill be called tree-indexed Markov chains in random environment ξTdetermined by distributions pθwith parameter θ and transition matrices Pθwith parameter θ, or (XT,ξT) will be called tree-indexed Markov chains in random environment.

Remark 2.3From Definition 2.3,it is easy to see that if(XT,ξT)is a tree-indexed Markov chain in random environment, let A be a subset of Ttwhich contains 1t, then

Remark 2.4If Θ is a discrete set. The definition of tree-indexed Markov chains in random environment becomes the definition of tree-indexed Markov chains in discrete random environment (see [27]).

Remark 2.5If ξTonly takes fixed point cT= {ct,t ∈T}, then XTis a nonhomogeneous Markov chain indexed by tree with initial distribution p(c0;x)and the transition matrices{Pt=p(c1t;x,y),t ∈T}. In fact, in this case, P(Xo=xo)=P(Xo=xo| →ξ) and p(ξo;xo)=p(co;xo)a.e.. Hence we have

Since also

So the above conclusion is true.

If for any t ∈T,ct= c0, then XTis a homogeneous Markov chain indexed by trees with initial distribution p(c0;x) and the transition matrix {P =p(c0;x,y),t ∈T}.

Remark 2.6If there is only one son for each vertex of the tree, and T is the nonnegative integer set N, the tree-indexed Markov chains in random environment will degenerate into Markov chains in single infinite random environment.

3 Equivalent Properties and Existence

In this section, we present the equivalent properties for tree-indexed Markov chains in random environment.

Theorem 3.1Let T be a locally finite and infinite tree,and(XT,ξT)be double tree-indexed stochastic process defined on the probability space (?,F,P) taking values in (χ,Θ). Then the following four propositions are equivalent:

(a)(XT,ξT)is a tree-indexed Markov chain in random environment defined as in Definition 2.3;

(b) XTand ξTsatisfy (2.6) and

(c) XTand ξTsatisfy (2.6) and

(d) (XT,ξT)has the following finite dimensional distribution: For any m,n ∈N and t ∈T,Bt∈B,

where PξTis a distribution of ξT.

The proof of this theorem can be found in Section 5.

Remark 3.1From(d)of Theorem 3.1 and Kolmogorov’s extension theorem, there exists a tree-indexed Markov chain in random environment(XT,ξT) defined on some probability space(?,F,P) such that (3.3) holds. In Theorem 3.2, we also provide an alternative approach to prove the existence of tree-indexed Markov chains in random environment.

Corollary 3.1If Θ is a countable set, (XT,ξT) is a tree-indexed Markov chain in discrete random environment if and only if

ProofIf Θ is a countable set, from (d) of Theorem 3.1, (XT,ξT) is a tree-indexed Markov chain in discrete random environment if and only if

Letting m=n in (3.5), (3.4) follows. The proof of necessity is complete.

Next we prove sufficiency. Assume that (3.4) holds. For m ≤n,

and

Hence (3.5) holds in this case.

For m>n,

and

In this case, (3.5) also holds. Thus we complete the proof.

Corollary 3.2Let T be a local finite and infinite tree, and χ = {1,2,···} be a countable state space. Let {Xt,t ∈T} be a collection of random variables defined on probability space(?,F,P) taking values in χ. Then the following descriptions are equivalent:

(a) {Xt,t ∈T} is a tree-indexed nonhomogeneous Markov chain defined as in Definition 2.1.

(b) For any positive integer n, XTsatisfies (2.2) and

(c) For any positive integer n, and for any xT(n)∈χT(n), we have

ProofLet ξTtake a fixed point cT= {ct,t ∈T}, andpt(x,y),t ∈T. Since

and

Then (XT,ξT) is a tree-indexed Markov chain in random environment with initial distribution(c0;x) and transition matrices {Pt={(c1t;x,y)},t ∈T} if and only if XTis a tree-indexed Markov chain with the initial distribution p(x) and transition matrices {Pt= {pt(x,y)}}. By Theorem 3.1, this is equivalent to

and

This is also equivalent to (3.16) and

Since (3.12) holds,

and

This corollary follows.

ProofThe corollary is a special case of Theorem 3.1, where T is the set of nonnegative integers N.

In this following, we will show the existence of tree-indexed Markov chains in random environment on some probability space.

Let (χT,AT) and (ΘT,BT) be two measurable space. Define a function K(·,·),ΘT×AT→[0,1], satisfying (i). For any θT∈ΘT, K(θT,·) is a probability measure on AT. (ii). For any A ∈AT, K(·,A) is a measurable function about BT. We say that K(·,·) is a probability transition kernel from (ΘT,BT) to (χT,AT).

Lemma 3.1There exists a probability transition kernel K(·,·) from (ΘT,BT) to (χT,AT),satisfying

ProofBy Kolmorgrov existence theorem, it is easy to see that (3.23) can generate a probability measure on (χT,AT) denoted by K(θT,·). Meanwhile, it is easy to see that for any cylinder sets {XT(n)= xT(n)}, K(θT,XT(n)= xT(n)) is a measurable function on BT. Hence,for any A ∈AT, K(θT,A) is a measurable function on BTby monotone class theorem. Thus K(·,·) is a probability transition kernel from (ΘT,BT) to (χT,AT).

Theorem 3.2Let (χT× ΘT,AT× BT) be a measurable space. Let m be a probability measure on (ΘT,BT), and K(·,·) be a probability transition kernel from (ΘT,BT) to (χT,AT)defined as in Lemma 3.1. Define an orbital process on (χT× ΘT,AT× BT) as following:XT(xT,θT)= xT,ξT(xT,θT) = θT(?ω = (xT,θT) ∈χT×ΘT), i.e., (XT(ω),ξT(ω)) = ω. Set a probability measure μPon (χT×ΘT,AT×BT), satisfying

where C ∈AT×BT, and CθTis a section of C. Then (XT,ξT) is a tree-indexed Markov chain in random environment under the probability measure μP.

The proof of this theorem is provided in Section 5.

4 Some Strong Limit Theorems

In this section, we will present some strong limit theorems of tree-indexed Markov chains in random environment.

Lemma 4.1Let (XT,ξT) be a tree-indexed Markov chain in random environment defined as in Definition 2.3, and let f(θT;x,y) be a function such that for any (x,y) ∈χ2, f(·;x,y)is a Borel measurable functions on BT. Assume that, for any t ∈T{o}, the integral of f(ξT;X1t,Xt) exists. Then we have for any t ∈T{o},

where Fn=σ{ξT,XT(n)}.

ProofBy Definition 2.3, we have for any t ∈T{o},

where BT={Bt,t ∈T} and {Bt∈B}. From (4.2) and the general method of measure theory,(4.1) follows.

Theorem 4.1Let (XT,ξT) be a tree-indexed Markov chain in random environment as defined in Definition 2.3, and {gt(θT;x,y),t ∈T{o}} be a collection of ternary real-valued functions defined on ΘT×χ2such that for any x,y ∈χ,gt(·;x,y)are Borel measurable functions on BT. Let gt=gt(ξT;X1t,Xt). If there exists a constant b>0 such that

where M is a positive constant and Fn=σ{ξT,XT(n)}. Then

The proof of this theorem will be given in Section 5.

Corollary 4.1Let(XT,ξT)be a tree-indexed Markov chain in random environment defined as Definition 2.3. Let Sn(y) be the number of y in set of random variables {Xt,t ∈T(n)}, and Sn(x,y) be the number of (x,y) in the set of random couples {(X1t,Xt),t ∈T(n){o}}, i.e.,where δx(·)is Kronecker δ function.Then for arbitrary x,y ∈χ, we have

ProofFor any t ∈T{o},let gt(ξT;X1t,Xt)=δy(Xt)and gt(ξT;X1t,Xt)=δx(X1t)δy(Xt)be in Theorem 4.1, respectively. Obviously, gt(ξT;X1t,Xt) satisfies the conditions of Theorem 4.1. Noticing that

E[δy(Xt)|F|t|?1]=p(ξ1t;X1t,y) a.e.

and

E[δx(X1t)δy(Xt)|F|t|?1]=δx(X1t)p(ξ1t;X1t,y) a.e.,

thus (4.5) and (4.6) follow immediately by Theorem 4.1.

Let T be a local finite and infinite tree, XTand ξTbe two tree-indexed stochastic processes taking values in χ and Θ, respectively. Denote

Let

fn(ω) is called the conditional entropy density of XT(n). If (XT,ξT) is a tree-indexed Markov chain in random environment defined as Definition 2.3, by (c) of Theorem 3.1, we have

The entropy density is an important notion in information theory. Entropy density converging to a constant in a sense (L1convergence, convergence in probability, a.e. convergence) is called the Shannon-McMillan theorem,or the entropy theorem,or the asymptotic equipartition property(AEP for short)in information theory. Shannon [25] first proved the AEP for convergence in probability for stationary ergodic information sources with finite alphabet. McMillan[20] and Breiman [5] proved the AEP for stationary ergodic information sources with finite alphabet in L1and a.e. convergence, respectively, Chung [6] considered the case of countable alphabet. The AEP for general stochastic processes can be found, for example, in Barron [2]and Algoet and Cover [1]. Liu and Yang [19] proved the AEP for a class of nonhomogeneous Markov information sources. Yang and Liu[32]studied the AEP for mth-order nonhomogeneous Markov information source. Dang, Yang and Shi [11] studied the AEP for nonhomogeneous bifurcating Markov chains indexed by a binary tree with finite state space. Shi, Zhong and Fan[28] studied the AEP of tree-indexed Markov chain in Markovian environment on countable state space.

In the following, let χ = {1,2,··· ,N}, we will give the strong limit theorem of the conditional entropy density for tree-indexed Markov chains in random environments.

Theorem 4.2Let χ = {1,2,··· ,N}, and let (XT,ξT) be a tree-indexed Markov chain in random environment taking values in χ×Θ defined as in Definition 2.3, and fn(ω) be the conditional entropy density defined by (4.7). Then

By Lemma 4.1 and Theorem 4.1, noticing that

we have

By (4.7) and (4.10), (4.8) follows directly.

Remark 4.1If there is only one son for each vertex of the tree, the tree-indexed Markov chains in random environment will degenerate into Markov chains in single infinite random environment. Thus we can easily obtain the similar results of Markov chains in random environment(see [18, Theorem 3.1, Corollaries 3.2–3.3]).

5 The Proofs

In this section, we will prove Theorems 3.1–3.2 and 4.1.

Proof of Theorem 3.1(a)?(b). Suppose that(2.6)and (2.7)are true. We just need to prove (3.1) holds. We have by the tower principle of conditional expectation and Remark 2.3,

Thus, (3.1) follows.

(b)?(c). Assume that(2.6)and(3.1)hold, we only need to prove(3.2)holds. Using (2.6),(3.1) and the tower principle of conditional expectation, we have

It follows by (5.1) that (3.2) holds, thus the proof of (c) is completed.

(c) ?(d). Suppose that (2.6) and (3.2) are true, we need to prove (3.3) holds. For any positive integers m,n, since

where the last equality is established by integral transformation theorem (see [7, Theorem 3.2.2]), thus (d) follows.

(d) ?(a). Assume that (3.3) is true, we need to prove (2.6) and (2.7) hold. Firstly, we prove (2.6) holds. In order to prove (2.6), we only need to prove that for any positive integer m,

We have by (3.3) and integral transformation theorem,

thus (5.2) holds, so we complete the proof of (2.6). Next, we will prove (2.7). Without loss of generality, we assume that t ∈Ln. To prove (2.7), we just need to prove that for any positive integers m and l,

We discuss the following three situations: Case 1. If l < n, noticing that Tt∩T(l)= T(l), we have

Since

we have by (5.5),

Combining(5.4)and(5.6),we obtain(5.3)for l

On the other hand,

We have by (5.8),

By (5.7) and (5.9), we can easily get that (5.3) holds when l=n. Case 3. Let l>n. Since

On the other hand,

We have by (5.11),

By (5.10) and (5.12), we conclude that (5.3) holds when l>n. Thus we complete the proof of(5.3), and (2.7) holds.

Proof of Theorem 3.2To prove that(XT,ξT)is a tree-indexed Markov chain in random environment under the probability measureμP, according to(b) of Theorem 3.1, it is sufficient to prove the following two equations,

Let m be an arbitrary positive integer, and Bt∈B for any t ∈T. Since

where the second equation and the third equation are obtained by (3.2)and (3.1), respectively.Hence (5.13) is proved by (5.15). By (3.23)–(3.24), we see that for any positive integer m,

Similarly, we have

We have by (5.17),

By (5.16) and (5.18), (5.14) holds. Thus we complete the proof of this theorem.

Proof of Theorem 4.1Given a constant r (|r|≤b). Let M0(r)=1 and

Since

By (3.1) and Lemma 4.1, we have

By (5.20)–(5.21), we have E[Mn(r) | Fn?1] = Mn?1(r) for n ≥1. Noticing that E[Mn(r)] =E[Mn?1(r)] = ··· = E[M0(r)] = 1. So {Mn(r),Fn,n ≥0} is a nonnegative martingale. By the Doob martingale convergence theorem, Mn(r) a.e. converges to a finite nonnegative r.v.M∞(r) when |r|

which implies

We have by (5.19) and (5.22) that,

Let 0

we have

By (4.3) and (5.24), for 0

Letting r →0+in (5.25), we get

If ?b

Combining (5.26) and (5.27), we obtain

Thus we complete the proof of Theorem 4.1.

AcknowledgementsThe authors sincerely thank the editors and reviewers for their helpful and important comments, especially during the time with COVID19 pandemic.