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

Authors: Bao Wang; Weiguo Yang; Zhiyan Shi; Qingpei Zang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We study the strong law of large numbers for the frequencies of occurrence of states and ordered couples of states for countable Markov chains indexed by an infinite tree with uniformly bounded degree, which extends the corresponding results of countable Markov chains indexed by a Cayley tree and generalizes the relative results of finite Markov chains indexed by a uniformly bounded tree.


---

## Body

## 1. Introduction

A treeT is a graph which is connected and contains no circuits. Given any two vertices α
≠
β
∈
T. Let α
β
¯ be the unique path connecting α and β. Define the distance d
(
α
,
β
) to be the number of edges contained in the path α
β
¯Select a vertex as the root (denoted byo). For any two vertices σ and t of tree T, we write σ
≤
t if σ is on the unique path from the root o to t. We denote by σ
∧
t the vertex farthest from o satisfying σ
∧
t
≤
t and σ
∧
t
≤
σ. For any vertex t of tree T, we denote by |
t
| the distance between o and t. The set of all vertices with distance n from the root o is called the nth level of T. For any vertex t of tree T, we denote the predecessor of t by 1
t, the predecessor of 1
t by 2
t, and the predecessor of (
n
-
1
)
t by n
t. We also call n
t the nth predecessor of t. Similarly, we denote the one of the successor of t by 1
t, the one of the successors of 1
t by 2
t, and one of the successors of (
n
-
1
)
t by n
t. We denote by T
(
n
) the subtree comprised of level 0 (the root o) through level n, and by L
n the set of all vertices on level n. In this paper, we mainly consider an infinite tree which has uniformly bounded degrees. That is, the numbers of neighbors of any vertices in this tree are uniformly bounded; we call it the uniformly bounded tree. If the root of a tree has M neighboring vertices and other vertices have M
+
1 neighboring vertices, we call this type of tree a Cayley tree and denote it by T
C
,
M. It is easy to see that this type of tree is the special case of uniformly bounded tree. Let S be the subgraph of T, X
S
=
{
X
t
,
t
∈
S
}, and x
S the realization of X
S. We denote by |
S
| the number of vertices of S.Definition 1 (see [1]).
LetT be a local finite and infinite tree; that is, the tree has infinite vertices and the degrees of any vertices in this tree are finite. Let G
=
{
0,1
,
2
,
…
} be a countable state space and {
X
t
,
t
∈
T
} a collection of G-valued random variables defined on the probability space (
Ω
,
ℱ
,
P
). Let
(1)
p
=
(
p
(
x
)
,
x
∈
G
)
be a distribution on G, and let
(2)
P
=
(
P
(
y
∣
x
)
)
,
x
,
y
∈
G
be a stochastic matrix on G
2. Let n be any positive integer. If for any vertices t
,
t
1
,
t
2
,
…
t
n
∈
T, t
i
∧
t
≤
1
t, 1
≤
i
≤
n,
(3)
P
(
X
t
=
y
∣
X
1
t
=
x
and
X
t
1
=
x
t
1
,
X
t
2
=
x
t
2
,
…
,
X
t
n
=
x
t
n
)
=
P
(
X
t
=
y
∣
X
1
t
=
x
)
=
P
(
y
∣
x
)
,
∀
x
,
y
∈
G
,
(4)
P
(
X
o
=
x
)
=
p
(
x
)
,
∀
x
∈
G
,
{
X
t
,
t
∈
T
} will be called G-valued Markov chains indexed by this tree T with the initial distribution (1) and the transition matrix (2) or called T-indexed Markov chains with state space G.Definition 2 (see [2, page 157]).
LetP be a stochastic matrix defined on the countable state space G. If there exists a distribution π
=
(
π
(
0
)
,
π
(
1
)
,
…
) satisfying
(5)
sup
⁡
i
⁡
∑
j
|
P
(
n
)
(
j
∣
i
)
-
π
(
j
)
|
⟶
0
,
as
n
⟶
∞
,
where P
(
n
)
(
j
∣
i
) is the n-step transition probability determined by P, then P is said to be strongly ergodic with distribution π. Obviously, if (5) holds, then we have π
P
=
π, and π is said to be the stationary distribution determined by P.Let{
X
n
,
n
≥
0
} be a sequence of random variables taking values in state space S
=
{
1,2
,
…
,
N
} with the joint distribution
(6)
p
(
x
0
,
…
,
x
n
)
=
P
(
X
0
=
x
0
,
…
,
X
n
=
x
n
)
,
x
i
∈
S
,
0
≤
i
≤
n
,
n
≥
0
.
Let
(7)
f
n
(
ω
)
=
-
1
n
ln
⁡
p
(
X
0
,
…
,
X
n
)
;
f
n
(
ω
) is called the entropy density of {
X
i
,
0
≤
i
≤
n
}.The convergence off
n
(
ω
) to a constant in a sense (L
1 convergence, convergence in probability, and a
.
e. convergence) is called Shannon-McMillan-Breiman theorem or asymptotic equipartition property (AEP) in information theory. Shannon [3] first proved AEP in convergence in probability for finite stationary ergodic sequence of random variables. McMillan [4] and Breiman [5, 6] proved AEP in L
1 and a
.
e. convergence, respectively, for finite stationary ergodic sequence of random variables. Chung [7] generalized Breiman's result to countable case.The subject of tree-indexed processes is rather young. Benjamini and Peres [1] have given the notion of the tree-indexed Markov chains and studied the recurrence and ray-recurrence for them. Guyon [8] has given the definition of bifurcating Markov chains indexed by binary tree and studied their limit theorems. Berger and Ye [9] have studied the existence of entropy rate for some stationary random fields on a homogeneous tree. Ye and Berger [10, 11] by using Pemantle's result [12] and a combinatorial approach have studied the asymptotic equipartition property (AEP) in the sense of convergence in probability for a PPG-invariant and ergodic random field on a homogeneous tree. Yang [13] has studied the strong law of large numbers and the asymptotic equipartition property (AEP) for finite Markov chains indexed by a homogeneous tree. Yang and Ye [14] have studied the strong law of large numbers and the asymptotic equipartition property (AEP) for finite level-nonhomogeneous Markov chains indexed by a homogeneous tree. Huang and Yang [15] have studied the strong law of large numbers and the asymptotic equipartition property (AEP) for finite Markov chains indexed by an infinite tree with uniformly bounded degree. Recently, Wang et al. [16] have studied the strong law of large numbers for countable Markov chains indexed by a Cayley tree.In some previous articles, only the tree-indexed Markov chains with the finite state space are considered; meanwhile the countable case has very important theoretical significance, so Chung [7] generalized Breiman's result [5, 6] to the countable case. Wang et al. [16] have studied the strong law of large numbers countable Markov chains indexed by a Cayley tree.The technique used to study the strong law of large numbers for countable Markov chains indexed by trees is different from that for finite case. The processing method of finite state space cannot apply to countable state space, because the sum and limit cannot be exchanged. For studying the strong law of large numbers for countable Markov chains indexed by trees, we first establish a strong limit theorem then use this strong limit theorem and smoothing property of conditional expectation repeatedly to establish our strong law of large numbers. In this paper, we use the same approach used in [16] to study the strong law of large numbers for Markov chains indexed by a uniformly bounded tree. Our results generalize the results of Huang and Yang [15] for finite Markov chains indexed by a uniformly bounded tree (Figure 1) and the results of Wang et al. [16] for countable Markov chains indexed by a Cayley tree.Figure 1
Uniformly bounded treeT.


