# Strong Law of Large Numbers for Hidden Markov Chains Indexed by Cayley Trees

Authors: Huilin Huang
Journal: ISRN Probability and Statistics
 (2012)

---

## Abstract

We extend the idea of hidden Markov chains on lines to the situation of hidden Markov chains indexed by Cayley trees. Then, we study the strong law of large numbers for hidden Markov chains indexed by Cayley trees. As a corollary, we get the strong limit law of the conditional sample entropy rate.


---

## Body

## 1. Introduction

Recently, interest in the theory of hidden Markov models (abbreviated HMM hereafter) has become widespread especially in areas such as speech recognition [1], image processing [2], DNA sequence analysis [3, 4], DNA microarray time-course analysis [5], and econometrics [6, 7]. For a good review of statistical and information-theoretic aspects of hidden Markov processes (HMPs); please see Ephraim and Merhav [8]. In recent years, the work of Baum and Petrie [9] on finite-state finite-alphabet HMMs has been expanded to HMM with finite as well as continuous state spaces and a general alphabet. In particular, statistical properties and ergodic theorems for relative entropy densities of HMMs were developed, and consistency and asymptotic normality of the maximum-likelihood (ML) parameter estimator were proved under some mild conditions [9–12].In this paper, we extend hidden Markov chain to hidden Markov chain indexed by Cayley trees, then we mainly prove the strong law of large numbers of offspring empirical measure for hidden Markov chain indexed by Cayley trees.


### 1.1.  Notations and Preliminaries

A treeT is a graph which is connected and contains no loops. 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 αβ¯.LetT 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 degree of a vertex is defined to be the number of neighbors of it. If every vertex of the tree has d neighbors in the next generation, we call it Cayley tree, which is denoted by TC,d. Thus on Cayley tree TC,d, every vertex has degree d+1 except that the root vertex has degree d. For any two vertices s and t of tree T, write s≤t if s is on the unique path connecting the root 0 to t. For any two vertices s and 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.In the following, we always letT denote the Cayley tree TC,d.Definition 1.1 (T-indexed homogeneous Markov chains (see [13, 14])).
LetT be an infinite Cayley tree and {Xt,t∈T} a stochastic process defined on probability space (Ω,ℱ,P) and with finite state space 𝒳. Let(1.1)p={p(i),i∈𝒳}
be a distribution on 𝒳, and
(1.2)A=(a(j∣i)),i,j∈𝒳
a transition probability matrix on 𝒳2. If for vertex t∈T, we have
(1.3)P(Xt=j∣Xt1=i,Xs=xs∀ssatisfyingt∧s≤1t)=P(Xt=j∣Xt1=i)=a(j∣i)∀i,j∈𝒳,(1.4)P(X0=i)=p(i)∀i∈𝒳,
then we call {Xt,t∈T} to be an 𝒳-valued homogeneous Markov chain indexed by infinite Cayley tree with the initial distribution (1.1) and transition probability matrix A whose elements are determined by (1.3).Definition 1.2.
LetT be an infinite Cayley tree and 𝒳 and 𝒴 two finite state spaces. {Xt,Yt,t∈T} is a stochastic process on a probability space (Ω,ℱ,P). Let A=(a(j∣i)) and B=(b(y∣i))i∈𝒳,y∈𝒴 be two stochastic matrices on 𝒳2 and 𝒳×𝒴, respectively. Suppose
(1.5)P(X0=i)=p(i)∀i∈𝒳,P(Y0=y0∣X0=x0)=b(y0∣x0).
If for vertex t∈T, we have
(1.6)P(Yt=yt,Xt=xt∣Yt1=yt1,Xt1=xt1,Ys=ys,Xs=xs,∀ssatisfyingt∧s≤1t)=P(Yt=yt,Xt=xt∣Xt1=xt1).
Moreover, we suppose that
(1.7)P(Yt=yt,Xt=xt∣Xt1=xt1)=P(Yt=yt∣Xt=xt)P(Xt=xt∣Xt1=xt1)=b(yt∣xt)a(xt∣xt1)
then {Xt,Yt,t∈T} will be called an 𝒳×𝒴-valued hidden Markov chain indexed by an infinite treeT or calledtree-indexed hidden Markov chaintaking values in the finite set 𝒳×𝒴.Remark 1.3.
(i) If we sum overyt in (1.6), we can get, for any t∈T,
(1.8)∑yt∈𝒴‍P(Yt=yt,Xt=xt∣Yt1=yt1,Xt1=xt1,Ys=ys,Xs=xs,∀ssatisfyingt∧s≤1t)=∑yt∈𝒴‍P(Yt=yt,Xt=xt∣Xt1=xt1)=P(Xt=xt∣Xt1=xt1).
After taking conditional expectations with respect to {Xt1,Xs,t∧s≤t1} on both sides of above equation, we arrive at (1.3). Therefore, {Xt,Yt,t∈T} is a tree-indexed Markov chain.
In Definition1.2, we also call the processes {Xt,t∈T} and {Yt,t∈T} to be state process and theobserved process, respectively, indexed by an infinite tree.
(ii) Obviously, by (1.6), the process Zt=(Xt,Yt) is atree-indexed Markov chainwith state-space 𝒳×𝒴.Property 1.
Suppose that{Xt,Yt,t∈T} is a hidden Markov chain indexed by an infinite tree  T which take values in 𝒳×𝒴, then we have
(1.9)P(YT(n)=yT(n))=∑xT(n)‍p(x0)b(y0∣x0)∏t∈T(n)∖{0}‍b(yt∣xt)a(xt∣xt1).Proof.
Since{Zt=(Xt,Yt),t∈T} is a tree-indexed Markov chain, it is easy to see (1.10)P(YT(n)=yT(n),XT(n)=xT(n))=p(x0)P(Y0=y0∣X0=x0)∏t∈T(n)∖{0}‍P(Yt=yt,Xt=xt∣Xt1=xt1)(1.11)=p(x0)P(Y0=y0∣X0=x0)∏t∈T(n)∖{0}‍P(Xt=xt∣Xt1=xt1)P(Yt=yt∣Xt=xt)=p(x0)b(y0∣x0)∏t∈T(n)∖{0}‍b(yt∣xt)a(xt∣xt1).
On the other hand, we have
(1.12)P(YT(n)=yT(n))=∑xT(n)‍P(YT(n)=yT(n),XT(n)=xT(n)).
The conclusion (1.9) is directly derived from (1.11) and (1.12).


