# Strong Law of Large Numbers of the Offspring Empirical Measure for Markov Chains Indexed by Homogeneous Tree

Authors: Huilin Huang
Journal: ISRN Applied Mathematics
 (2012)

---

## Abstract

We study the limit law of the offspring empirical measure and for Markov chains indexed by homogeneous tree with almost everywhere convergence. Then we prove a Shannon-McMillan theorem with the convergence almost everywhere.


---

## Body

## 1. Introduction

A tree is a graphG={T,E} which is connected and contains no circuits, where T and E denote the vertex set and the edge set, respectively. Given any two vertices α≠β∈T, let αβ¯ be the unique path connecting α and β. Define the graph distance d(α,β) to be the number of edges contained in the path αβ¯.LetG be an infinite tree with root 0. The set of all vertices with distance n from the root is called the nth generation of T, which is denoted by Ln. We denote by T(n) the union of the first n generations of T. For each vertex t, there is a unique path from 0 to t, and |t| for the number of edges on this path. We denote the first predecessor of t by 1t, the second predecessor of t by 2t and denote by nt the nth predecessor of t. The degree of a vertex is defined to be the number of neighbors of it. If the degree sequence of a tree is uniformly bounded, we call the tree a uniformly bounded tree. Let d be a positive integer. If every vertex of the tree has d neighbors in the next generation, we say it Cayley tree, which is denoted by TC,d. Thus on Cayley tree, every vertex has degree d+1 except that the root index which has degree d. For any two vertices s and t of tree T, write s≤t if s is on the unique path from the root 0 to t. We denote by s∧t the vertex farthest from 0 satisfying s∧t≤s and s∧t≤t. XA={Xt,t∈A} and denote by |A| the number of vertices of A.Definition 1.1 (see [1]).
LetG be an infinite Cayley tree TC,d,S a finite state space, and {Xt,t∈T} be a collection of S-valued random variables defined on probability space (Ω,ℱ,P). Let
(1.1)p={p(x),x∈S}
be a distribution on S and
(1.2)P=(P(y∣x)),x,y∈S,
be a stochastic matrix on S2. If for any vertex t,
(1.3)P(Xt=y∣X1t=xandXsfort∧s≤1t)=P(Xt=y∣X1t=x)=P(y∣x)∀x,y∈S,P(X0=x)=p(x)∀x∈S,{Xt, t∈T} will be called S-valued Markov  chains  indexed  by  an  infinite  treeG with the initial distribution (1.1) and transition matrix (1.2) or called tree-indexed Markov chains with state-space S. Furthermore, if transition matrix P is ergodic, then we call {Xt,t∈T} an ergodic  Markov  chains indexed by the infinite tree T.The above definition is the extension of the definitions of Markov chain fields on trees (see [1, page 456] and [2]). In this paper, we always suppose that the tree-indexed Markov chain is ergodic.The subject of tree-indexed processes is rather young. 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 [4] have studied the existence of entropy rate for some stationary random fields on a homogeneous tree. Ye and Berger (see [5, 6]), by using Pemantle’s result [7] 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 [8] have studied a strong law of large numbers for the frequency of occurrence of states for Markov chains fields on a homogeneous tree (a particular case of tree-indexed Markov chains and PPG-invariant random fields). Takacs (see [9]) have studied the strong law of large numbers for the univariate functions of finite Markov chains indexed by an infinite tree with uniformly bounded degree. Subsequently, Huang and Yang (see [10]) has studied the Shannon-McMillan theorem of finite homogeneous Markov chains indexed by a uniformly bounded infinite tree. Dembo et al., (see [11]) has showed the large deviation principle holds for the empirical offspring measure of Markov chains on random trees and demonstrated the explicit rate function, which is defined in terms of specific relative entropy (see [12]) and Cramér’s rate function.In this paper, we study the strong law of large numbers for the offspring empirical measure and the Shannon-McMillan theorem with a.e. convergence for Markov chain fields on treeTC,d by using a method similar to that of [10].


## 2. Statements of the Results

