1. INTRODUCTION
We begin with notations and definitions, which mainly follow from
Spitzer [6] and Berger and Ye
[2].
A tree is a graph G = {T,E} which is
connected and contains no circuits. Thus, G is a tree if and
only if, given any two vertices x ≠ y ∈
T, there exists an unique path x =
z1,z2,…,zm
= y from x to y with
z1,…,zm
distinct. The distance between x and y is defined to
be m − 1, the number of edges in the path connecting
x and y.
To index the vertices on T, we first assign a vertex as the
“root” and label it {0}. A vertex is said to be on the
nth level if the path linking it to the root has n
edges. The root {0} is also said to be on the 0th level.
Definition 1: Let T be a tree with root {0}, and
let {Nn,h ≥ 1} be a
sequence of positive integers. T is said to be a generalized Bethe tree
or a generalized Cayley tree if each vertex on the nth level
has Nn+1 branches to the (n +
1)st level.
For example, when N1 = N + 1 ≥ 2 and
Nn = N(n ≥ 2),
T is a rooted Bethe tree
TB,N on which each vertex has
N + 1 neighboring vertices (TB,2
drawn in Fig. 1), and when
Nn = N ≥ 1(n ≥ 1),
T is a rooted Cayley tree
TC,N on which each vertex has
N branches to the next level.
In the following, we always assume that T is a generalized
Cayley tree and denote by T(n) the
subgraph of T containing the vertices from level 0 (the root)
to level n. We use (n,j)(1 ≤ j
≤
N1,…,Nn,n
≥ 1) to denote the jth vertex at the nth level and
denote by |B| the number of vertices in the
subgraph B. It is easy to see that for n ≥ 1,
Let b be a positive integer, S =
{1,2,…,b},Ω =
ST,ω = ω(·) ∈
Ω, where ω(·) is a function defined on T and
taking values in S, and F be the smallest Borel field
containing all cylinder sets in Ω. Let X =
{Xt,t ∈ T} be the
coordinate stochastic process defined on the measurable space
(Ω,F); that is, for any ω = ω(·) ∈
Ω, define
Let μ be a probability measure on (Ω,F). Denote
Now, we give a definition of Markov chain fields on the tree
T by using the cylinder distribution directly, which is a
natural extension of the classical definition of Markov chains (see
Feller [3, p.372]).
Definition 2: Let P =
P(j|i) be a strictly positive
stochastic matrix on S, q =
(q(1),…,q(b)) be a strictly positive
distribution on S, and μP be a measure
on (Ω,F). If
then μP will be called a Markov chain field
on tree T determined by the stochastic matrix P and
the distribution q.
Remark 1: μP given by (3) and (4)
also depends on q. Hence, Definition 2 slightly extends the
one given by Spitzer [6] and Berger
and Ye [2], where q is
taken to be the stationary distribution π =
(π(1),…,π(b)) determined by P.
Remark 2: If for all n ≥
1,Nn = 1 and
xn,1 is denoted by
xn, then we have by (3) and (4),
This is the cylinder distribution of Markov chains.
The tree model has drawn increasing interest from specialists in
physics, probability, and information theory. Berger and Ye [2] have studied the existence of entropy rate
for G-invariant random fields on trees. Recently, Ye and Berger
[7] have also studied the ergodic
property and the Shannon–McMillan theorem for PPG-invariant
fields on trees. However, their main work is restricted to Bethe tree
TB,2 or Cayley tree
TC,2, and the convergence of the results
is only the convergence in probability. Benjamini and Peres [1] have introduced the notions of the
tree-indexed Markov chains and the tree-indexed random walk and have
studied the recurrence and ray-recurrence for them.
In Section 3, we first prove a strong limit theorem on the
frequencies of the ordered couples of states for the Markov chain
fields on the generalized Cayley trees (or generalized Bethe trees),
from which some strong limit theorems, including the
Shannon–McMillan theorem with a.s. convergence, for the Markov
chain fields on the Cayley tree
TC,N or Bethe tree
TB,N follow.
In the proof, a new technique in the study of a.s. convergence
proposed in our previous works (see Liu and Yang [4,5]) is applied.
2. SOME LEMMAS
Lemma 1: Let μ1 and
μ2 be two probability measures on the measurable space
(Ω,F), and let {τn,n
≥ 1} be a sequence of positive random variables such that
Then,
Proof: Let Zn =
μ2(XT(n))/μ1(XT(n)).
It is easy to see that
Eμ1(Zn)
≤ 1, where Eμ1 denotes the
expectation under μ1. Hence, for all ε > 0, we
have by the Markov's inequality,
Since ε > 0 is arbitrary, by the Borel–Cantelli lemma,
it follows from (7) that
Obviously, (5) and (8) imply (6). █
Let k,l ∈
S,Sn(k,ω) be the
number of k in
XT(n) =
{Xt,t ∈
T(n)}, and
Sn(k,l,ω) be the
number of couple (k,l) in the couples of random
variables
that is,
where
Let
It is easy to see that
In the following, we always assume that μP is
the Markov chain field on tree T determined by the stochastic
matrix P = (P(j|i)) and the
distribution q.
Lemma 2: For all k ∈ S, we have
Proof: Let 0 < λ < 1 be a constant, and Q
= (Q(j|i)), i,j
∈ S, be another stochastic matrix, where for all
i ∈ S,
Denote by μQ the Markov chain field on the
tree T determined by Q and distribution q.
Then,
Let
By (4), (11), (15), and (17)–(19), we have
Hence, by using Lemma 1, it follows from (20) that there exists
A(λ) ∈ F,
μP(A(λ)) = 1, such that
Taking λ ∈ (0,ak) and noting that
we have by (21),
Hence, (16) holds. █
Lemma 3: If there exist positive integers
N*,N*, and d such that N*
≤ Nn ≤ N* when n
≥ d, then
Proof: It is easy to see that there exist finite numbers
a and b and finite random variables α(ω) and
β(ω) such that
Hence,
This together with Lemma 2 implies (23) evidently. In a similar way,
we can verify (24)–(26) by using inequalities (27) and (28).
█
Lemma 4: Let 0 < p < 1 and
{cn,n ≥ 1} be a sequence of
nonnegative real numbers. If there exists a sequence of real numbers
{αk,k ≥ 1} such that 0 <
αk < p,αk
→ p, and
then
if there exists a sequence of real numbers
{βk,k ≥ 1} such that p <
βk < 1,βk →
p, and
then
Proof: By (29),
Hence,
since
It is easy to see that
Inequality (30) follows from (31) and (32) directly. In a similar
way, we can verify the second part of the lemma. █
3. MAIN RESULTS
Theorem 1: If there exist positive integers
N*, N*, and d such that
N* ≤ Nn ≤
N* when n ≥ d, then for all k,l ∈
S,
Proof: Let 0 < λ < 1 be a constant and D
= (D(j|i)), i,j
∈ S, be another stochastic matrix, where
Denote by μD the Markov chain field on tree
T determined by D and the distribution q.
Then,
By (23) and Lemma 1, there exist
A(k,l,λ) ∈ F and
μP(A(k,l,λ)) =
1, such that
Take αi ∈
(0,P(l|k)) and
βi ∈
(P(l|k),1),i = 1,2,…,
such that αi →
P(l/k),βi →
P(l/k)(i → ∞). Let
.
Then, by
(34) and (35), we have for all i ≥ 1,
By Lemma 4, it follows from (36) that
Let
.
In a similar way, it can be shown that
The theorem follows because
μP(A*(k,l)
∩ μP(A*(k,l)) =
1. █
Corollary 1: Under the conditions of Theorem 1, we
have
In particular, if T is a Bethe tree
TB,N or a Cayley tree
TC,N, then
Proof: The corollary follows from Theorem 1 and (28)
directly. █
Theorem 2: If T is a Bethe tree
TB,N or a Cayley tree
TC,N, then for all k
∈ S,
where π = (π(1),…,π(b)) is the stationary
distribution determined by P.
Proof: Let
By (39), μP(H) = 1. Let ω
∈ H. Then,
where αn(j,k,ω) →
0(n → ∞). Adding the b equalities for
j = 1,2,…,b and using (13), we have
It follows from (42) and (12) that
Multiplying the kth equality of (43) by
P(i|k)(k =
1,2,…,b), adding them together, and using (43) once
again, we obtain
where P(h)(i|
j) (h is a positive integer) is the
hth-order transition probability determined by stochastic
matrix (P(j|i)). By induction, we
have
Let
By (44) and (12), we have
Since limh
P(h+1)(i| j) =
π(i),
Equation (40) follows from (45)–(47), and (41) follows from
(40) and (23)–(26) directly. █
Corollary 2: Under the conditions of Theorem 2, we
have
Proof: Equation (48) follows from (33) and (41), and (49)
follows from (48) and (40). █
Theorem 3: Let T be a Bethe tree
TB,N or a Cayley tree
TC,N, and f
(x,y) be a function defined on
S2. Set
Then,
Proof: By (50) and (10), we have
The theorem follows from (52) and (48) directly. █
Let μ be a probability measure on (Ω,F) and let
fn(ω) is called the entropy density
on subgraph T(n) with respect to μ. If
μ = μP, then by (4) we have
The convergence of fn(ω) to a
constant in a sense (L1 convergence, convergence in
probability, or a.s. convergence) is called the Shannon–McMillan
theorem or the asymptotic equipartition property (AEP) in formation
theory. By using Theorem 3, we can easily obtain the
Shannon–McMillan theorem for Markov chain fields on the Bethe
tree TB,N and the Cayley tree
TC,N with a.s. convergence.
Theorem 4: Let μP be a
Markov chain field on Bethe tree TB,N
or the Cayley tree TC,N, and
fn(ω) be defined by (53). Then,
Proof: Letting f (x,y) =
−ln P(y|x) in Theorem 3, the
proof follows from (51) directly. █
Remark: As we have mentioned in Section 1, Ye and Berger
have studied the Shannon–McMillan theorem for PPG-invariant
random field on trees, but the convergence in their results is only the
convergence in probability. They conjectured that these results also
hold with a.s. convergence. Since the Markov chain field is a
particular case of the PPG-invariant random fields, Theorem 4 partly
solved the conjecture of Ye and Berger.