## 2. Some Lemmas

Before proving the main results, we begin with some lemmas.Lemma 3.
LetT be an infinite tree with uniformly bounded degree, {
X
t
,
t
∈
T
} a T-indexed Markov chain with countable state space G defined as before, and {
g
t
(
x
,
y
)
,
t
∈
T
} uniformly bounded functions defined on G
2. Let
(8)
G
n
(
ω
)
=
∑
t
∈
T
(
n
)
∖
{
o
}
‍
E
[
g
t
(
X
1
t
,
X
t
)
∣
X
1
t
]
,
H
n
(
ω
)
=
∑
t
∈
T
(
n
)
∖
{
o
}
‍
g
t
(
X
1
t
,
X
t
)
.
Then for all N
≥
0, we have
(9)
lim
⁡
n
→
∞
H
n
(
ω
)
-
G
n
(
ω
)
|
T
(
n
+
N
)
|
=
0
a
.
e
.Proof.
Huang and Yang (see [15, Theorem 1]) have obtained a similar result for finite Markov chains indexed by a uniformly bounded tree. By checking carefully the proof of that theorem, one can find it also holds for countable Markov chains indexed by a uniformly bounded tree, so the proof of this lemma is omitted.Lemma 4.
LetT and {
X
t
,
t
∈
T
} be defined as Lemma 3, ℱ
n
=
σ
(
X
T
(
n
)
), as t
∈
L
n, n
≥
1, ∀
k
∈
G, ∀
h
≥
1, and we have
(10)
P
(
X
h
t
=
k
∣
ℱ
n
)
=
P
(
X
h
t
=
k
∣
X
t
)
.Proof.
We only need to prove the situation ofh
=
2. By the Markov property (3), we have
(11)
P
(
X
2
t
=
k
∣
ℱ
n
)
=
∑
m
‍
P
(
X
2
t
=
k
,
X
1
t
=
m
∣
ℱ
n
)
=
∑
m
‍
P
(
X
2
t
=
k
∣
X
1
t
=
m
,
ℱ
n
)
P
(
X
1
t
=
m
∣
ℱ
n
)
=
∑
m
‍
P
(
X
2
t
=
k
∣
X
1
t
=
m
,
X
t
)
P
(
X
1
t
=
m
∣
X
t
)
=
∑
m
‍
P
(
X
2
t
=
k
,
X
1
t
=
m
∣
X
t
)
=
P
(
X
2
t
=
k
∣
X
t
)
.
By induction, (10) holds for h
≥
2.