## 1.1.  Notations and Preliminaries

A treeT is a graph which is connected and contains no loops. 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 αβ¯.LetT 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 degree of a vertex is defined to be the number of neighbors of it. If every vertex of the tree has d neighbors in the next generation, we call it Cayley tree, which is denoted by TC,d. Thus on Cayley tree TC,d, every vertex has degree d+1 except that the root vertex has degree d. For any two vertices s and t of tree T, write s≤t if s is on the unique path connecting the root 0 to t. For any two vertices s and 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.In the following, we always letT denote the Cayley tree TC,d.Definition 1.1 (T-indexed homogeneous Markov chains (see [13, 14])).
LetT be an infinite Cayley tree and {Xt,t∈T} a stochastic process defined on probability space (Ω,ℱ,P) and with finite state space 𝒳. Let(1.1)p={p(i),i∈𝒳}
be a distribution on 𝒳, and
(1.2)A=(a(j∣i)),i,j∈𝒳
a transition probability matrix on 𝒳2. If for vertex t∈T, we have
(1.3)P(Xt=j∣Xt1=i,Xs=xs∀ssatisfyingt∧s≤1t)=P(Xt=j∣Xt1=i)=a(j∣i)∀i,j∈𝒳,(1.4)P(X0=i)=p(i)∀i∈𝒳,
then we call {Xt,t∈T} to be an 𝒳-valued homogeneous Markov chain indexed by infinite Cayley tree with the initial distribution (1.1) and transition probability matrix A whose elements are determined by (1.3).Definition 1.2.
LetT be an infinite Cayley tree and 𝒳 and 𝒴 two finite state spaces. {Xt,Yt,t∈T} is a stochastic process on a probability space (Ω,ℱ,P). Let A=(a(j∣i)) and B=(b(y∣i))i∈𝒳,y∈𝒴 be two stochastic matrices on 𝒳2 and 𝒳×𝒴, respectively. Suppose
(1.5)P(X0=i)=p(i)∀i∈𝒳,P(Y0=y0∣X0=x0)=b(y0∣x0).
If for vertex t∈T, we have
(1.6)P(Yt=yt,Xt=xt∣Yt1=yt1,Xt1=xt1,Ys=ys,Xs=xs,∀ssatisfyingt∧s≤1t)=P(Yt=yt,Xt=xt∣Xt1=xt1).
Moreover, we suppose that
(1.7)P(Yt=yt,Xt=xt∣Xt1=xt1)=P(Yt=yt∣Xt=xt)P(Xt=xt∣Xt1=xt1)=b(yt∣xt)a(xt∣xt1)
then {Xt,Yt,t∈T} will be called an 𝒳×𝒴-valued hidden Markov chain indexed by an infinite treeT or calledtree-indexed hidden Markov chaintaking values in the finite set 𝒳×𝒴.Remark 1.3.
(i) If we sum overyt in (1.6), we can get, for any t∈T,
(1.8)∑yt∈𝒴‍P(Yt=yt,Xt=xt∣Yt1=yt1,Xt1=xt1,Ys=ys,Xs=xs,∀ssatisfyingt∧s≤1t)=∑yt∈𝒴‍P(Yt=yt,Xt=xt∣Xt1=xt1)=P(Xt=xt∣Xt1=xt1).
After taking conditional expectations with respect to {Xt1,Xs,t∧s≤t1} on both sides of above equation, we arrive at (1.3). Therefore, {Xt,Yt,t∈T} is a tree-indexed Markov chain.
In Definition1.2, we also call the processes {Xt,t∈T} and {Yt,t∈T} to be state process and theobserved process, respectively, indexed by an infinite tree.
(ii) Obviously, by (1.6), the process Zt=(Xt,Yt) is atree-indexed Markov chainwith state-space 𝒳×𝒴.Property 1.
Suppose that{Xt,Yt,t∈T} is a hidden Markov chain indexed by an infinite tree  T which take values in 𝒳×𝒴, then we have
(1.9)P(YT(n)=yT(n))=∑xT(n)‍p(x0)b(y0∣x0)∏t∈T(n)∖{0}‍b(yt∣xt)a(xt∣xt1).Proof.
Since{Zt=(Xt,Yt),t∈T} is a tree-indexed Markov chain, it is easy to see (1.10)P(YT(n)=yT(n),XT(n)=xT(n))=p(x0)P(Y0=y0∣X0=x0)∏t∈T(n)∖{0}‍P(Yt=yt,Xt=xt∣Xt1=xt1)(1.11)=p(x0)P(Y0=y0∣X0=x0)∏t∈T(n)∖{0}‍P(Xt=xt∣Xt1=xt1)P(Yt=yt∣Xt=xt)=p(x0)b(y0∣x0)∏t∈T(n)∖{0}‍b(yt∣xt)a(xt∣xt1).
On the other hand, we have
(1.12)P(YT(n)=yT(n))=∑xT(n)‍P(YT(n)=yT(n),XT(n)=xT(n)).
The conclusion (1.9) is directly derived from (1.11) and (1.12).