For every vertext∈T, the random vector of offspring states is defined as(2.1)Ct=(X1(t),X2(t),…,Xd(t))∈Sd.Letc=(c1,c2,…,cd) be a d-dimensional vector on Sd.Now we also let the distribution (1.1) serve as the initial distribution. Define the offspring transition kernel Q from S to Sd. We define the law P of a tree-indexed process X by the following rules.(i)
The state of the root random variableX0 is determined by distribution (1.1).(ii)
For every vertext∈T with state x, the offspring states are given independently of everything else, by the offspring law Q(·∣x) on Sd, where(2.2)Q(c∣x)∶=Q(Ct=(c1,c2,…,cd)∣Xt=x)=∏i=1dP(ci∣x).
Here the last equation holds because of the property of conditional independence.For every finiten∈N, let {Xt,t∈T} be S-valued Markov chains indexed by an infinite tree T. Now we define the offspring empirical measure
(2.3)Ln(x,c)=∑t∈T(n)I{(Xt,Ct)=(x,c)}|T(n)|∀(x,c)∈S×Sd.
For any state x∈S, Sn(x) is the empirical measure, which is defined as follows:(2.4)Sn(x)=∑t∈T(n)I{Xt=x}|T(n)|∀x∈S,
where I{·} denotes the indicator function as usual and c=(c1,c2,…,cd).In the rest of this paper, we consider the limit law of the random sequence of{Ln(x,c),n≥1}, which is defined as above.Theorem 2.1.
LetG be a Cayley tree TC,d, S a finite state space,  and {Xt,t∈T} be tree-indexed Markov chain with initial distribution (1.1) and ergodic transition matrix P.  Let Ln(x,c) be defined as (2.3).  Thus one has
(2.5)lim⁡n→∞Ln(x,c)=π(x)Q(c∣x)a.e.,
where π is the stationary distribution of the ergodic matrix P, that is, π=πP, and Σx∈Sπ(x)=1.Corollary 2.2.
Under the condition of Theorem2.1,  suppose that f(x,c) is any function defined on S×Sd.  Denote
(2.6)Hn(ω)=∑t∈T(n)f(Xt,Ct).
Then
(2.7)lim⁡n→∞Hn(ω)|T(n)|=∑(x,c)∈S×Sdπ(x)Q(c∣x)f(x,c).a.e.Proof.
Noting that(2.8)Hn(ω)=∑t∈T(n)f(Xt,Ct)=∑(x,c)∈S×Sd∑t∈T(n)I{(Xt,Ct)=(x,c)}f(x,c),
thus by using Theorem 2.1 we get
(2.9)lim⁡n→∞Hn(ω)|T(n)|=∑(x,c)∈S×Sdf(x,c)lim⁡n→∞Ln(x,c)=∑(x,c)∈S×Sdπ(x)Q(c∣x)f(x,c).a.e.
LetG={T,E} be a tree graph, (Xt)t∈T be a stochastic process indexed by tree G with state space S. Denote Yt=(Xt,Ct) to be the offspring processes derived by (Xt)t∈T. It is easy to see that(2.10)P(yT(n))=P(YT(n)=yT(n))=p(x0)∏t∈T(n+1)∖{0}P(xt∣x1t)=p(x0)∏t∈T(n)Q(ct∣xt),
where ct∈Sd. Let
(2.11)fn(ω)=-1|T(n)|ln⁡P(YT(n)).fn(ω) will be called the entropy density of YT(n). If (Xt)t∈T is a tree-indexed Markov chain with state space S defined by Definition 1.1, we have by (2.10)
(2.12)fn(ω)=-1|T(n)|[ln⁡p(X0)+∑t∈T(n)ln⁡Q(Ct∣Xt)].
The convergence offn(ω) to a constant in a sense (L1 convergence, convergence in probability, a.e. convergence) is called the Shannon-McMillan theorem or the entropy theorem or the AEP in information theory. Here from Corollary 2.2, if we let(2.13)f(x,c)=-ln⁡Q(c∣x),
we can easily obtain the Shannon-McMillan theorem with a.e. convergence for Markov chain fields on tree TC,d.Corollary 2.3.
Under the condition of Corollary2.2, let fn(ω) be defined as (2.12). Then
(2.14)lim⁡n→∞fn(ω)=-∑(x,c)∈S×Sdπ(x)Q(c∣x)ln⁡Q(c∣x).a.e.


## 3. Proof of Theorem2.1