## 3. Strong Law of Large Numbers

In the following, letN
≥
0, k
∈
G, d
0
(
t
)
=
1, let N
τ be the Nth predecessor of τ defined as before, and
(12)
d
N
(
t
)
=
|
τ
∈
T
:
N
τ
=
t
|
,
S
k
N
(
A
)
=
∑
t
∈
A
‍
I
k
(
X
t
)
d
N
(
t
)
,
(13)
S
l
,
k
N
(
A
)
=
∑
t
∈
A
‍
I
l
(
X
1
t
)
I
k
(
X
t
)
d
N
(
t
)
,
where
(14)
I
k
(
i
)
=
{
1
,
i
=
k
,
0
,
i
≠
k
.Theorem 5.
LetT be an infinite tree with uniformly bounded degree, P a strongly ergodic stochastic matrix, and π the unique stationary distribution of P. Let {
X
t
,
t
∈
T
} be a T-indexed Markov chain taking values in countable state space G with the stochastic matrix P. Then, for any integer N
≥
0, we have
(15)
lim
⁡
n
→
∞
S
k
N
(
T
(
n
)
)
|
T
(
n
+
N
)
|
=
π
(
k
)
a
.
e
.
,
k
∈
G
.Proof.
Letg
t
(
x
,
y
)
=
d
N
(
t
)
I
k
(
y
) for all t
∈
T in Lemma 3; then by (8) and (12), we have
(16)
H
n
(
ω
)
=
∑
t
∈
T
(
n
)
∖
{
o
}
‍
d
N
(
t
)
I
k
(
X
t
)
=
S
k
N
(
T
(
n
)
)
-
d
N
(
o
)
I
k
(
X
o
)
,
G
n
(
ω
)
=
∑
t
∈
T
(
n
)
∖
{
o
}
‍
E
[
d
N
(
t
)
I
k
(
X
t
)
∣
X
1
t
]
=
∑
t
∈
T
(
n
)
∖
{
o
}
‍
d
N
(
t
)
P
(
X
t
=
k
∣
X
1
t
)
=
∑
t
∈
T
(
n
-
1
)
‍
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
)
.
Since T is a uniformly bounded tree, so {
g
t
(
x
,
y
)
=
d
N
(
t
)
I
k
(
y
)
,
t
∈
T
} are uniformly bounded functions defined on G
2; then, from Lemma 3, we have
(17)
lim
⁡
n
→
∞
S
k
N
(
T
(
n
)
)
-
∑
t
∈
T
(
n
-
1
)
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
)
|
T
(
n
+
N
)
|
=
0
a
.
e
.
Let g
t
(
x
,
y
)
=
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
=
y
) in Lemma 3; by Definition 1 and Lemma 4, we have
(18)
E
[
g
t
(
X
1
t
,
X
t
)
∣
X
1
t
]
=
E
[
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
)
∣
X
1
t
]
=
d
N
+
1
(
t
)
E
[
E
(
I
k
(
X
1
t
)
∣
X
t
)
∣
X
1
t
]
=
d
N
+
1
(
t
)
E
[
E
(
I
k
(
X
1
t
)
∣
ℱ
|
t
|
)
∣
ℱ
|
t
|
-
1
]
=
d
N
+
1
(
t
)
E
[
I
k
(
X
1
t
)
∣
ℱ
|
t
|
-
1
]
=
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
1
t
)
.
Since {
g
t
(
x
,
y
)
=
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
=
y
)
,
t
∈
T
} are also uniformly bounded functions defined on G
2, from Lemma 3 and (18), for any N
≥
0, we have
(19)
lim
⁡
n
→
∞
(
(
∑
t
∈
T
(
n
-
1
)
∖
{
o
}
‍
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
)
-
∑
t
∈
T
(
n
-
1
)
∖
{
o
}
‍
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
1
t
)
)
×
(
|
T
(
n
+
N
-
1
)
|
)
-
1
(
∑
t
∈
T
(
n
-
1
)
∖
{
o
}
‍
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
)
)
=
0
a
.
e
.
Hence,
(20)
lim
⁡
n
→
∞
⁡
(
(
∑
t
∈
T
(
n
-
1
)
‍
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
)
-
∑
t
∈
T
(
n
-
2
)
‍
d
N
+
2
(
t
)
P
(
X
2
t
=
k
∣
X
t
)
)
×
(
|
T
(
n
+
N
)
|
)
-
1
(
∑
t
∈
T
(
n
-
1
)
‍
d
N
+
1
(
t
)
P
(
X
1
t
=
k
∣
X
t
)
)
=
0
a
.
e
.
By (17) and (20), we have
(21)
lim
⁡
n
→
∞
⁡
(
(
S
k
N
(
T
(
n
)
)
-
∑
t
∈
T
(
n
-
2
)
d
N
+
2
(
t
)
P
(
X
2
t
=
k
∣
X
t
)
)
×
(
|
T
(
n
+
N
)
|
)
-
1
(
S
k
N
(
T
(
n
)
)
-
∑
t
∈
T
(
n
-
2
)
d
N
+
2
(
t
)
P
(
X
2
t
=
k
∣
X
t
)
)
)
=
0
a
.
e
.
By induction, for fixed N
≥
0 and all h
≥
1, we have
(22)
lim
⁡
n
→
∞
S
k
N
(
T
(
n
)
)
-
∑
t
∈
T
(
n
-
h
)
d
N
+
h
(
t
)
P
(
X
h
t
=
k
∣
X
t
)
|
T
(
n
+
N
)
|
=
0
a
.
e
.
By (12), we have
(23)
∑
t
∈
T
(
n
-
h
)
‍
d
N
+
h
(
t
)
P
(
X
h
t
=
k
∣
X
t
)
=
∑
t
∈
T
(
n
-
h
)
‍
∑
l
∈
G
‍
d
N
+
h
(
t
)
I
l
(
X
t
)
P
(
X
h
t
=
k
∣
X
t
=
l
)
=
∑
l
∈
G
‍
∑
t
∈
T
(
n
-
h
)
‍
d
N
+
h
(
t
)
I
l
(
X
t
)
P
(
h
)
(
k
∣
l
)
=
∑
l
∈
G
‍
S
l
N
+
h
(
T
(
n
-
h
)
)
P
(
h
)
(
k
∣
l
)
.
As h
≤
n,
(24)
∑
l
∈
G
‍
S
l
N
+
h
(
T
(
n
-
h
)
)
=
|
T
(
N
+
n
)
|
-
|
T
(
N
+
h
-
1
)
|
,
we have as h
≤
n
(25)
|
∑
t
∈
T
(
n
-
h
)
d
N
+
h
(
t
)
P
(
X
h
t
=
k
∣
X
t
)
|
T
(
n
+
N
)
|
-
π
(
k
)
|
≤
|
∑
l
∈
G
S
l
N
+
h
(
T
(
n
-
h
)
)
[
P
(
h
)
(
k
∣
l
)
-
π
(
k
)
]
|
T
(
n
+
N
)
|
|
+
|
T
(
N
+
h
-
1
)
|
|
T
(
n
+
N
)
|
≤
sup
⁡
l
∈
G
|
P
(
h
)
(
k
∣
l
)
-
π
(
k
)
|
+
|
T
(
N
+
h
-
1
)
|
|
T
(
n
+
N
)
|
.
Since P is strongly ergodic, the first term of right-hand side of (25) is arbitrary small for large h, and the limit of second term is zero as n
→
∞; (15) can be obtained from (22) and (25).Theorem 6.
Under the conditions of Theorem5, let S
l
,
k
N
(
A
) be defined by (13); then
(26)
lim
⁡
n
→
∞
⁡
S
l
,
k
N
(
T
(
n
)
∖
{
o
}
)
|
T
(
n
+
N
)
|
=
π
(
l
)
P
(
k
∣
l
)
a
.
e
.
,
k
,
l
∈
G
.Proof.
Letg
t
(
x
,
y
)
=
d
N
(
t
)
I
l
(
x
)
I
k
(
y
)
for
all
t
∈
T in Lemma 3; it is easy to see that {
g
t
(
x
,
y
)
,
t
∈
T
} are uniformly functions defined in G
2, and, by (8) and Lemma 3, we have
(27)
H
n
(
ω
)
=
∑
t
∈
T
(
n
)
∖
{
o
}
‍
d
N
(
t
)
I
l
(
X
1
t
)
I
k
(
X
t
)
=
S
l
,
k
N
(
T
(
n
)
∖
{
o
}
)
,
G
n
(
ω
)
=
∑
t
∈
T
(
n
)
∖
{
o
}
‍
E
[
d
N
(
t
)
I
l
(
X
1
t
)
I
k
(
X
t
)
∣
X
1
t
]
=
∑
t
∈
T
(
n
)
∖
{
o
}
‍
I
l
(
X
1
t
)
d
N
(
t
)
P
(
X
t
=
k
∣
X
1
t
=
l
)
=
∑
t
∈
T
(
n
-
1
)
‍
d
N
+
1
(
t
)
I
l
(
X
t
)
P
(
k
∣
l
)
=
S
l
N
+
1
(
T
(
n
-
1
)
)
P
(
k
∣
l
)
,
(28)
lim
⁡
n
→
∞
S
l
,
k
N
(
T
(
n
)
∖
{
o
}
)
-
S
l
N
+
1
(
T
(
n
-
1
)
)
P
(
k
∣
l
)
|
T
(
n
+
N
)
|
=
0
a
.
e
.
Equation (26) follows from (28) and Theorem 5.LetN
=
0 in Theorems 5 and 6; we can obtain the strong law of large numbers for the frequencies of occurrence of states and ordered couples of states for countable Markov chains indexed by the uniformly bounded tree.Corollary 7.
Under the conditions of Theorem5, let
(29)
S
k
(
T
(
n
)
)
=
S
k
0
(
T
(
n
)
)
=
|
{
t
∈
T
(
n
)
:
X
t
=
k
}
|
,
S
l
,
k
(
T
(
n
)
∖
{
o
}
)
=
S
l
,
k
0
(
T
(
n
)
∖
{
o
}
)
=
|
{
t
∈
T
(
n
)
∖
{
o
}
:
(
X
1
t
,
X
t
)
=
(
l
,
k
)
}
|
;
then
(30)
lim
⁡
n
→
∞
S
k
(
T
(
n
)
)
|
T
(
n
)
|
=
π
(
k
)
a
.
e
.
,
k
∈
G
,
lim
⁡
n
→
∞
S
l
,
k
(
T
(
n
)
∖
{
o
}
)
|
T
(
n
)
|
=
π
(
l
)
P
(
k
∣
l
)
a
.
e
.
,
k
,
l
∈
G
.Proof.
LettingN
=
0 in Theorems 5 and 6, this corollary follows.From Theorems5 and 6, we can obtain easily the strong law of large numbers for countable Markov chains indexed by a Cayley tree [16] and the strong law of large numbers for finite Markov chains indexed by a uniformly bounded tree [15].



---

*Source: 325361-2014-03-13.xml*