No CrossRef data available.
Article contents
SOME STRONG LIMIT THEOREMS FOR MARKOV CHAIN FIELDS ON TREES
Published online by Cambridge University Press: 01 July 2004
Abstract
In this article, we introduce the notion of the Markov chain fields on the generalized Bethe trees or generalized Cayley trees, and some strong limit theorems on the frequencies of states and ordered couples of states, including the Shannon–McMillan theorem on Bethe tree TB,N and Cayley tree TC,N, are obtained. In the proof, a new technique in the study of the strong limit theorem in probability theory is applied.
Information
- Type
- Research Article
- Information
- Probability in the Engineering and Informational Sciences , Volume 18 , Issue 3 , July 2004 , pp. 411 - 422
- Copyright
- © 2004 Cambridge University Press
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.
Bethe tree TB,2.
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.
References
REFERENCES
Benjamini, I. &
Peres, Y.
(1994).
Markov chains indexed by trees.
Annals of Probability
22:
219–243.Google Scholar
Berger, T. &
Ye, Z.
(1990).
Entropic aspects of random fields on trees.
IEEE Transactions on Information Theory
36(5):
1006–1018.Google Scholar
Feller, W.
(1968).
An introduction to probability theory and its applications,
Vol. 1, 3rd ed.
New York:
Wiley.
Liu, W. &
Yang, W. G.
(1995).
A limit theorem for the entropy density of nonhomogeneous Markov
information source.
Statistics and Probability Letters
22:
295–301.Google Scholar
Liu, W. &
Yang, W. G.
(1996).
An extension of Shannon–McMillan theorem and some limit
properties for nonhomogeneous Markov chains.
Stochastic Processes and Their Applications
61:
129–146.Google Scholar
Spitzer, F.
(1975).
Markov random fields on an infinite tree.
Annals of Probability
3:
387–398.Google Scholar
Ye, Z. &
Berger, T.
(1996).
Ergodic, regularity and asymptotic equipartition property of random
fields on trees.
Journal of Combinatorics, Information and System Sciences
21(2):
157–184.Google Scholar
Bethe tree TB,2.
You have
Access
- 4
- Cited by