LetTC,d be a Cayley tree, S a finite state space, and {Xt,t∈T} tree-indexed Markov chain with any initial distribution (1.1) and ergodic transition matrix P. Let gt(Xt,Ct) be functions defined on S×Sd. Letting λ be a real number, L0={0}, ℱn=σ(XT(n)), now we can define a nonnegative martingale as follows:
(3.1)tn(λ,ω)=eλ∑t∈T(n-1)gt(Xt,Ct)∏t∈T(n-1)E[eλgt(Xt,Ct)∣Xt].
At first we come to prove the above fact.Theorem 3.1.
{tn(λ,ω), ℱn, n≥1} is a nonnegative martingale.Proof of Theorem3.1.
Note that, by Markov property and the property of conditional independence, we have(3.2)E[eλ∑t∈Lngt(Xt,Ct)∣Fn]=∑xLn+1eλ∑t∈Lngt(Xt,ct)P(XLn+1=xLn+1∣XT(n))=∑xLn+1∏t∈Lneλgt(Xt,ct)Q(ct∣Xt)=∏t∈Ln∑ct∈Sdeλgt(Xt,ct)Q(ct∣Xt)=∏t∈LnE[eλgt(Xt,Ct)∣Xt]a.e.
On the other hand, we also have
(3.3)tn+1(λ,ω)=tn(λ,ω)eλ∑t∈Lngt(Xt,Ct)∏t∈LnE[eλgt(Xt,Ct)∣Xt].
Combining (3.2) and (3.3), we get
(3.4)E[tn+1(λ,ω)∣Fn]=tn(λ,ω)a.e.
Thus we complete the proof of this theorem.Theorem 3.2.
Let(Xt)t∈T and {gt(x,c),t∈T} be defined as above, and denote
(3.5)Gn(ω)=∑t∈T(n)E[gt(Xt,Ct)∣Xt].
Let α>0, denote
(3.6)D(α)={limsup⁡n→∞1|T(n)|∑t∈T(n)E[gt2(Xt,Ct)eα|gt(Xt,Ct)|∣Xt]=M(ω)<∞},(3.7)Hn(ω)=∑t∈T(n)gt(Xt,Ct).
Then
(3.8)lim⁡n→∞Hn(ω)-Gn(ω)|T(n)|=0a.e.on⁡D(α).Proof.
By Theorem3.1, we have known that {tn(λ,ω),ℱn,n≥1} is a nonnegative martingale. According to Doob martingale convergence theorem, we have
(3.9)lim⁡ntn(λ,ω)=t(λ,ω)<∞a.e.
so that
(3.10)limsup⁡n→∞ln⁡tn+1(λ,ω)|T(n)|≤0a.e.
Combining (3.1), (3.7), and (3.10), we arrive at
(3.11)limsup⁡n→∞1|T(n)|{λHn(ω)-∑t∈T(n)ln⁡[E[eλgt(Xt,Ct)∣Xt]]}≤0a.e.
Let λ>0. Dividing two sides of above equation by λ, we get
(3.12)limsup⁡n→∞1|T(n)|{Hn(ω)-∑t∈T(n)ln⁡[E[eλgt(Xt,Ct)∣Xt]]λ}≤0a.e.
By (3.12) and inequalities lnx≤x-1(x>0),0≤ex-1-x≤2-1x2e|x|, as 0<λ≤α, it follows that
(3.13)limsup⁡n→∞1|T(n)|[Hn(ω)-∑t∈T(n)E[gt(Xt,Ct)∣Xt]]≤limsup⁡n→∞1|T(n)|∑t∈T(n){ln⁡[E[eλgt(Xt,Ct)∣Xt]]λ-E[gt(Xt,Ct)∣Xt]}≤limsup⁡n→∞1|T(n)|∑t∈T(n){E[eλgt(Xt,Ct)∣Xt]-1λ-E[gt(Xt,Ct)∣Xt]}≤λ2limsup⁡n→∞1|T(n)|∑t∈T(n)E[gt2(Xt,Ct)eλ|gt(Xt,Ct)|∣Xt]≤λ2limsup⁡n→∞1|T(n)|∑t∈T(n)E[gt2(Xt,Ct)eα|gt(Xt,Ct)|∣Xt]≤λ2M(ω)a.e.ω∈D(α).
Letting λ→0+ in (3.13), by (3.5) we have
(3.14)limsup⁡n→∞Hn(ω)-Gn(ω)|T(n)|≤0a.e.ω∈D(α).
Let -α≤λ<0. Similarly to the analysis of the case 0<λ≤α, it follows from (3.12) that
(3.15)liminf⁡n→∞Hn(ω)-Gn(ω)|T(n)|≥λ2M(ω)a.e.ω∈D(α).
Letting λ→0-, we can arrive at
(3.16)liminf⁡n→∞Hn(ω)-Gn(ω)|T(n)|≥0a.e.ω∈D(α).
Combining (3.14) and (3.16), we obtain (3.8) directly.Corollary 3.3.
Under the conditions of Theorem3.2, one has
(3.17)lim⁡n→∞[Ln(x,c)-Sn(x)Q(c∣x)]=0a.e.,
where π is the stationary distribution of the ergodic matrix P, that is, π=πP, and Σx∈Sπ(x)=1.Proof.
For anyt∈T, let
(3.18)gt(Xt,Ct)=I{(Xt,Ct)=(x,c)}=I{Xt=x}⋅I{Ct=c}.
Then we have
(3.19)Gn(ω)=∑t∈T(n)E[gt(Xt,Ct)∣Xt]=∑t∈T(n)∑ct∈SdI{Xt=x}⋅I{ct=c}Q(ct∣Xt)=∑t∈T(n)I{Xt=x}Q(c∣x)=|T(n)|⋅Sn(x)Q(c∣x)(3.20)Hn(ω)=∑t∈T(n)gt(Xt,Ct)=∑t∈T(n)I{(Xt,Ct)=(x,c)}=|T(n)|⋅Ln(x,c).
Combing (3.19) and (3.20), we can derive our conclusion by Theorem 3.2.
In our proof, we will use Lemma3.4.Lemma 3.4 (see [10]).
LetTC,d be a Cayley tree, S a finite state space, and {Xt, t∈T} tree-indexed Markov chain with any initial distribution (1.1) and ergodic transition matrix P. Let Sn(x) be defined as (2.4). Thus one has(3.21)lim⁡n→∞Sn(x)=π(x)a.e.Proof of Theorem2.1.
Combining Corollary3.3 and Lemma 3.4, we arrive at our conclusion directly.



---

*Source: 536530-2012-04-03.xml*