## 2. Strong Law of Large Numbers

Let{Xt,Yt,t∈T} be 𝒳×𝒴-valued hidden Markov chains indexed by an infinite Cayley tree T. For every finite n∈N, we define the offspring empirical measure as follows:
(2.1)Sn(x,y)=∑t∈T(n)‍δx(Xt)δy(Yt)|T(n)|∀(x,y)∈𝒳×𝒴,
here and thereafter δx(·) denotes the Kronecker function. In the rest of this paper, we consider the limit law of the random sequence of Sn(x,y) which are defined as above.Theorem 2.1.
LetT be a Cayley tree and let {Xt,Yt,t∈T} be 𝒳×𝒴-valued hidden Markov chains indexed by T. If the transition probability matrix A of {Xt,t∈T} is ergodic, then
(2.2)limn→∞Sn(x,y)=π(x)b(y∣x)a.e.,
where and thereafter π is the stationary distribution of the ergodic matrix A; that is, π=πA, and Σx∈𝒳π(x)=1.We postpone the proof of Theorem2.1 to Section 3.From the expression of (2.1), we can easily obtain the empirical measure of the observed chain {Yt,t∈T} which is denoted by Mn(·)(2.3)Mn(y)=∑x∈𝒳‍Sn(x,y)=∑t∈T(n)‍δy(Yt)|T(n)|∀y∈𝒴.
Thus, we can obtain the following Corollary 2.2.Corollary 2.2.
Under the same conditions of Theorem2.1, one has
(2.4)limn→∞Mn(y)=∑x∈𝒳‍π(x)b(y∣x)a.e.Letf(x,y) be any function defined on 𝒳×𝒴. Denote
(2.5)Gn(ω)=∑t∈T(n)‍f(Xt,Yt).
By simple computation, we arrive at the following Corollary 2.3.Corollary 2.3.
Under the same conditions of Theorem2.1, one also has
(2.6)limn→∞Gn(ω)|T(n)|=∑(x,y)∈𝒳×𝒴‍π(x)b(y∣x)f(x,y)a.e.Now, we define the conditional entropy rate ofYT(n) given XT(n) as follows
(2.7)fn(ω)=-1|T(n)|lnP(YT(n)∣XT(n)).
From (1.6), we obtain that
(2.8)fn(ω)=-∑t∈T(n)‍lnP(Yt∣Xt)|T(n)|.The convergence offn(ω) to a constant in a sense (L1 convergence, convergence in probability, a.e. convergence) is called the conditional version ofShannon-McMillan theoremor the entropy theorem or the AEP in information theory. Here from Corollary 2.3, if we let
(2.9)f(Xt,Yt)=-lnP(Yt∣Xt),
we can easily obtain the Shannon-McMillan theorem with a.e. convergence for conditional sample entropy rate of hidden Markov chain fields on Cayley tree T.Corollary 2.4.
Under the same conditions of Theorem2.1, one has
(2.10)limn→∞fn(ω)=-∑y∈𝒴‍∑x∈𝒳‍π(x)b(y∣x)lnb(y∣x)a.e.


