# Strong Law of Large Numbers for Hidden Markov Chains Indexed by an Infinite Tree with Uniformly Bounded Degrees

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

---

## Abstract

We study strong limit theorems for hidden Markov chains fields indexed by an infinite tree with uniformly bounded degrees. We mainly establish the strong law of large numbers for hidden Markov chains fields indexed by an infinite tree with uniformly bounded degrees and give the strong limit law of the conditional sample entropy rate.


---

## Body

## 1. Introduction

The impact of the theory of hidden Markov models (HMMs) has become widespread for modeling sequences of dependent random variables during the last two decades. Hidden Markov models have many applications in a wide range of areas, such as speech recognition (Rabiner (1998)) [1], image processing [2], DNA sequence analysis (see, e.g., [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 [8]. In recent years, the work of Baum and Petrie [9] on finite-state finite-alphabet HMMs has been extended 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 want to expand tree-indexed homogeneous Markov chain fields to hidden Markov chain fields indexed by an infinite tree.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 L
n. 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 1
t, the second predecessor of t by 2
t, and the nth predecessor of t by t
n. The degree of a vertex is defined to be the number of neighbors of it. In this paper, we mainly consider an infinite tree which has uniformly bounded degree; that is, the numbers of neighbors of any vertices in this tree are uniformly bounded. 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. X
A
=
{
X
t
,
t
∈
A
} and denote by |
A
| the number of vertices of A.When the context permits, this type of trees is all denoted simply byT.Definition 1 (homogeneous Markov chains indexed by treeT (see [13, 14])).
LetT be an infinite tree with uniformly bounded degrees, let X be a finite state space, and let {
X
t
,
t
∈
T
} be a stochastic process defined on probability space (
Ω
,
F
,
P
), taking values in the finite set X. Let
(1)
p
=
{
p
i
,
i
∈
X
}
be a distribution on X, and let
(2)
A
=
a
j
∣
i
,
i
,
j
∈
X
,
be a transition probability matrix on X
2. If, for any vertex t,
(3)
P
X
t
=
j
∣
X
t
1
=
i
,
X
s
=
x
s
for
t
∧
s
≤
t
1
,
∀
x
s
∈
X
=
P
X
t
=
j
∣
X
t
1
=
i
=
a
j
∣
i
,
∀
i
,
j
∈
X
,
(4)
P
X
0
=
i
=
p
i
,
∀
i
∈
X
.
Thus {
X
t
,
t
∈
T
} will be called X-valued homogeneous Markov chains indexed by infinite tree with the initial distribution (1) and transition probability matrix A whose elements are determined by (3).Definition 2.
LetT be an infinite tree with uniformly bounded degrees and let {
X
t
,
t
∈
T
} and {
Y
t
,
t
∈
T
} be two stochastic processes on a probability space (
Ω
,
F
,
P
) with finite state spaces X and Y, respectively. Let A
=
(
a
(
j
∣
i
)
)
i
,
j
∈
X and B
=
(
b
(
y
∣
i
)
)
i
∈
X
,
y
∈
Y be two stochastic matrices on X
2 and X
×
Y, respectively. Suppose
(5)
P
X
0
=
i
=
p
i
,
∀
i
∈
X
,
P
Y
0
=
y
0
∣
X
0
=
x
0
=
b
y
0
∣
x
0
.
If for any vertex t
∈
T,
(6)
P
Y
t
=
y
t
,
X
t
=
x
t
∣
Y
t
1
=
y
t
1
,
X
t
1
=
x
t
1
,
aaaa
Y
s
=
y
s
,
X
s
=
x
s
,
for
t
∧
s
≤
t
1
aaaaaa
∀
x
t
,
x
t
1
,
x
s
∈
X
,
y
t
,
y
t
1
,
y
s
∈
Y
=
P
Y
t
=
y
t
,
X
t
=
x
t
∣
X
t
1
=
x
t
1
.
Moreover, we suppose
(7)
P
Y
t
=
y
t
,
X
t
=
x
t
∣
X
t
1
=
x
t
1
=
P
Y
t
=
y
t
∣
X
t
=
x
t
P
X
t
=
x
t
∣
X
t
1
=
x
t
1
∶
=
b
y
t
∣
x
t
a
x
t
∣
x
t
1
,
where
(8)
a
x
t
∣
x
t
1
=
P
X
t
=
x
t
∣
X
t
1
=
x
t
1
,
b
y
t
∣
x
t
=
P
Y
t
=
y
t
∣
X
t
=
x
t
.
Then {
X
t
,
Y
t
,
t
∈
T
} will be called X
×
Y-valuedhidden Markov chain indexed by an infinite tree
T, or calledtree-indexed hidden Markov chain taking values in the finite set X
×
Y.Remark 3.
If we sum overy
t in (6) and take conditional expectations with respect to {
X
t
1
,
X
s
,
t
∧
s
≤
t
1
} on both sides of the result equation, we can easily arrive at (3). In Definition 2, We can also call the processes {
X
t
,
t
∈
T
} and {
Y
t
,
t
∈
T
}, respectively, to bestate process and theobserved process indexed by an infinite tree.


## 2. Two Useful Lemmas

LetT be an infinite tree with uniformly bounded degrees and let {
X
t
,
Y
t
,
t
∈
T
} be X
×
Y-valued hidden Markov chains indexed by T. Let g
t
(
i
,
j
,
y
) be functions defined on X
×
X
×
Y. Let λ be a real number, L
0
=
{
0
}, F
n
=
σ
(
X
T
(
n
)
,
Y
T
(
n
)
), and now we define a stochastic sequence as follows:
(9)
t
n
λ
,
ω
=
e
λ
∑
t
∈
T
(
n
)
∖
0
g
t
(
X
t
1
,
X
t
,
Y
t
)
∏
t
∈
T
n
∖
{
0
}
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
.
At first we come to prove the following fact.Lemma 4.
{
t
n
(
λ
,
ω
)
,
F
n
,
n
≥
1
} is a nonnegative martingale.Proof of Lemma4.
Obviously, by (6), the process Z
t
=
(
X
t
,
Y
t
) is atree-indexed Markov chain with state space X
×
Y, so that we have
(10)
P
Y
T
n
=
y
T
n
,
X
T
n
=
x
T
n
=
p
x
0
P
Y
0
=
y
0
∣
X
0
=
x
0
×
∏
t
∈
T
n
∖
0
‍
P
Y
t
=
y
t
,
X
t
=
x
t
∣
X
t
1
=
x
t
1
(11)
=
p
x
0
P
Y
0
=
y
0
∣
X
0
=
x
0
×
∏
t
∈
T
n
∖
{
0
}
‍
P
X
t
=
x
t
∣
X
t
1
=
x
t
1
P
Y
t
=
y
t
∣
X
t
=
x
t
=
p
x
0
b
y
0
∣
x
0
∏
t
∈
T
n
∖
{
0
}
‍
b
y
t
∣
x
t
a
x
t
∣
x
t
1
.
Then we have
(12)
P
X
L
n
=
x
L
n
,
Y
L
n
=
y
L
n
∣
X
T
n
-
1
=
x
T
n
-
1
,
Y
T
n
-
1
=
y
T
n
-
1
=
P
X
T
n
=
x
T
n
,
Y
T
n
=
y
T
n
P
X
T
n
-
1
=
x
T
n
-
1
,
Y
T
n
-
1
=
y
T
n
-
1
=
∏
t
∈
L
n
‍
P
X
t
=
x
t
,
Y
t
=
y
t
∣
X
t
1
=
x
t
1
;
here the second equation holds because of (10). Furthermore, we have
(13)
E
e
λ
∑
t
∈
L
n
g
t
X
t
1
,
X
t
,
Y
t
∣
F
n
-
1
=
∑
x
L
n
,
y
L
n
‍
e
λ
∑
t
∈
L
n
g
t
X
t
1
,
x
t
,
y
t
aaaaaaaaaa
×
P
X
L
n
=
x
L
n
,
Y
L
n
=
y
L
n
∣
X
T
n
-
1
,
Y
T
n
-
1
=
∑
x
L
n
,
y
L
n
‍
∏
t
∈
L
n
‍
e
λ
g
t
X
t
1
,
x
t
,
y
t
P
X
t
=
x
t
,
Y
t
=
y
t
∣
X
t
1
=
∏
t
∈
L
n
‍
∑
x
t
,
y
t
∈
X
×
Y
‍
e
λ
g
t
X
t
1
,
x
t
,
y
t
P
X
t
=
x
t
,
Y
t
=
y
t
∣
X
t
1
=
∏
t
∈
L
n
‍
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
a
.
e
.
On the other hand, we also have(14)
t
n
λ
,
ω
=
t
n
-
1
λ
,
ω
e
λ
∑
t
∈
L
n
g
t
(
X
t
1
,
X
t
,
Y
t
)
∏
t
∈
L
n
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
.
Combining (13) and (14), we get
(15)
E
t
n
λ
,
ω
∣
F
n
-
1
=
t
n
-
1
λ
,
ω
a
.
e
.
Thus we complete the proof of Lemma 4.Lemma 5.
Let{
X
t
,
Y
t
,
t
∈
T
} be X
×
Y-valued hidden Markov chains indexed by an infinite tree T with uniformly bounded degrees. {
g
t
(
i
,
j
,
y
)
,
t
∈
T
} are functions defined as above; denote
(16)
R
n
ω
=
∑
t
∈
T
n
∖
0
‍
E
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
.
Let α
>
0, {
a
n
,
n
≥
1
} be a sequence of nonnegative random variables. Denote
(17)
D
α
=
ω
:
lim
⁡
n
→
∞
a
n
=
∞
,
∑
t
∈
T
n
∖
0
‍
a
a
A
a
a
limsup
⁡
n
→
∞
1
a
n
∑
t
∈
T
n
∖
0
‍
E
g
t
2
X
t
1
,
X
t
,
Y
t
e
α
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
a
a
a
a
a
a
a
a
a
a
a
i
a
a
a
a
a
a
a
a
a
i
i
×
e
α
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
aaaa
∑
t
∈
T
n
∖
0
‍
=
M
ω
<
∞
,
(18)
H
n
(
ω
)
=
∑
t
∈
T
n
∖
0
‍
g
t
X
t
1
,
X
t
,
Y
t
.
Then
(19)
lim
⁡
n
→
∞
H
n
ω
-
R
n
ω
a
n
=
0
a
.
e
.
o
n
D
(
α
)
.Proof.
By Lemma4, we have known that {
t
n
(
λ
,
ω
)
,
F
n
,
n
≥
1
} is a nonnegative martingale. According to Doob martingale convergence theorem, we have
(20)
lim
⁡
n
t
n
(
λ
,
ω
)
=
t
(
λ
,
ω
)
<
∞
a
.
e
.
,
which implies that
(21)
limsup
⁡
n
→
∞
ln
⁡
t
n
(
λ
,
ω
)
a
n
≤
0
a
.
e
.
Combining (9), (18), and (21), we arrive at
(22)
limsup
⁡
n
→
∞
1
a
n
λ
H
n
ω
-
∑
t
∈
T
n
∖
{
0
}
‍
ln
⁡
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
≤
0
a
.
e
.
Let λ
>
0. Dividing two sides of the above equation by λ, we get
(23)
limsup
⁡
n
→
∞
1
a
n
H
n
ω
-
∑
t
∈
T
n
∖
0
‍
ln
⁡
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
λ
≤
0
a
.
e
.
For case 0
<
λ
≤
α, by using inequalities ln
⁡
x
≤
x
-
1
(
x
>
0
), 0
≤
e
x
-
1
-
x
≤
(
1
/
2
)
x
2
e
|
x
|, and (23)(24)
limsup
⁡
n
→
∞
1
a
n
H
n
ω
-
∑
t
∈
T
n
∖
{
0
}
‍
E
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
≤
limsup
⁡
n
→
∞
1
a
n
∑
t
∈
T
n
∖
{
0
}
‍
ln
⁡
⁡
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
λ
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
ln
⁡
⁡
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
λ
-
E
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
≤
limsup
⁡
n
→
∞
1
a
n
∑
t
∈
T
n
∖
{
0
}
‍
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
-
1
λ
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
ln
⁡
⁡
E
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
λ
-
E
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
≤
λ
2
limsup
⁡
n
→
∞
1
a
n
∑
t
∈
T
n
∖
{
0
}
‍
E
g
t
2
X
t
1
,
X
t
,
Y
t
e
λ
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
≤
λ
2
limsup
⁡
n
→
∞
1
a
n
∑
t
∈
T
n
∖
{
0
}
‍
E
g
t
2
X
t
1
,
X
t
,
Y
t
e
α
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
≤
λ
2
M
(
ω
)
a
.
e
.
ω
∈
D
(
α
)
.
Letting λ
→
0
+ in (24), combining with (16), we have
(25)
limsup
⁡
n
→
∞
H
n
ω
-
R
n
ω
a
n
≤
0
a
.
e
.
ω
∈
D
α
.
Let -
α
≤
λ
<
0. Similarly to the analysis of the case 0
<
λ
≤
α, it follows from (22) that
(26)
liminf
⁡
n
→
∞
H
n
(
ω
)
-
R
n
ω
a
n
≥
λ
2
M
(
ω
)
a
.
e
.
ω
∈
D
(
α
)
.
Letting λ
→
0
-, we can arrive at
(27)
liminf
⁡
n
→
∞
H
n
ω
-
R
n
ω
a
n
≥
0
a
.
e
.
ω
∈
D
(
α
)
.
Combining (25) and (27), we obtain (19) directly.Corollary 6.
Let{
X
t
,
Y
t
,
t
∈
T
} be X
×
Y-valued hidden Markov chains indexed by an infinite tree T with uniformly bounded degrees. If {
g
t
(
i
,
j
,
y
)
,
t
∈
T
} are the uniformly bounded functions defined on X
2
×
Y, let N be nonnegative integer. Then
(28)
lim
⁡
n
→
∞
H
n
ω
-
G
n
ω
|
T
(
n
+
N
)
|
=
0
a
.
e
.Proof.
Lettinga
n
=
|
T
(
n
+
N
)
| in Lemma 5, noticing that {
g
t
(
i
,
j
,
y
)
,
t
∈
T
} are uniformly bounded, then D
(
α
)
=
Ω for all α
>
0. This theorem follows from Lemma 5 directly.


## 3. Strong Law of Large Numbers

In the following, we always letN
≥
0, k
∈
S, d
0
(
t
)
∶
=
1, and denote
(29)
d
N
t
∶
=
τ
∈
T
:
τ
N
=
t
,
(30)
S
n
N
x
=
∑
t
∈
T
(
n
)
d
N
(
t
)
δ
x
(
X
t
)
T
n
+
N
,
∀
x
∈
X
;
here and thereafter δ
x
(
·
) denotes the Kronecker function. The following lemma is very useful for proving our main result.Lemma 7 (see [14]).
LetT be an infinite tree T with uniformly bounded degrees and let {
X
t
,
t
∈
T
} be a tree-indexed Markov chain with finite state space X, which is determined by initial distribution (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
‍
π
(
x
)
=
1. Let S
n
N
(
x
) be defined as (30). Thus one has
(31)
lim
⁡
n
→
∞
S
n
N
x
=
π
x
a
.
e
.Theorem 8.
LetT be an infinite tree with uniformly bounded degrees and let {
X
t
,
Y
t
,
t
∈
T
} be X
×
Y-valued hidden Markov chains indexed by T. For all nonnegative integer N, define the following weighted empirical measure of triples (
X
t
1
,
X
t
,
Y
t
):
(32)
M
n
N
x
~
,
x
,
y
=
∑
t
∈
T
n
∖
{
0
}
d
N
t
δ
x
~
X
t
1
δ
x
X
t
δ
y
Y
t
T
n
+
N
aaaaaaaaaaaaaaaaaaaaaaaaaaaa
∀
(
x
~
,
x
,
y
)
∈
X
×
X
×
Y
.
If the transition probability matrix A of {
X
t
,
t
∈
T
} is ergodic, one has
(33)
lim
⁡
n
→
∞
M
n
N
x
~
,
x
,
y
-
π
x
~
b
y
∣
x
a
x
∣
x
~
=
0
a
.
e
.
,
where π is the stationary distribution of the ergodic matrix A.Proof.
For anyt
∈
T, let
(34)
g
t
i
,
j
,
k
=
d
N
(
t
)
δ
x
~
(
i
)
δ
x
(
j
)
δ
y
(
k
)
.
Then we have
(35)
R
n
ω
=
∑
t
∈
T
n
∖
{
0
}
‍
E
g
t
X
t
1
,
X
t
,
Y
t
∣
X
t
1
=
∑
t
∈
T
n
∖
{
0
}
‍
∑
x
t
,
y
t
∈
X
×
Y
‍
g
t
X
t
1
,
x
t
,
y
t
aaaaaaaaaaaaiaaaaaa
×
P
X
t
=
x
t
,
Y
t
=
y
t
∣
X
t
1
=
∑
t
∈
T
n
∖
{
0
}
‍
∑
x
t
,
y
t
∈
X
×
Y
‍
d
N
t
δ
x
~
X
t
1
δ
x
x
t
δ
y
y
t
aaaaiaaaaaaaaaaaaaa
×
P
X
t
=
x
t
∣
X
t
1
aaaaaaaaaaaaaaaiaaa
×
P
Y
t
=
y
t
∣
X
t
=
x
t
=
∑
t
∈
T
n
∖
{
0
}
‍
d
N
t
δ
x
~
X
t
1
b
y
∣
x
a
x
∣
x
~
=
∑
t
∈
T
n
-
1
‍
d
N
+
1
t
δ
x
~
X
t
b
y
∣
x
a
x
∣
x
~
=
T
n
+
N
·
S
n
-
1
N
+
1
x
~
b
y
∣
x
a
x
∣
x
~
,
H
n
ω
=
∑
t
∈
T
n
∖
{
0
}
‍
g
t
X
t
1
,
X
t
,
Y
t
=
∑
t
∈
T
n
∖
{
0
}
‍
d
N
t
δ
x
~
X
t
1
δ
x
X
t
δ
y
Y
t
=
T
n
+
N
·
M
n
N
x
~
,
x
,
y
.
Combining (35) and Corollary 6, we obtain
(36)
lim
⁡
n
→
∞
M
n
N
x
~
,
x
,
y
-
S
n
-
1
N
+
1
x
~
b
y
∣
x
a
x
∣
x
~
=
0
.
By using Lemma 7, our conclusion (33) holds.Corollary 9.
Under the conditions of Theorem8, denote M
n
(
x
~
,
x
,
y
)
=
M
n
0
(
x
~
,
x
,
y
); then one has
(37)
lim
⁡
n
→
∞
M
n
x
~
,
x
,
y
-
π
x
~
b
y
∣
x
a
x
∣
x
~
=
0
a
.
e
.
,
where π is the stationary distribution of the ergodic matrix A.For every finiten
∈
N, let {
X
t
,
Y
t
,
t
∈
T
} be X
×
Y-valued hidden Markov chains indexed by an infinite tree T with uniformly bounded degrees. We define the offspring empirical measure as follows:
(38)
S
n
x
,
y
=
∑
t
∈
T
n
δ
x
X
t
δ
y
Y
t
T
n
,
∀
x
,
y
∈
X
×
Y
.In the following, we consider the limit law of the random sequence ofS
n
(
x
,
y
) which are defined as above.Theorem 10.
LetT be an infinite tree T with uniformly bounded degrees, and let {
X
t
,
Y
t
,
t
∈
T
} be X
×
Y-valued hidden Markov chains indexed by T. If the transition probability matrix A of {
X
t
,
t
∈
T
} is ergodic, then
(39)
lim
⁡
n
→
∞
S
n
x
,
y
=
π
(
x
)
b
y
∣
x
a
.
e
.
,
where π is the stationary distribution of the ergodic matrix A.Proof.
LettingN
=
0, we have
(40)
M
n
x
~
,
x
,
y
=
M
n
0
x
~
,
x
,
y
=
∑
t
∈
T
n
∖
{
0
}
δ
x
~
X
t
1
δ
x
X
t
δ
y
Y
t
T
n
aaaaaaaaa
∀
(
x
~
,
x
,
y
)
∈
X
×
X
×
Y
.
Comparing (38) with (40), it is easy to see
(41)
S
n
x
,
y
=
∑
t
∈
T
n
δ
x
X
t
δ
y
Y
t
T
n
=
∑
x
~
∈
X
‍
M
n
(
x
~
,
x
,
y
)
+
δ
x
(
X
0
)
δ
y
(
Y
0
)
T
n
.
Taking limit on both sides of above equation as n tends to infinity, it follows from Corollary 9 that
(42)
lim
⁡
n
→
∞
S
n
x
,
y
=
∑
x
~
∈
X
‍
π
(
x
~
)
b
y
∣
x
a
x
∣
x
~
=
π
(
x
)
b
y
∣
x
a
.
e
.
,
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 10.From the expression of (38) we can easily obtain the empirical measure of the observed chain {
Y
t
,
t
∈
T
} which is denoted by M
n
(
·
),
(43)
M
n
y
=
∑
x
∈
X
‍
S
n
x
,
y
=
∑
t
∈
T
(
n
)
δ
y
(
Y
t
)
T
n
,
∀
y
∈
Y
.
Thus we can obtain Corollary 11.Corollary 11.
Under the same conditions of Theorem10, one has
(44)
lim
⁡
n
→
∞
M
n
(
y
)
=
∑
x
∈
X
‍
π
(
x
)
b
y
∣
x
a
.
e
.Letf
(
x
,
y
) be any function defined on X
×
Y. Denote
(45)
G
n
(
ω
)
=
∑
t
∈
T
n
‍
f
X
t
,
Y
t
.
By simpe computation, we arrive at Corollary 12.Corollary 12.
Under the same conditions of Theorem10, one also has
(46)
lim
⁡
n
→
∞
G
n
(
ω
)
T
n
=
∑
x
,
y
∈
X
×
Y
‍
π
(
x
)
b
y
∣
x
f
(
x
,
y
)
a
.
e
.Now we define conditional entropy rate ofY
T
(
n
) given X
T
(
n
) by
(47)
f
n
ω
=
-
1
T
n
ln
⁡
P
Y
T
n
∣
X
T
n
.
From (6), we obtain that
(48)
f
n
ω
=
-
∑
t
∈
T
n
ln
⁡
P
Y
t
∣
X
t
T
n
.The convergence off
n
(
ω
) to a constant in a sense (L
1 convergence, convergence in probability, a.e. convergence) is called the conditional version ofShannon-McMillan theorem or the entropy theorem or the AEP (asymptotic equipartition property) in information theory. Here from Corollary 12, if we let
(49)
f
X
t
,
Y
t
=
-
ln
⁡
P
Y
t
∣
X
t
,
we can easily obtain the Shannon-McMillan theorem with a.e. convergence for conditional entropy theorem of hidden Markov chain fields on tree T.Corollary 13.
Under the same conditions of Theorem10, one has
(50)
lim
⁡
n
→
∞
f
n
(
ω
)
=
-
∑
y
∈
Y
‍
∑
x
∈
X
‍
π
x
b
y
∣
x
ln
⁡
b
y
∣
x
a
.
e
.Here one also specifies 0
ln
⁡
0 as zero by convention.


## 4. Conclusion

This paper gives some strong limit theorems for hidden Markov chains fields indexed by an infinite tree with uniformly bounded degrees. We study the strong law of large numbers for hidden Markov chains fields indexed by an infinite tree with uniformly bounded degrees and give the strong law of the conditional sample entropy rate.



---

*Source: 628321-2014-12-09.xml*