Báo cáo hóa học: " Research Article Some Shannon-McMillan Approximation Theorems for Markov Chain Field on the Generalized Bethe Tree"

Chia sẻ: Nguyen Minh Thang | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

54
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tuyển tập báo cáo các nghiên cứu khoa học quốc tế ngành hóa học dành cho các bạn yêu hóa học tham khảo đề tài: Research Article Some Shannon-McMillan Approximation Theorems for Markov Chain Field on the Generalized Bethe Tree

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo hóa học: " Research Article Some Shannon-McMillan Approximation Theorems for Markov Chain Field on the Generalized Bethe Tree"

Hindawi Publishing Corporation Journal of Inequalities and Applications Volume 2011, Article ID 470910, 18 pages doi:10.1155/2011/470910 Research Article Some Shannon-McMillan Approximation Theorems for Markov Chain Field on the Generalized Bethe Tree Kangkang Wang1 and Decai Zong2 1 School of Mathematics and Physics, Jiangsu University of Science and Technology, Zhenjiang 212003, China 2 College of Computer Science and Engineering, Changshu Institute of Technology, Changshu 215500, China Correspondence should be addressed to Wang Kangkang, wkk.cn@126.com Received 26 September 2010; Accepted 7 January 2011 Academic Editor: Jozef Bana´ s ´ Copyright q 2011 W. Kangkang and D. Zong. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. A class of small-deviation theorems for the relative entropy densities of arbitrary random ﬁeld on the generalized Bethe tree are discussed by comparing the arbitrary measure μ with the Markov measure μQ on the generalized Bethe tree. As corollaries, some Shannon-Mcmillan theorems for the arbitrary random ﬁeld on the generalized Bethe tree, Markov chain ﬁeld on the generalized Bethe tree are obtained. 1. Introduction and Lemma Let T be a tree which is inﬁnite, connected and contains no circuits. Given any two vertices x / y ∈ T , there exists a unique path x x1 , x2 , . . . , xm y from x to y with x1 , x2 , . . . , xm distinct. The distance between x and y is deﬁned to m − 1, the number of edges in the path connecting x and y. To index the vertices on T , we ﬁrst assign a vertex as the “root” and label it as O. A vertex is said to be on the nth level if the path linking it to the root has n edges. The root O is also said to be on the 0th level. Deﬁnition 1.1. Let T be a tree with root O, and let {Nn , n ≥ 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 1th level. For example, when N1 N 1 ≥ 2 and Nn N n ≥ 2 , T is rooted Bethe tree TB,N on which each vertex has N 1 neighboring
2 Journal of Inequalities and Applications Level 3 (2,2) (2,5) Level 2 (1,3) (1,1) (1,2) Level 1 (0,1) Root Figure 1: Bethe tree TB,2 . vertices see Figure 1, TB,2 , and when Nn N ≥ 1 n ≥ 1 , T is 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 Bethe 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 j th 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, n n n T N0 · · · Nm N1 · · · Nm . 1 1.1 m0 m1 ST , ω Let S {s0 , s1 , s2 , . . .}, Ω ω · ∈ Ω, where ω · is a function deﬁned on T and taking values in S, and let F be the smallest Borel ﬁeld containing all cylinder sets in Ω. Let X {Xt , t ∈ T } be the coordinate stochastic process deﬁned on the measurable space Ω, F ; that is, for any ω {ω t , t ∈ T }, deﬁne Xt ω ωt, t ∈ T. 1.2 ¸ n n n n XT n μ XT xT μ xT Xt , t ∈ T , . 1.3 Now we give a deﬁnition of Markov chain ﬁelds on the tree T by using the cylinder distribution directly, which is a natural extension of the classical deﬁnition of Markov chains see 1 . Deﬁnition 1.2. Let Q Q j | i . One has a strictly positive stochastic matrix on S, q q s0 , q s1 , q s2 . . . a strictly positive distribution on S, and μQ a measure on Ω, F . If μQ x0,1 q x0,1 , 1.4 n−1 N0 ···Nm Nm 1 i n μQ xT q x0,1 q xm | xm,i , n ≥ 1. 1,j m0 i1 j Nm i−1 1 1
Journal of Inequalities and Applications 3 Then μQ will be called a Markov chain ﬁeld on the tree T determined by the stochastic matrix Q and the distribution q. Let μ be an arbitrary probability measure deﬁned as 1.3 , denote 1 n log μ X T fn ω − . 1.5 n T n fn ω is called the entropy density on subgraph T with respect to μ. If μ μQ , then by 1.4 , 1.5 we have ⎡ ⎤ n−1 N0 ···Nm Nm 1 i 1 ⎣log q X0,1 | Xm,i ⎦. fn ω − log q Xm 1.6 1,j n T m0 i1 j Nm i−1 1 1 The convergence of fn ω in a sense L1 convergence, convergence in probability, or almost sure convergence is called the Shannon-McMillan theorem or the entropy theorem or the asymptotic equipartition property AEP in information theory. The Shannon-McMillan theorem on the Markov chain has been studied extensively see 2, 3 . In the recent years, with the development of the information theory scholars get to study the Shannon-McMillan theorems for the random ﬁeld on the tree graph see 4 . The tree models have recently drawn increasing interest from specialists in physics, probability and information theory. Berger and Ye see 5 have studied the existence of entropy rate for G-invariant random ﬁelds. Recently, Ye and Berger see 6 have also studied the ergodic property and Shannon- McMillan theorem for PPG-invariant random ﬁelds on trees. But their results only relate to the convergence in probability. Yang et al. 7–9 have recently studied a.s. convergence of Shannon-McMillan theorems, the limit properties and the asymptotic equipartition property for Markov chains indexed by a homogeneous tree and the Cayley tree, respectively. Shi and Yang see 10 have investigated some limit properties of random transition probability for second-order Markov chains indexed by a tree. In this paper, we study a class of Shannon-McMillan random approximation theorems for arbitrary random ﬁelds on the generalized Bethe tree by comparison between the arbitrary measure and Markov measure on the generalized Bethe tree. As corollaries, a class of Shannon-McMillan theorems for arbitrary random ﬁelds and the Markov chains ﬁeld on the generalized Bethe tree are obtained. Finally, some limit properties for the expectation of the random conditional entropy are discussed. Lemma 1.3. Let μ1 and μ2 be two probability measures on Ω, F , D ∈ F, and let {τn , n ≥ 0} be a positive-valued stochastic sequence such that τn > 0, μ1 -a.s. ω ∈ D, lim inf 1.7 Tn n then n μ2 X T 1 ≤ 0, μ1 -a.s. ω ∈ D. lim sup log 1.8 n → ∞ τn μ1 X T n
4 Journal of Inequalities and Applications n In particular, let τn |T |, then n μ2 X T 1 ≤ 0, μ1 -a.s. ω ∈ D. lim sup log 1.9 n T μ1 X T n n→∞ Proof see 11 . Let n μ XT 1 1.10 ϕ μ | μQ . lim sup log n T μQ X T n n→∞ ϕ μ | μQ is called the sample relative entropy rate of μ relative to μQ . ϕ μ | μQ is also called the asymptotic logarithmic likelihood ratio. By 1.9 n μ XT 1 1.11 ϕ μ | μQ ≥ lim inf ≥ 0, μ-a.s. log n T μQ X T n n→∞ Hence ϕ μ | μQ can be look on as a type of measures of the deviation between the arbitrary random ﬁelds and the Markov chain ﬁelds on the generalized Bethe tree. 2. Main Results Theorem 2.1. Let X {Xt , t ∈ T } be an arbitrary random ﬁeld on the generalized Bethe tree. fn ω Q and ϕ μ | μQ are, respectively, deﬁned as 1.5 and 1.10 . Denote α ≥ 0, Hm Xm 1,j | Xm,i the random conditional entropy of Xm 1,j relative to Xm,i on the measure μQ , that is, Q H m Xm | Xm,i − q xm | Xm,i log q xm | Xm,i . 1,j 1,j 1,j 2.1 xm 1,j ∈S Let Dc ω : ϕ μ | μQ ≤ c , 2.2 n−1 N0 ···Nm Nm 1 i 1 −α EQ log2 q Xm bα | Xm,i · q Xm | Xm,i | Xm,i < ∞, lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 2.3
Journal of Inequalities and Applications 5 when 0 ≤ c ≤ α2 bα /2, ⎧ ⎫ ⎨ ⎬ n−1 N0 ···Nm Nm 1 i 1 Q fn ω − H m Xm | Xm,i lim sup 1,j ⎩ ⎭ n T n→∞ m0 i1 j Nm i−1 1 1 2.4 ≤ 2cbα , μ-a.s. ω ∈ D c . ⎧ ⎫ ⎨ ⎬ n−1 N0 ···Nm Nm 1 i 1 Q lim inf fn ω − H m Xm | Xm,i 1,j n→∞ ⎩ ⎭ Tn m0 i1 j Nm i−1 1 1 2.5 ≥ − 2cbα − c, μ-a.s. ω ∈ D c . In particular, ⎡ ⎤ n−1 N0 ···Nm Nm 1 i 1 Q lim ⎣fn ω − | Xm,i ⎦ Hm Xm 1,j n T n→∞ m0 i1 j Nm i−1 1 1 2.6 0, μ-a.s. ω ∈ D 0 , where log is the natural logarithmic, EQ is expectation with respect to the measure μQ . Proof. Let Ω, F, μ be the probability space we consider, λ an arbitrary constant. Deﬁne −λ 1−λ EQ q Xm | Xm,i | Xm,i xm,i q xm | xm,i ; 2.7 1,j 1,j xm 1,j ∈S denote 1−λ n−1 N0 ···Nm Nm 1 i q xm | xm,i 1,j n μQ λ, xT q x0,1 . 2.8 −λ i−1 1 EQ q Xm | Xm,i | Xm,i xm,i m0 i1 j Nm 1,j 1
6 Journal of Inequalities and Applications We can obtain by 2.7 , 2.8 that in the case n ≥ 1, n μQ λ; xT xLn ∈S 1−λ n−1 N0 ···Nm Nm 1 i q xm | xm,i 1,j q x0,1 −λ i−1 1 EQ q Xm | Xm,i | Xm,i xm,i m0 i1 j Nm xLn ∈S 1,j 1 1−λ N0 ···Nn−1 Nn i q xn,j | xn−1,i n−1 μQ λ; xT −λ 1 EQ q Xn,j | Xn−1,i | Xn−1,i xn−1,i i1 j Nn i−1 xLn ∈S 2.9 1−λ N0 ···Nn−1 Nn i q xn,j | xn−1,i n−1 μQ λ; xT −λ j Nn i−1 1 xn,j ∈S EQ q xn,j | xn−1,i | Xn−1,i xn−1,i i1 −λ EQ q Xn,j | Xn−1,i | Xn−1,i xn−1,i N0 ···Nn−1 Nn i n−1 T μQ λ; x −λ EQ q xn,j | xn−1,i | Xn−1,i xn−1,i i1 j Nn i−1 1 n−1 μQ λ; xT , μQ λ; xT 0 q x0,1 1. 2.10 x0,1 ∈S xL0 ∈S n n Therefore, μQ λ, xT 0, 1, 2, . . . are a class of consistent distributions on ST . Let ,n n μQ λ, X T , 2.11 Un λ, ω μ XT n then {Un λ, ω , Fn , n ≥ 1} is a nonnegative supermartingale which converges almost surely see 12 . By Doob’s martingale convergence theorem we have lim Un λ, ω U∞ λ, ω < ∞. μ-a.s. 2.12 n→∞ Hence by 1.3 , 1.9 , 2.9 , and 2.11 we get 1 log Un λ, ω ≤ 0. μ-a.s. lim sup 2.13 n T n→∞
Journal of Inequalities and Applications 7 By 1.4 , 2.8 , and 2.11 , we have 1 log Un λ, ω n T n−1 N0 ···Nm Nm 1 i 1 −λ −λ log q Xm | Xm,i − log EQ q Xm | Xm,i | Xm,i 1,j 1,j n T m0 i1 j Nm i−1 1 1 n μQ X T 1 . log n T μ XT n 2.14 By 1.10 , 2.2 , 2.13 , and 2.14 we have n−1 N0 ···Nm Nm 1 i 1 −λ −λ log q Xm | Xm,i − log EQ q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 ≤ ϕ μ | μQ ≤ c, μ-a.s. ω ∈ D c . 2.15 By 2.15 we have n−1 N0 ···Nm Nm 1 i 1 −λ log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 n−1 N0 ···Nm Nm 1 i 1 −λ ≤ lim sup log EQ q Xm | Xm,i | Xm,i 1,j T n n→∞ m0 i1 j Nm i−1 1 1 −EQ −λ log q Xm | Xm,i | Xm,i c, μ-a.s. ω ∈ D c . 1,j 2.16 By the inequality 12 x−λ − 1 λ log x 2 x−|λ| , λ log x ≤ 0 ≤ x ≤ 1, 2.17 2 log x ≤ x − 1 x ≥ 0 and 2.16 , 2.17 , 2.3 , we have in the case of |λ| < α,
8 Journal of Inequalities and Applications n−1 N0 ···Nm Nm 1 i 1 −λ log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 n−1 N0 ···Nm Nm 1 i 1 −λ ≤ lim sup EQ q Xm | Xm,i | Xm,i − 1 1,j n T n→∞ m0 i1 j Nm i−1 1 1 −EQ − λ log q Xm | Xm,i | Xm,i c 1,j n−1 N0 ···Nm Nm 1 i 1 EQ λ2 log2 q Xm ≤ lim sup | Xm,i 1,j 2Tn n→∞ m0 i1 j Nm i−1 1 1 −|λ| ·q X m | Xm,i | Xm,i c 1,j n−1 N0 ···Nm Nm 1 i λ2 −α EQ log2 q Xm ≤ lim sup 1,j | Xm,i · q Xm | Xm,i | Xm,i 1,j 2Tn n→∞ m0 i1 j Nm i−1 1 1 12 c λ bα c. μ-a.s. ω ∈ D c . 2 2.18 When 0 < λ < α, we get by 2.18 n−1 N0 ···Nm Nm 1 i 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 c 1 ≤ λ bα , μ-a.s. ω ∈ D c . λ 2 2.19 Let g λ 1/2 λbα c/λ, in the case 0 < c ≤ α2 bα /2, then it is obvious g λ attains, at λ 2c /bα , its smallest value g 2c /bα 2cbα on the interval 0, α . We have n−1 N0 ···Nm Nm 1 i 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 ≤ 2cbα , μ-a.s. ω ∈ D c . 2.20
Journal of Inequalities and Applications 9 When c 0, we select 0 < λi < α such that λi → 0 i → ∞ . Hence for all i, it follows from 2.19 that n−1 N0 ···Nm Nm 1 i 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 ≤ 0, μ-a.s. ω ∈ D 0 . 2.21 It is easy to see that 2.20 also holds if c 0 from 2.21 . Analogously, when −α < λ < 0, it follows from 2.18 if 0 ≤ c ≤ α2 bα /2, n−1 N0 ···Nm Nm 1 i 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim inf 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 ≥ − 2cbα , μ-a.s. ω ∈ D c . 2.22 Setting λ 0 in 2.14 , by 2.14 we have n μQ X T 1 1 log Un 0, ω ≤ 0, μ-a.s. lim sup lim sup log 2.23 n n T T μ XT n n→∞ n→∞ Noticing Q H m Xm | Xm,i EQ − log q Xm | Xm,i | Xm,i . 2.24 1,j 1,j By 1.4 , 1.5 , 2.20 , and 2.23 , we obtain ⎡ ⎤ n−1 N0 ···Nm Nm 1 i 1 Q lim sup⎣fn ω − ⎦ H m Xm 1,j , Xm,i n T n→∞ m0 i1 j Nm i−1 1 1 n μQ X T 1 ≤ lim sup log n T μ XT n n→∞ 2.25 n−1 N0 ···Nm Nm 1 i 1 lim sup n T n→∞ m0 i1 j Nm i−1 1 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i 1,j 1,j ≤ 2 c bα , μ-a.s. ω ∈ D c .
10 Journal of Inequalities and Applications Hence 2.4 follows from 2.25 . By 1.4 , 1.5 , 1.10 , 2.2 , and 2.22 , we have ⎡ ⎤ n−1 N0 ···Nm Nm 1 i 1 Q lim inf⎣fn ω − ω⎦ Hm n T n→∞ m0 i1 j Nm i−1 1 1 ⎡ ⎤ n μQ X T ⎢ ⎥ 1 ≥ lim inf log⎣ ⎦ n T μ XT n n→∞ 2.26 n−1 N0 ···Nm Nm 1 i 1 lim inf n T n→∞ m0 i1 j Nm i−1 1 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i 1,j 1,j ≥ −ϕ μ | μQ − 2cbα ≥ − 2cbα − c, μ-a.s. ω ∈ D c . Therefore 2.5 follows from 2.26 . Set c 0 in 2.4 and 2.5 , 2.6 holds naturally. Corollary 2.2. Let X {Xt , t ∈ T } be the Markov chains ﬁeld determined by the measure μQ on the Q generalized Bethe tree T · fn ω , bα are, respectively, deﬁned as 1.6 and 2.3 , and Hm Xm 1,j | Xm,i is deﬁned by 2.1 . Then ⎧ ⎫ ⎨ ⎬ n−1 N0 ···Nm Nm 1 i 1 Q lim fn ω − Hm Xm | Xm,i 0. μQ -a.s. 2.27 1,j n → ∞⎩ ⎭ Tn m0 i1 j Nm i−1 1 1 Proof. We take μ ≡ μQ , then ϕ μ | μQ ≡ 0. It implies that 2.2 always holds when c 0. Therefore D 0 Ω holds. Equation 2.27 follows from 2.3 and 2.6 . 3. Some Shannon-McMillan Approximation Theorems on the Finite State Space Corollary 3.1. Let X {Xt , t ∈ T } be an arbitrary random ﬁeld which takes values in the alphabet S {s1 , . . . , sN } on the generalized Bethe tree. fn ω , ϕ μ | μQ and D c are deﬁned as 1.5 , Q 1.10 , and 2.2 . Denote 0 ≤ α < 1, 0 ≤ c ≤ 2Nα2 / 1 − α e 2 . Hm Xm 1,j | Xm,i is deﬁned as above. Then ⎡ ⎤ n−1 N0 ···Nm Nm 1 i 1 Q lim sup⎣fn ω − | Xm,i ⎦ H m Xm 1,j n T n→∞ m0 i1 j Nm i−1 1 1 3.1 √ −1 2e ≤ 2cN, μ-a.s. ω ∈ D c , 1−α
Journal of Inequalities and Applications 11 ⎡ ⎤ 1 n−1 N0 ···Nm Nm 1 i Q lim inf⎣fn ω − | Xm,i ⎦ Hm Xm 1,j Tn m0 i1 j n→∞ Nm i−1 1 3.2 1 2e−1 √ ≥− 2cN − c, μ-a.s. ω ∈ D c . 1−α Proof. Set 0 < α < 1 we consider the function log x 2 x1−α , 0. φx 0 < x ≤ 1, 0 < α < 1 Set φ 0 3.3 Then x−α 2 log x 2 φx log x 1−α . 3.4 e2/ α−1 . Accordingly it can be obtained that Let φ x 0 thus x 2 2 φ e2/ α−1 e−2 . max φ x , 0 ≤ x ≤ 1 3.5 α−1 By 2.3 and 3.5 we have n−1 N0 ···Nm Nm 1 i 1 −α EQ log2 q Xm bα | Xm,i · q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 n−1 N0 ···Nm Nm 1 i 1 1−α log2 q xm | Xm,i · q xm | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 i−1 1 xm 1,j ∈S j Nm 1 n−1 N0 ···Nm Nm 1 i sN 2 1 2 e−2 ≤ lim sup α−1 n T n→∞ i−1 1 xm s1 m0 i1 j Nm 1,j 1 n T −1 2 2 2 2 e−2 · lim sup e−2 < ∞. N N α−1 α−1 n T n→∞ 3.6 Therefore, 2.3 holds naturally. By 2.18 and 3.6 we have n−1 N0 ···Nm Nm 1 i 1 −λ log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 2e−2 ≤ Nλ2 c, μ-a.s. ω ∈ D c . 2 α−1 3.7
12 Journal of Inequalities and Applications In the case of 0 < λ < α, by 3.7 we have n−1 N0 ···Nm Nm 1 i 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 2e−2 c ≤ Nλ , μ-a.s. ω ∈ D c . λ 2 α−1 3.8 2λNe−2 / α − 1 2 c/λ, in the case 0 < c ≤ 2Nα2 / 1 − α e 2 , then it is Let g λ obvious g λ attains, at λ 1 − α e c/2N , its smallest value g 1 − α e c/2N √ 2e−1 2cN/ 1 − α on the interval 0, α . That is n−1 N0 ···Nm Nm 1 i 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim sup 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 2e−1 √ ≤ 2cN, μ-a.s. ω ∈ D c . 1−α 3.9 By the similar means of reasoning 2.21 , it can be concluded that 3.9 also holds when c 0. According to the methods of proving 2.4 , 3.1 follows from 1.5 , 2.23 , and 3.9 . Similarly, when −α < λ < 0, 0 ≤ c ≤ 2Nα2 / 1 − α e 2 , by 3.7 we have n−1 N0 ···Nm Nm 1 i 1 − log q Xm | Xm,i − EQ log q Xm | Xm,i | Xm,i lim inf 1,j 1,j n T n→∞ m0 i1 j Nm i−1 1 1 2e−1 √ ≥− 2cN, μ-a.s. ω ∈ D c . 1−α 3.10 Imitating the proof of 2.5 , 3.2 follows from 1.5 , 1.10 , 2.2 , and 3.10 . Corollary 3.2 see 9 . Let X {Xt , t ∈ T } be the Markov chains ﬁeld determined by the measure Q μQ on the generalized Bethe tree T · fn ω is deﬁned as 1.6 , and Hm Xm 1,j | Xm,i is deﬁned as 2.1 . Then ⎧ ⎫ ⎨ ⎬ n−1 N0 ···Nm Nm 1 i 1 Q lim fn ω − H m Xm | Xm,i 0. μQ -a.s. 3.11 1,j n → ∞⎩ ⎭ Tn m0 i1 j Nm i−1 1 1
Journal of Inequalities and Applications 13 Proof. By 3.1 and 3.2 in Corollary 3.1, we obtain that when c 0, ⎧ ⎫ ⎨ ⎬ n−1 N0 ···Nm Nm 1 i 1 Q fn ω − Hm Xm | Xm,i 0, μ-a.s. ω ∈ D 0 . lim 1,j n → ∞⎩ ⎭ n T m0 i1 j Nm i−1 1 1 3.12 Set μ ≡ μQ , then ϕ μ | μQ ≡ 0. It implies 2.2 always holds when c 0. Therefore D 0 Ω holds. Equation 3.11 follows from 3.12 . Corollary 3.3. Under the assumption of Corollary 3.1, if μ μQ , then ⎧ ⎫ ⎨ ⎬ n−1 N0 ···Nm Nm 1 i 1 Q fn ω − Hm Xm | Xm,i 0. μ-a.s. lim 3.13 1,j n → ∞⎩ ⎭ n T m0 i1 j Nm i−1 1 1 Proof. It can be obtained that ϕ μ | μQ ≡ 0, μ a.s. holds if μ μQ see Gray 1990 13 , therefore μ D 0 1. Equation 3.13 follows from 3.12 . Let X {Xt , t ∈ T } be a Markov chains ﬁeld on the generalized Bethe tree with the initial distribution and the joint distribution with respect to the measure μP as follows: μP x0,1 p x0,1 , 3.14 n−1 N0 ···Nm Nm 1 i n μP xT p x0,1 p xm | xm,i , n ≥ 1, 3.15 1,j m0 i1 j Nm i−1 1 1 where P p j | i is a strictly positive stochastic matrix on S, p p s0 , p s1 , p s2 . . . is a strictly positive distribution. Therefore, the entropy density of X {Xt , t ∈ T } with respect to the measure μP is ⎡ ⎤ n−1 N0 ···Nm Nm 1 i 1 ⎣log p X0,1 | Xm,i ⎦. fn ω − log p Xm 3.16 1,j n T m0 i1 j Nm i−1 1 1 Let the initial distribution and joint distribution of X {Xt , t ∈ T } with respect to the measure μQ be deﬁned as 1.4 and 1.5 , respectively. We have the following conclusion. Corollary 3.4. Let X {Xt , t ∈ T } be a Markov chains ﬁeld on the generalized Bethe tree T whose initial distribution and joint distribution with respect to the measure μP and μQ are deﬁned by 3.14 , 3.15 and 1.4 , 1.5 , respectively. fn ω is deﬁned as 3.16 . If p l |h −q l |h ≤ c, 3.17 q l|h h∈S l∈S
14 Journal of Inequalities and Applications then ⎡ ⎤ n−1 N0 ···Nm Nm 1 i 1 Q lim sup⎣fn ω − | Xm,i ⎦ Hm Xm 1,j n T n→∞ m0 i1 j Nm i−1 1 3.18 1 2e−1 √ ≤ 2cN, μP -a.s. 1−α ⎡ ⎤ 1 n−1 N0 ···Nm Nm 1 i Q lim inf⎣fn ω − | Xm,i ⎦ H m Xm 1,j Tn m0 i1 j n→∞ Nm i−1 1 3.19 1 √ −1 2e ≥− 2cN − c. μP -a.s, 1−α Proof. Let μ μP in Corollary 3.1, and by 1.5 , 3.15 we get 3.16 . By the inequalities log x ≤ x − 1 x > 0 , a ≤ a , 3.17 , and 1.10 , we obtain ϕ μP | μQ n μP X T 1 lim sup log n T μQ X T n n→∞ N0 ···Nm Nm 1 i n−1 p X0,1 p Xm | Xm,i 1,j 1 m0 i1 j Nm 1 i−1 1 lim sup log N0 ···Nm Nm 1 i n−1 n T q X0,1 q Xm | Xm,i n→∞ 1,j m0 i1 j Nm 1 i−1 1 n−1 N0 ···Nm Nm 1 i p Xm | Xm,i p X0,1 1 1 1,j ≤ lim sup log lim sup log q X0,1 n n T T q Xm | Xm,i n→∞ n→∞ 1,j m0 i1 j Nm i−1 1 1 n−1 N0 ···Nm Nm 1 i p l|h 1 ≤ lim sup δh Xm,i δl Xm log 1,j q l|h n T n→∞ m0 i1 j Nm i−1 1 h∈S l∈S 1 n−1 N0 ···Nm Nm 1 i p l|h 1 ≤ lim sup δh Xm,i δl Xm −1 1,j q l|h n T n→∞ m0 i1 j Nm i−1 1 h∈S l∈S 1 n T −1p l | h −q l | h ≤ lim sup q l|h n T n→∞ h∈S l∈S p l |h −q l |h ≤ . q l|h h∈S l∈S 3.20 By 3.17 and 3.20 we have ϕ μP | μQ ≤ c, a.s. 3.21 It follows from 2.2 and 3.21 that D c Ω; therefore 3.18 , 3.19 follow from 3.1 , 3.2 .
Journal of Inequalities and Applications 15 4. Some Limit Properties for Expectation of Random Conditional Entropy on the Finite State Space n Lemma 4.1 see 8 . Let X T {Xt , t ∈ T n } be a Markov chains ﬁeld deﬁned on a Bethe tree n TB,N , Sn k, ω be the number of k in the set of random variables X T {Xt , t ∈ T n }. then for all k ∈ S, Sn k , ω πk μQ -a.s, lim 4.1 Tn n where π π 1 ,...,π N is the stationary distribution determined by Q. n Theorem 4.2. Let X T {Xt , t ∈ T n } be a Markov chains ﬁeld deﬁned on a Bethe tree TB,N , and Q let Hm Xm 1,j | Xm,i be deﬁned as above. Then ⎡ ⎤ n−1 N 1 N m−1 N1 Ni 1 Q Q ⎣ | Xm,i ⎦ H0 X1,i | X0,1 H m Xm lim 1,j n T n i1 m1 i1 j N i−1 1 4.2 − π k q l | k log q l | k , μQ -a.s. k ∈S l∈S Proof. Noticing now N1 N 1, for all n ≥ 2, Nn N , that therefore we have n−1 N 1 N m−1 N1 Ni Q Q H0 X1,i | X0,1 H m Xm | Xm,i 1,j i1 m1 i1 j N i−1 1 N1 − EQ log q X1,i | X0,1 | X0,1 i1 n−1 N 1 N m−1 Ni − EQ log q Xm | Xm,i | Xm,i 1,j m1 i1 j N i−1 1 N1 − q x1,i | X0,1 log q x1,i | X0,1 i 1 x1,i ∈S n−1 N 1 N m−1 Ni − q xm | Xm,i log q xm | Xm,i 1,j 1,j m1 i1 1 xm 1,j ∈S j N i−1
16 Journal of Inequalities and Applications N1 − δk X0,1 q l | k log q l | k i 1 k ∈S l∈S n−1 N 1 N m−1 Ni − δk Xm,i q l | k log q l | k m1 i1 j N i−1 1 k ∈S l∈S ⎡ ⎤ n−1 N 1 N m−1 N1 Ni q l | k log q l | k ⎣ δk Xm,i ⎦ − δk X0,1 m0 i1 i1 k ∈S l∈S j N i−1 1 − q l | k log q l | k N Sn−1 k, ω δk X0,1 . k ∈S l∈S 4.3 n n−1 Noticing that limn → ∞ |T |/|T | N , by 4.3 we have ⎡ ⎤ n−1 N 1 N m−1 N1 Ni 1 Q Q ⎣ | Xm,i ⎦ H0 X1,i | X0,1 Hm Xm lim 1,j n T n i1 m1 i1 j N i−1 1 1 −lim q l | k log q l | k N Sn−1 k, ω δk X0,1 n T n k ∈S l∈S 4.4 1 − q l | k log q l | k lim Sn−1 k, ω n−1 T n k ∈S l∈S − π k q l | k log q l | k . k ∈S l∈S Equation 4.2 follows from 4.4 . n Theorem 4.3. Let X T {Xt , t ∈ T n } be a Markov chains ﬁeld deﬁned on a Bethe tree TB,N , Q Hm Xm 1,j | Xm,i deﬁned as above. Then ⎧ ⎫ ⎨N ⎬ n−1 N 1 N m−1 Ni 1 1 Q Q EQ H0 X1,i | X0,1 EQ Hm Xm | Xm,i lim 1,j ⎩i ⎭ n T n m1 i1 j N i−1 1 1 4.5 − q k q l | k log q l | k . μQ -a.s. k ∈S l∈S
Journal of Inequalities and Applications 17 Q Proof. By the deﬁnition of Hm Xm | Xm,i and properties of conditional expectation, we 1,j have n−1 N 1 N m−1 N1 Ni Q Q EQ H0 X1,i | X0,1 EQ Hm Xm | Xm,i 1,j i1 m1 i1 j N i−1 1 N1 − EQ EQ log q X1,i | X0,1 | X0,1 i1 n−1 N 1 N m−1 Ni − EQ EQ log q Xm | Xm,i | Xm,i 1,j m1 i1 j N i−1 1 N1 − EQ log q X1,i | X0,1 i1 n−1 N 1 N m−1 Ni − EQ log q Xm | Xm,i 1,j m1 i1 j N i−1 1 4.6 N1 − q x0,1 , x1,i log q x1,i | x0,1 i 1 x0,1 ∈S x1,i ∈S n−1 N 1 N m−1 Ni − q xm,i , xm log q xm | xm,i 1,j 1,j m1 i1 j N i−1 1 xm,i ∈S xm 1,j ∈S N1 − q k q l | k log q l | k i 1 k ∈S l∈S n−1 N 1 N m−1 Ni − q k q l | k log q l | k m1 i1 j N i−1 1 k ∈S l∈S n − q k q l | k log q l | k T −1 . k ∈S l∈S Accordingly we have by 4.6 ⎧ ⎫ ⎨N ⎬ n−1 N 1 N m−1 Ni 1 1 Q Q EQ H0 X1,i | X0,1 EQ Hm Xm | Xm,i lim 1,j ⎩i ⎭ n T n m1 i1 j N i−1 1 1 n T −1 4.7 − q k q l | k log q l | k lim n T n k ∈S l∈S − q k q l | k log q l | k , μQ -a.s. k ∈S l∈S Therefore 4.5 also holds.
18 Journal of Inequalities and Applications Acknowledgments The work is supported by the Project of Higher Schools’ Natural Science Basic Research of Jiangsu Province of China 09KJD110002 . The author would like to thank the referee for his valuable suggestions. Correspondence author: K. Wang, main research interest is strong limit theory in probability theory. D. Zong main research interest is intelligent algorithm. References 1 K. L. Chung, A Course in Probability Theory, Academic Press, New York, NY, USA, 2nd edition, 1974. 2 L. Wen and Y. Weiguo, “An extension of Shannon-McMillan theorem and some limit properties for nonhomogeneous Markov chains,” Stochastic Processes and their Applications, vol. 61, no. 1, pp. 129– 145, 1996. 3 W. Liu and W. Yang, “Some extensions of Shannon-McMillan theorem,” Journal of Combinatorics, Information & System Sciences, vol. 21, no. 3-4, pp. 211–223, 1996. 4 Z. Ye and T. Berger, Information Measures for Discrete Random Fields, Science Press, Beijing, China, 1998. 5 T. Berger and Z. X. Ye, “Entropic aspects of random ﬁelds on trees,” IEEE Transactions on Information Theory, vol. 36, no. 5, pp. 1006–1018, 1990. 6 Z. Ye and T. Berger, “Ergodicity, regularity and asymptotic equipartition property of random ﬁelds on trees,” Journal of Combinatorics, Information & System Sciences, vol. 21, no. 2, pp. 157–184, 1996. 7 W. Yang, “Some limit properties for Markov chains indexed by a homogeneous tree,” Statistics & Probability Letters, vol. 65, no. 3, pp. 241–250, 2003. 8 W. Yang and W. Liu, “Strong law of large numbers and Shannon-McMillan theorem for Markov chain ﬁelds on trees,” IEEE Transactions on Information Theory, vol. 48, no. 1, pp. 313–318, 2002. 9 W. Yang and Z. Ye, “The asymptotic equipartition property for nonhomogeneous Markov chains indexed by a homogeneous tree,” IEEE Transactions on Information Theory, vol. 53, no. 9, pp. 3275– 3280, 2007. 10 Z. Shi and W. Yang, “Some limit properties of random transition probability for second-order nonhomogeneous markov chains indexed by a tree,” Journal of Inequalities and Applications, vol. 2009, Article ID 503203, 2009. 11 W. Liu and W. Yang, “Some strong limit theorems for Markov chain ﬁelds on trees,” Probability in the Engineering and Informational Sciences, vol. 18, no. 3, pp. 411–422, 2004. 12 J. L. Doob, Stochastic Processes, John Wiley & Sons, New York, NY, USA, 1953. 13 R. M. Gray, Entropy and Information Theory, Springer, New York, NY, USA, 1990.