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 Wang
1
and Decai Zong
2
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, [email protected]
Received 26 September 2010; Accepted 7 January 2011
Academic Editor: J
´
ozef 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 field on
the generalized Bethe tree are discussed by comparing the arbitrary measure μ with the Markov
measure μ
branches to the n 1th level. For example, when N
1
N 1 ≥ 2
and N
n
N n ≥ 2 , T is rooted Bethe tree T
B,N
on which each vertex has N 1 neighboring
2 Journal of Inequalities and Applications
Root
(0,1)
Level 2
Level 3
Level 1
(1,1)(1,2)
(1,3)
(2,2)(2,5)
Figure 1: Bethe tree T
B,2
.
vertices see Figure 1, T
B,2
,andwhenN
n
N ≥ 1 n ≥ 1, T is rooted Cayley tree T
C,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
m
.
1.1
Let S {s
0
,s
1
,s
2
, }, ΩS
T
, ω ω· ∈ Ω,whereω· is a function defined on T and
taking values in S,andletF be the smallest Borel field containing all cylinder sets in Ω.Let
X {X
t
,t ∈ T} be the c oordinate stochastic p rocess defined on the measurable space Ω,F;
that is, for any ω {ωt,t∈ T},define
X
t
ω
ω
t
,t∈ T. 1.2
X
T
1
,qs
2
a strictly positive distribution on S,andμ
Q
ameasureonΩ,F.If
μ
Q
x
0,1
q
x
0,1
,
μ
Q
x
T
n
q
x
0,1
Let μ be an arbitrary probability measure defined as 1.3,denote
f
n
ω
−
1
T
n
log μ
X
T
n
.
1.5
f
n
ω is called the entropy density on subgraph T
n
with respect to μ.Ifμ μ
Q
,thenby1.4,
1.5 we have
N
m1
i
jN
m1
i−11
log q
X
m1,j
| X
m,i
⎤
⎦
. 1.6
The convergence of f
n
ω in a sense L
1
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. I n the recent ye ars,
with the development of the information theory scholars get to study the Shannon-McMillan
theorems for the random field 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
fields. Recently, Ye and Berger see 6 have also studied the ergodic property and Shannon-
> 0,μ
1
-a.s. ω ∈ D, 1.7
then
lim sup
n →∞
1
τ
n
log
μ
2
X
T
n
μ
1
X
T
n
≤ 0,μ
1
-a.s. ω ∈ D. 1.8
4 Journal of Inequalities and Applications
In particular, let τ
n
Proof see 11.Let
ϕ
μ | μ
Q
lim sup
n →∞
1
T
n
log
μ
X
T
n
μ
Q
X
T
n
.
μ
Q
X
T
n
≥ 0,μ-a.s.
1.11
Hence ϕμ | μ
Q
can be look on as a type of measures of the deviation between the arbitrary
random fields and the Markov chain fields on the generalized Bethe tree.
2. Main Results
Theorem 2.1. Let X {X
t
,t∈ T} be an arbitrary random field on the generalized Bethe tree. f
n
ω
and ϕμ | μ
Q
are, respectively, defined as 1.5 and 1.10.Denoteα ≥ 0, H
Q
m
X
m1,j
| X
m,i
the
random conditional entropy of X
m1,j
| X
m,i
.
2.1
Let
D
c
ω : ϕ
μ | μ
Q
≤ c
, 2.2
b
α
lim sup
n →∞
1
T
n
· q
X
m1,j
| X
m,i
−α
| X
m,i
< ∞,
2.3
Journal of Inequalities and Applications 5
when 0 ≤ c ≤ α
2
b
α
/2,
lim sup
n →∞
⎧
⎨
⎩
f
n
ω
−
m,i
⎫
⎬
⎭
≤
2cb
α
,μ-a.s. ω ∈ D
c
.
2.4
lim inf
n →∞
⎧
⎨
⎩
f
n
ω
−
1
T
⎭
≥−
2cb
α
− c, μ-a.s. ω ∈ D
c
.
2.5
In particular,
lim
n →∞
⎡
⎣
f
n
ω
−
1
T
n
n−1
,
2.6
where log is the natural logarithmic, E
Q
is expectation with respect t o the measure μ
Q
.
Proof. Let Ω, F,μ be the probability space we consider, λ an arbitrary constant. Define
E
Q
qX
m1,j
| X
m,i
−λ
| X
m,i
x
m,i
x
m1,j
∈S
qx
m1,j
| x
jN
m1
i−11
qx
m1,j
| x
m,i
1−λ
E
Q
qX
m1,j
| X
m,i
−λ
| X
m,i
x
m,i
.
2.8
6 Journal of Inequalities and Applications
Wecanobtainby2.7, 2.8 that in the case n ≥ 1,
x
L
n
i
jN
m1
i−11
q
x
m1,j
| x
m,i
1−λ
E
Q
q
X
m1,j
| X
m,i
−λ
| X
m,i
x
m,i
μ
1−λ
E
Q
q
X
n,j
| X
n−1,i
−λ
| X
n−1,i
x
n−1,i
μ
Q
λ; x
T
n−1
N
0
···N
n−1
−λ
| X
n−1,i
x
n−1,i
μ
Q
λ; x
T
n−1
N
0
···N
n−1
i1
N
n
i
jN
n
i−11
E
Q
q
λ; x
T
n−1
,
2.9
x
L
0
∈S
μ
Q
λ; x
T
0
x
0,1
∈S
q
x
0,1
1. 2.10
n
λ, ω, F
n
,n≥ 1} is a nonnegative supermartingale which converges almost surely
see 12. By Doob’s martingale convergence theorem we have
lim
n →∞
U
n
λ, ω
U
∞
λ, ω
< ∞.μ-a.s. 2.12
Hence by 1.3, 1.9, 2.9,and2.11 we get
lim sup
n →∞
1
T
n
log U
n
0
···N
m
i1
N
m1
i
jN
m1
i−11
−λ log q
X
m1,j
| X
m,i
− log E
Q
qX
m1,j
| X
m,i
−λ
| X
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
−λ log q
X
m1,j
| X
m,i
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
−λ
log q
X
m1,j
| X
m,i
i1
N
m1
i
jN
m1
i−11
log E
Q
q
X
m1,j
| X
m,i
−λ
| X
m,i
−E
Q
−λ log q
X
m1,j
n →∞
1
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
−λ
log q
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
E
Q
qX
m1,j
| X
m,i
−λ
| X
m,i
− 1
−E
Q
N
m1
i
jN
m1
i−11
E
Q
λ
2
log
2
q
X
m1,j
| X
m,i
·qX
m1,j
| X
m,i
−|λ|
| X
m,i
Q
log
2
q
X
m1,j
|X
m,i
· q
X
m1,j
| X
m,i
−α
| X
m,i
c
1
2
λ
2
jN
m1
i−11
−
log q
X
m1,j
| X
m,i
− E
Q
log q
X
m1,j
| X
m,i
| X
m,i
≤
1
2
α
on the interval 0,α.Wehave
lim sup
n →∞
1
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
−
log q
When c 0, we select 0 <λ
i
<αsuch that λ
i
→ 0 i →∞.Henceforalli, it follows from
2.19 that
lim sup
n →∞
1
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
Analogously, when −α<λ<0, it follows from 2.18 if 0 ≤ c ≤ α
2
b
α
/2,
lim inf
n →∞
1
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
.
2.22
Setting λ 0in2.14,by2.14 we have
lim sup
n →∞
1
T
n
log U
n
0,ω
lim sup
n →∞
1
T
n
log
μ
Q
| X
m,i
.
2.24
By 1.4, 1.5, 2.20,and2.23,weobtain
lim sup
n →∞
⎡
⎣
f
n
ω
−
1
T
n
n−1
m0
N
0
···N
log
μ
Q
X
T
n
μ
X
T
n
lim sup
n →∞
1
T
n
n−1
m0
N
0
···N
m
≤
2cb
α
,μ-a.s.ω∈ D
c
.
2.25
10 Journal of Inequalities and Applications
Hence 2.4 follows from 2.25.By1.4, 1.5, 1.10, 2.2,and2.22,wehave
lim inf
n →∞
⎡
⎣
f
n
ω
−
1
T
n
n
log
⎡
⎢
⎣
μ
Q
X
T
n
μ
X
T
n
⎤
⎥
⎦
lim inf
n →∞
1
T
n
log q
X
m1,j
| X
m,i
| X
m,i
≥−ϕ
μ | μ
Q
−
2cb
α
≥−
2cb
α
− c, μ-a.s.ω∈ D
c
.
2.26
Therefore 2.5 follows from 2.26.Setc 0in2.4 and 2.5, 2.6 holds naturally.
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
H
Q
m
X
m1,j
| X
m,i
2
. H
Q
m
X
m1,j
| X
m,i
is defined as
above. Then
lim sup
n →∞
⎡
⎣
f
n
ω
−
1
T
n
n−1
m0
√
2cN, μ-a.s. ω ∈ D
c
,
3.1
Journal of Inequalities and Applications 11
lim inf
n →∞
⎡
⎣
f
n
ω
−
1
T
n
n−1
m0
N
0
.
3.2
Proof. Set 0 <α<1 we consider the function
φ
x
log x
2
x
1−α
, 0 <x≤ 1, 0 <α<1
Set φ
0
0
. 3.3
Then
φ
x
x
−α
2/α−1
2
α − 1
2
e
−2
.
3.5
By 2.3 and 3.5 we have
b
α
lim sup
n →∞
1
T
n
n−1
m0
N
0
···N
lim sup
n →∞
1
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
x
m1,j
∈S
m
i1
N
m1
i
jN
m1
i−11
s
N
x
m1,j
s
1
2
α − 1
2
e
−2
N
2
α −1
2
1
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
−λ
log q
X
3.7
12 Journal of Inequalities and Applications
In the case of 0 <λ<α,by3.7 we have
lim sup
n →∞
1
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
−
c
.
3.8
Let gλ2λNe
−2
/α −1
2
c/λ,inthecase0<c≤ 2Nα
2
/1 − αe
2
,thenitis
obvious gλ attains, at λ 1 − αe
c/2N, its smallest value g1 − αe
c/2N
2e
−1
√
2cN/1 − α on the interval 0,α.Thatis
lim sup
n →∞
1
T
n
X
m1,j
| X
m,i
| X
m,i
≤
2e
−1
1 − α
√
2cN, μ-a.s.ω∈ D
c
.
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,and3.9.
Similarly, when −α<λ<0, 0 ≤ c ≤ 2Nα
2
/1 − αe
2
,by3.7 we have
lim inf
| X
m,i
− E
Q
log q
X
m1,j
| X
m,i
| X
m,i
≥−
2e
−1
1 −α
√
2cN, μ-a.s.ω∈ D
c
.
3.10
Imitating the proof of 2.5, 3.2 follows from 1.5, 1.10, 2.2,and3.10.
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
H
Q
m
X
m1,j
| X
m,i
⎫
···N
m
i1
N
m1
i
jN
m1
i−11
H
Q
m
X
m1,j
| X
m,i
⎫
⎬
⎭
0,μ-a.s.ω∈ D
0
.
3.12
Set μ ≡ μ
0
···N
m
i1
N
m1
i
jN
m1
i−11
H
Q
m
X
m1,j
| X
m,i
⎫
⎬
⎭
0.μ-a.s. 3.13
Proof. It can be obtained that ϕμ | μ
Q
≡ 0,μ a.s. holds i f μ μ
Q
see Gray 1990 13,
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
p
x
m1,j
| x
m,i
,n≥ 1,
3.15
where P pj | i is a strictly positive stochastic matrix on S, p ps
0
,ps
1
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
log p
X
m1,j
| X
m,i
⎤
⎦
. 3.16
Let the initial distribution and joint distribution of X {X
t
,t∈ T} with respect to the measure
μ
l | h
≤ c, 3.17
14 Journal of Inequalities and Applications
then
lim sup
n →∞
⎡
⎣
f
n
ω
−
1
T
n
n−1
m0
N
0
···N
m
n →∞
⎡
⎣
f
n
ω
−
1
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
μ
P
| μ
Q
lim sup
n →∞
1
T
n
log
μ
P
X
T
n
μ
Q
X
T
n
lim sup
p
X
m1,j
| X
m,i
q
X
0,1
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
q
T
n
n−1
m0
N
0
···N
m
i1
N
m1
i
jN
m1
i−11
log
p
X
m1,j
| X
m,i
q
h∈S
l∈S
δ
h
X
m,i
δ
l
X
m1,j
log
p
l | h
q
l | h
≤ lim sup
n →∞
1
δ
l
X
m1,j
p
l | h
q
l | h
− 1
≤
h∈S
l∈S
lim sup
n →∞
T
n
.
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 DcΩ; 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
Lemma 4.1 see 8. Let X
T
n
{X
t
,t ∈ T
n
} be a Markov chains field defined on a Bethe tree
T
B,N
, S
n
k, ω be the number of k in the set of random variables X
T
n
{X
t
,t ∈ T
n
} be a Markov chains field defined on a Bethe tree T
B,N
,and
let H
Q
m
X
m1,j
| X
m,i
be defined as above. Then
lim
n
1
T
n
⎡
⎣
N1
i1
⎦
−
k∈S
l∈S
π
k
q
l | k
log q
l | k
,μ
Q
-a.s.
4.2
Proof. Noticing now N
1
N 1, for all n ≥ 2, N
n
N, that therefore we have
N1
i1
N1
i1
− E
Q
log q
X
1,i
| X
0,1
| X
0,1
n−1
m1
N1N
m−1
i1
Ni
jNi−11
− E
Q
0,1
−
n−1
m1
N1N
m−1
i1
Ni
jNi−11
x
m1,j
∈S
q
x
m1,j
| X
m,i
log q
x
m1,j
| X
m,i
i1
Ni
jNi−11
k∈S
l∈S
δ
k
X
m,i
q
l | k
log q
l | k
−
k∈S
l∈S
q
X
m,i
⎤
⎦
−
k∈S
l∈S
q
l | k
log q
l | k
NS
n−1
k, ω
δ
k
X
0,1
0,1
n−1
m1
N1N
m−1
i1
Ni
jNi−11
H
Q
m
X
m1,j
| X
m,i
⎤
⎦
−lim
n
1
T
l∈S
q
l | k
log q
l | k
lim
n
1
T
n−1
S
n−1
k, ω
−
k∈S
l∈S
π
defined as above. Then
lim
n
1
T
n
⎧
⎨
⎩
N1
i1
E
Q
H
Q
0
X
1,i
| X
0,1
l∈S
q
k
q
l | k
log q
l | k
.μ
Q
-a.s.
4.5
Journal of Inequalities and Applications 17
Proof. By the definition of H
Q
m
X
m1,j
| X
m,i
and properties of conditional expectation, we
have
N1
i1
X
m1,j
| X
m,i
N1
i1
− E
Q
E
Q
log q
X
1,i
| X
0,1
| X
0,1
n−1
log q
X
1,i
| X
0,1
n−1
m1
N1N
m−1
i1
Ni
jNi−11
− E
Q
log q
X
m1,j
| X
m,i
N1N
m−1
i1
Ni
jNi−11
x
m,i
∈S
x
m1,j
∈S
q
x
m,i
,x
m1,j
log q
x
m1,j
| x
m,i
−
k∈S
l∈S
q
k
q
l | k
log q
l | k
−
k∈S
l∈S
q
k
q
l | k
log q
i1
E
Q
H
Q
0
X
1,i
| X
0,1
n−1
m1
N1N
m−1
i1
Ni
jNi−11
E
Q
H
n
T
n
− 1
T
n
−
k∈S
l∈S
q
k
q
l | k
log q
l | k
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 fields 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.
Copyright: Tài liệu đại học ©