## 3. Proof of Theorem2.1

LetT be a Cayley tree and let {Xt,Yt,t∈T} be 𝒳×𝒴-valued hidden Markov chains indexed by T. Let gt(i,j,y) be functions defined on 𝒳×𝒳×𝒴. Let λ be a real number, L0={0}, ℱn=σ(XT(n),YT(n)), now we define a stochastic sequence as follows:
(3.1)tn(λ,ω)=eλ∑t∈T(n)∖{0}‍gt(Xt1,Xt,Yt)∏t∈T(n)∖{0}E[eλgt(Xt1,Xt,Yt)∣Xt1].
At first, we come to prove the following fact.Lemma 3.1.
The{tn(λ,ω),ℱn,n≥1} is a nonnegative martingale.Proof of Lemma3.1.
Obviously, we have(3.2)P(XLn=xLn,YLn=yLn∣XT(n-1)=xT(n-1),YT(n-1)=yT(n-1))=P(XT(n)=xT(n),YT(n)=yT(n))P(XT(n-1)=xT(n-1),YT(n-1)=yT(n-1))=∏t∈Ln‍P(Xt=xt,Yt=yt∣Xt1=xt1),
here the second equation holds because of (1.10). Furthermore, we have
(3.3)E[eλ∑t∈Ln‍gt(Xt1,Xt,Yt)∣ℱn-1]=∑xLn,yLn‍eλ∑t∈Ln‍gt(xt1,xt,yt)P(XLn=xLn,YLn=yLn∣XT(n-1),YT(n-1))=∑xLn,yLn‍∏t∈Ln‍eλgt(Xt1,xt,yt)P(Xt=xt,Yt=yt∣Xt1)=∏t∈Ln‍∑(xt,yt)∈𝒳×𝒴‍eλgt(Xt1,xt,yt)P(Xt=xt,Yt=yt∣Xt1)=∏t∈Ln‍E[eλgt(Xt1,Xt,Yt)∣Xt1]a.e.
On the other hand, we also have
(3.4)tn(λ,ω)=tn-1(λ,ω)eλ∑t∈Ln‍gt(Xt1,Xt,Yt)∏t∈Ln‍E[eλgt(Xt1,Xt,Yt)∣Xt1].
Combining (3.3) and (3.4), we get
(3.5)E[tn(λ,ω)∣ℱn-1]=tn-1(λ,ω)a.e.
Thus, we complete the proof of Lemma 3.1.Lemma 3.2.
Let{Xt,Yt,t∈T} be 𝒳×𝒴-valued hidden Markov chains indexed by an infinite Cayley tree T. {gt(i,j,y),t∈T} are functions defined as above, denote
(3.6)Rn(ω)=∑t∈T(n)∖{0}‍E[gt(Xt1,Xt,Yt)∣Xt1].
Let α>0, denote
(3.7)D(α)={limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍E[gt2(Xt1,Xt,Yt)eα|gt(Xt1,Xt,Yt)|∣Xt1]=M(ω)<∞},(3.8)Hn(ω)=∑t∈T(n)∖{0}‍gt(Xt1,Xt,Yt).
Then,
(3.9)limn→∞Hn(ω)-Rn(ω)|T(n)|=0a.e.onD(α).Proof.
By Lemma3.1, we have known that {tn(λ,ω),ℱn,n≥1} is a nonnegative martingale. According to Doob’s martingale convergence theorem, we have
(3.10)limntn(λ,ω)=t(λ,ω)<∞a.e.,
so that
(3.11)limsupn→∞lntn(λ,ω)|T(n)|≤0a.e.
Combining (3.1), (3.8), and (3.11), we arrive at
(3.12)limsupn→∞1|T(n)|{λHn(ω)-∑t∈T(n)∖{0}‍ln[E[eλgt(Xt1,Xt,Yt)∣Xt1]]}≤0a.e.
Let λ>0. Dividing two sides of the above equation by λ, we get
(3.13)limsupn→∞1|T(n)|{Hn(ω)-∑t∈T(n)∖{0}‍ln[E[eλgt(Xt1,Xt,Yt)∣Xt1]]λ}≤0a.e.
For case 0<λ≤α, combining with (3.13), the inequalities lnx≤x-1(x>0) and 0≤ex-1-x≤2-1x2e|x|, then it follows that
(3.14)limsupn→∞1|T(n)|[Hn(ω)-∑t∈T(n)∖{0}‍E[gt(Xt1,Xt,Y)∣Xt1]]≤limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍{ln[E[eλgt(Xt1,Xt,Yt)∣Xt1]]λ-E[gt(Xt1,Xt,Yt)∣Xt1]}≤limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍{E[eλgt(Xt1,Xt,Yt)∣Xt1]-1λ-E[gt(Xt1,Xt,Yt)∣Xt1]}≤λ2limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍E[gt2(Xt1,Xt,Yt)eλ|gt(Xt1,Xt,Yt)|∣Xt1]≤λ2limsupn→∞1|T(n)|∑t∈T(n)∖{0}‍E[gt2(Xt1,Xt,Yt)eα|gt(Xt1,Xt,Yt)|∣Xt1]≤λ2M(ω)a.e.ω∈D(α).
Letting λ→0+ in (3.14), combining with (3.6), we have
(3.15)limsupn→∞Hn(ω)-Rn(ω)|T(n)|≤0a.e.ω∈D(α).
Let -α≤λ<0. Similar to the analysis of the case 0<λ≤α it follows from (3.13) that
(3.16)liminfn→∞Hn(ω)-Rn(ω)|T(n)|≥λ2M(ω)a.e.ω∈D(α).
Letting λ→0-, we can arrive at
(3.17)liminfn→∞Hn(ω)-Rn(ω)|T(n)|≥0a.e.ω∈D(α).
Combining (3.15) and (3.17), we obtain (3.9) directly.Now we define the empirical measures of the Markov chain{Xt,t∈T} indexed by Cayley tree T as Sn(x):(3.18)Sn(x)=∑t∈T(n)‍δx(Xt)|T(n)|∀x∈𝒳.The following lemma is very useful for proving our main result.Lemma 3.3 (see [14]).
LetT be a Cayley tree and {Xt,t∈T} a tree-indexed Markov chain with finite state space 𝒳, which is determined by any initial distribution (1.1) and finite transition probability matrix A. Suppose that the stochastic matrix A is ergodic, whose unique stationary distribution is π; that is, πA=π and ∑x∈𝒳‍π(x)=1. Let Sn(x) be defined as (3.18). Thus, we have
(3.19)limn→∞Sn(x)=π(x)a.e.Corollary 3.4.
LetT be a Cayley tree and let {Xt,Yt,t∈T} be 𝒳×𝒴-valued hidden Markov chains indexed by T. Define the following empirical measure of triples (Xt1,Xt,Yt):
(3.20)Mn(x~,x,y)=∑t∈T(n)∖{0}‍δx~(Xt1)δx(Xt)δy(Yt)|T(n)|∀(x~,x,y)∈𝒳×𝒳×𝒴.
If the transition probability matrix A of {Xt,t∈T} is ergodic, we have
(3.21)limn→∞[Mn(x~,x,y)-π(x~)b(y∣x)a(x∣x~)]=0a.e.,
where π is the stationary distribution of the ergodic matrix A.Proof.
For anyt∈T, let
(3.22)gt(i,j,k)=δx~(i)δx(j)δy(k),
then we have
(3.23)Rn(ω)=∑t∈T(n)∖{0}‍E[gt(Xt1,Xt,Yt)∣Xt1]=∑t∈T(n)∖{0}‍∑(xt,yt)∈𝒳×𝒴‍gt(Xt1,xt,yt)P(Xt=xt,Yt=yt∣Xt1)=∑t∈T(n)∖{0}‍∑(xt,yt)∈𝒳×𝒴‍δx~(Xt1)δx(xt)δy(yt)P(Xt=xt∣Xt1)P(Yt=yt∣Xt=xt)=∑t∈T(n)∖{0}‍δx~(Xt1)b(y∣x)a(x∣x~)=|T(n-1)|·d·Sn-1(x~)b(y∣x)a(x∣x~),(3.24)Hn(ω)=∑t∈T(n)∖{0}‍gt(Xt1,Xt,Yt)=∑t∈T(n)∖{0}‍δx~(Xt1)δx(Xt)δy(Yt)=|T(n)|·Mn(x~,x,y).
Since T is a Cayley tree, we have
(3.25)limn→∞|T(n-1)|·d|T(n)|=1.
Combining the above fact with (3.9), (3.23), (3.24), and (3.19), we can derive our conclusion (3.21) directly.Let us conclude this section by proving our main result Theorem2.1.Proof of Theorem2.1.
Comparing (2.1) and (3.20), it is easy to see
(3.26)Sn(x,y)=∑t∈T(n)‍δx(Xt)δy(Yt)|T(n)|=∑x~∈𝒳‍Mn(x~,x,y)+δx(X0)δy(Y0)|T(n)|.
Taking limit on both sides of the above equation as n tends to infinity, it follows from Corollary 3.4 that
(3.27)limn→∞Sn(x,y)=∑x~∈𝒳‍π(x~)b(y∣x)a(x∣x~)=π(x)b(y∣x),
where the last equation holds because π is unique stationary distribution of the ergodic stochastic matrix A; that is, πA=π. Thus, we complete the proof of Theorem 2.1.



---

*Source: 768657-2012-09-23.xml*