第6卷第3期2007年3月南阳师范学院学报
JournalofNanyangNormalUniversityVol.6No13
Mar.2007
有限非齐次马尔可夫链的强极限定理
王学武
(山东工商学院数学与信息科学学院,山东烟台2005)
摘 要:利用分析法研究了马氏链相对熵密度的若干极限性质,推广了Shannon2McMillan的极限定理,改进并推广了文
[1]～[3]的主要结果,建立了新的有限非齐次马尔可夫链的强极限定理.
关键词:强极限定理;马尔可夫链;熵;相对熵密度中图分类号:O211.4 文献标识码:A 文章编号:1671-6132(2007)03-0014-041 预备知识
信息论中的一个重要问题是相对熵密度的极限性质.Shannon于1948年最先证明了平稳遍历马氏链的相对熵密度fn(ω)依概率收敛于一常数,McMillan于1953年和Breiman于1957年分别证明了如果{Xn}是平稳遍历的,那么fn(ω)分别依L1收敛和a.s.收敛到某一常数.后来有一些作者讨论更为一般的情况见文[1]～[4].LiuWen和YangWeiguo于1996年证明了下面的定理:
[3]
定理A 设{Xn,n≥0}具有初始分布(1.6)与转移矩阵(1.7)的马氏链,如果存在常数α>0满足
n
tα(i,j)=limsup(1/n)
n→∞
n
m
k=1
∑g
k
2k
(i,j)pk(i,j)e
α|gk(i,j)|
<∞,(1.1)(1.2)(1.3)
则其中,
n→∞
lim[Fn(ω)-(1/n)
k=1
∑∑g
j=1
(Xk-1,j)pk(Xk-1,j)]=0, a.s.1
n
Fn(ω)=(1/n)
k=1
∑g
k
(Xk-1,Xk).
本文受到LiuWen的启发,在定理A的条件下,采用分析法得到理想的结果,见定理2.1.设{Xn,n≥0}是取值于状态空间S={1,2,…,m}上的一列随机变量,其联合分布为
(1.4)P(X0=x0,…,Xn=xn)=P(x0,…,xn)>0,xi∈S,0≤i≤n.
(1.5)令fn(ω)=-(1/n)lnp(X0,…,Xn),
则称fn(ω)为{Xn,n≥0}的相对熵密度.
设{Xn,n≥0}是取值于状态空间S={1,2,…,m}上的非齐次马尔可夫链,其初始分布和转移矩阵分别为
(p(1),p(2),…,p(m)),p(i)>0,i∈S,(1.6)
(1.7)Pn=(pn(i,j)),pn(i,j)>0,i,j∈S,n≥1,
其中pn(i,j)=P(Xn=jXn-1=i),n≥1,则
n
p(x0,…,xn)=p(x0)
k=1
∏p
n
k
(xk-1,xk),
k
(1.8)(1.9)
fn(ω)=-(1/n)[lnp(X0)+
k=1
∑lnp
(Xk-1,Xk)].
2 主要结果
定理211 设{Xn,n≥0}具有初始分布(1.6)与转移矩阵(1.7)的马氏链,如果存在常数α>0使
(1.1)成立,Fn(ω)如(1.3)定义,则有
n
n→∞
m
m
i
k-1
lim[Fn(ω)-(1/n)
k=1
∑∑∑max{δ(X
j=1
i=1
),δ.s.,j(Xk)}gk(i,j)pk(i,j)]=0 a(2.1)
收稿日期:2006-10-20
作者简介:王学武(1965-),黑龙冈人,副教授,从事不动点理论和概率极限理论的研究。
' 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第3期
n
王学武:有限非齐次马尔可夫链的强极限定理
n
k
m
m
i
k-1
・15・
即
n→∞
lim(1/n)[
k=1
∑g
(Xk-1,Xk)-
k=1
∑∑∑max{δ(X
j=1
i=1
),δj(Xk)}gk(i,j)pk(i,j)]=0,(2.2)
a.s..其中,δi(Xk-1),δj(Xk)是Kronecker函数.
证明我们考虑基本的概率空间([0,1),F,P),其中F是[0,1)区间上的Lebesgue可测集的全体,P
是Lebesgue测度.首先给出具有初始分布(1.6)和转移矩阵(1.7)的马氏链在此概率空间的一种实现.将区间[0,1)分成m个左闭右开区间
D1=[0,p(1)),D2=[p(1),p(1)+p(2)),…,Dm=[1-p(m),1)这些区间记为0阶区间,显然P(Dx0)=p(x0),x0=1,2,…,m,假定m个n-1阶区间{Dx0…xn-1,xi=1,2,…,m,0≤i≤n-1}已经定义,将左闭右开区间Dx0…xn-1按比例
p(xn-1,1)∶p(xn-1,2)∶…∶p(xn-1,m)分成m个右半开区间Dx0…xn-11,Dx0…xn-12,…,Dx0…xn-1m,从而对n≥1有
n
n
P(Dx0…xn)=p(x0)
k=1
∏p
k(xk-1,xk).(2.3)
对n≥1定义随机变量Xn(ω)∶[0,1)→S,使得Xn(ω)=xn,如果ω∈Dx0…xn,所以有{ω∶X0=x0,…,Xn=xn}=Dx0…xn,n
P(X0=x0,…,Xn=xn)=p(x0,…,xn)=p(x0)
k=1
∏p
k
(xk-1,xk).
因此{Xn,n≥0}具有初始分布(1.6)与转移矩阵(1.7)的马氏链.
设各阶区间(包括零阶区间[0,1))的全体为K,r为非零常数,i,j∈S.定义集函数u如下:假定Dx0…xn
是n阶区间,对n≥1,令
n
n
rgkmax{
δ u(Dx0…xn)=exp[r∑1/[1+δ-1)pk]i(Xk-1)δj(Xk)gk]∏i(Xk-1)(e
k=1
k=1
n
δi(Xk-1),δj(Xk)}
×
(2.4)
p(x0)
k=1
∏p
k
(xk-1,xk),
m
m
x0x1
其中,gk=gk(i,j),pk=pk(i,j).并令u(Dx0)=2时有
m
m
x1=1
∑u(D
)(e+
),u([0,1))=
x0=1
∑u(D
x0
),由(2.4)知,当n≥
∑
xn=1
u(Dx0…xn)=u(Dx0…xn-1)
xn=1
∑[1+δ(X
i
rgn
exp[δri(Xn-1)δj(Xn)gn]
n-1
rgn
-1)pn]
max{δi(Xk-1),δj(Xn)}
=.
u(Dx0…xn-1)若Xn-1(ω)=i,则若Xn-1(ω)≠i,则
1-pn(xn-1,j)
[1+δi(Xn-1)(e
m
exp[δri(Xn-1)gn]pn(xn-1,j)rgn
1+δ-1)pni(Xn-1)(e
-1)pn]
δi(Xn-1)
xn=1m
∑u(D∑u(D
x0…xn
)=u(Dx0…xn-1)
rg
1-pn(i,j)+enpn(i,j)rg
1+(en-1)pn(i,j)
m
=u(Dx0…xn-1),
x0…xn
xn=1
x0…xn
)=u(Dx0…xn-1),故Πω∈[0,1),
xn=1
∑u(D
)=u(Dx0…xn-1).
所以u是可加的集函数,从而存在定义在[0,1)上的单增函数f(具体构建方法见文献[3])使得ΠDx0…xn有
+
-
u(Dx0…xn)=f(Dx0…xn)-f(Dx0…xn),u(Dx0…xn)P(Dx0…xn)
f(Dx0…xn)-f(Dx0…xn)
Dx0…xn-Dx0…xn
+
-+
-
+-
(2.5)
其中,Dx0…xn和Dx0…xn分别是区间Dx0…xn的右端点和左端点.
又令
tn(r,ω)=
=
,ω∈Dx0…xn.
(2.6)
设f的可微点的全体为A(r,i,j),则
limtn(r,ω)=有限数,ω∈A(r,i,j).
n→∞
(2.7)(2.8)
由单调函数导数存在定理,有P(A(r))=1.且
limsup(1/n)lntn(r,ω)≤0,ω∈A(r,i,j).
n→∞
r而 (1/n)lntn(r,ω)=
n
n
k=1
δ(X∑
i
k-1
)δj(Xk)gk-
1n
n
k=1
∑max{δ(X
i
k-1
),δj(Xk)}×
(2.9)
rgk
ln[1+δ-1)pk],ω∈[0,1).i(Xk-1)(e
由(2.8)和(2.9),有
© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
・16・南阳师范学院学报 第6卷
n→∞
limsuprn
n
k=1
δi(Xk-1)δj(Xk)gk-∑
1n
n
k=1
∑
n
rgk
max{δ-1)pk]≤0,i(Xk-1),δj(Xk)}ln[1+δi(Xk-1)(e
ω∈A(r,i,j),
(1)令r>0,根据(2.10)得
n→∞
(2.10)
limsup1n
n
k=1
δi(Xk-1)δj(Xk)gk-∑
1nrk=1
∑
rgk
max{δ-1)pk]≤0,i(Xk-1),δj(Xk)}ln[1+δi(Xk-1)(e
ω∈A(r,i,j),
由(2.11)及上极限的性质limsup(an-bn)≤0]
n→∞
x
(2.11)
n→∞
limsup(an-cn)≤limsup(bn-cn),又根据不等
n→∞
式ln(x+1)≤x,x>-1和0≤e-1-x≤xe得
nn
1limsup≤δmax{δi(Xk-1)δj(Xk)gk-∑i(Xk-1),δj(Xk)}gkpk∑n→∞
n
k=1
k=1
n→∞
2|x|
limsuplimsuplimsup
1n
1r
nk=1n
nn
i
k-1
k=1
∑max{δ(X
i
k-1
),δj(Xk)}ln[1+δi(Xk-1)(e
rgk
-1)pk]-rgk
k=1
∑max{δ(Xik-1),δj(Xk)}gkpk≤
11n→∞
max{δ(X
n∑
n∑k=1
),δj(Xk)}
rgk1r{ln[1+δi(Xk-1)(e-1)pk]-rgkpk}≤
n
1rn→∞
{ln[1+(en-1)pk]-rgkpk}≤limsup
n→∞
1n∑k=1
1r
pk(e
rgk
-1-rgk)≤
(2.12)
rlimsup(1/n)
n→∞
k=1
∑gpe
2k
k
r|gk|
,ω∈A(r,i,j),r∈(0,α).
∞
取rm∈(0,α),m=1,2,…,满足rm→0,当m→∞时,并设A1(i,j)=∩A(rm,i,j),则P(A1(i,j))=1,
m=1
根据(2.12)和(1.1)得1 limsup
n→∞
nn
i
k-1
n
k=1
δ(X∑
nk=1
)δj(Xk)gk-r|gk|
k=1
∑max{δ(X
i
k-1
≤),δj(Xk)}gkpk(2.13)
rmsup(1/n)mli
n→∞
∑
gkpkem
2
≤rt(i,j),ω∈A1(i,j).mα
n
由于r.13),得m→0,根据(2
n
1limsupδi(Xk-1)δj(Xk)gk-∑n→∞
n
k=1
k=1
∑max{δ(X
i
i
k-1
k-1
ω∈A1(i,j).),δj(Xk)}gkpk≤0,
(2.14)
(2)取r<0,根据(2.10)得
n→∞
liminf1n
i
k-1
δ(X
n∑
k=1
)δj(Xk)gk-
max{δ(X
nr∑
k=1
1n
),δj(Xk)}ln[1+δi(Xk-1)(e
rgk
-1)pk]≥0,
(2.15)
ω∈A(r,i,j).
由(2.15)及上极限的性质liminf(an-bn)≥0]
n→∞
x
n→∞
liminf(an-cn)≥liminf(bn-cn),又根据不等
n→∞
式ln(x+1)≤x,x>-1和0≤e-1-x≤xe得
nn
1liminfδmax{δi(Xk-1)δj(Xk)gk-∑i(Xk-1),δj(Xk)}gkpk≥∑n→∞
n
k=1
k=1
n→∞
2|x|
liminfliminfliminf
1n
1r
nk=1n
nn
i
k-1
k=1
∑max{δ(X
i
k-1
),δj(Xk)}ln[1+δi(Xk-1)(e
rgk
-1)pk]-rgk
k=1
∑max{δ(X
i
k-1
),δj(Xk)}gkpk≥
11n→∞
max{δ(X
n∑
n∑k=1
),δj(Xk)}
rgk
1r
{ln[1+δi(Xk-1)(e-1)pk-rgkpk}≥
n
1r
n→∞
{ln[1+(e
n
-1)pk]-rgkpk}≥liminfn→∞
1n∑k=1
1r
pk(e
rgk
-1-rgk)≥
(2.16)
∞
rlimsup(1/n)
n→∞
k=1
∑gpe
2k
k
r|gk|
,ω∈A(r,i,j),r∈(-α,0).
取r,0),m=1,2,…满足rm∈(-αm→0,当m→∞时.并设A2(i,j)=∩A(rm,i,j),则P(A2(i,j))=1,
m=1
根据(2.12)和(1.1)得
liminf
n→∞
1n
nn
i
k-1
k=1
δ(X∑
)δj(Xk)gk-
k=1
∑max{δ(X
i
k-1
≥),δj(Xk)}gkpk© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第3期王学武:有限非齐次马尔可夫链的强极限定理
n
・17・
rmsup(1/n)mli
n→∞
k=1
∑
gkpkem
2
r|gk|
≥rt(i,j),ω∈A1(i,j).mα(2.17)
由于r.17)和(1.1)得m→0及(2
n
1liminfδi(Xk-1)δj(Xk)gk-∑n→∞
n
k=1
n
k=1
∑max{δ(X
i
n
i
k-1
≥0,ω∈A2(i,j).),δj(Xk)}gkpk(2.18)
令A=A1
∩A
m
2
,则P(A)=1.根据(2.14)和(2.18)得
n→∞
lim
1n
n
k=1
δ(X∑
i
k-1
)δj(Xk)gk-
k=1
∑max{δ(X
k-1
),δj(Xk)}gkpk=0,ω∈A.(2.19)
令A
3
=
∩
1n
A(i,j),则P(A)=1.由(2.19),得i,j
n
n
k
m
m
i
k-1m
k=1
n
3
n→∞
limlim
m
∑g
(Xk-1,Xk)-m
i
k-1
k=1i=1
∑∑∑max{δ(X
j=1
nn),δj(Xk)}gkpkm
i
=
),δj(Xk)}gkpk=3
1n
m
m
n→∞
k=1i=1
δ(X∑∑∑
j=1n
)δj(Xk)gk(i,j)-
k=1i=1∑∑∑max{δ(Xj=1
k=1k-1
∑∑lim
i=1
j=1
1n
n→∞
k=1δi(Xk-1)δj(Xk)gk(i,j)-∑∑max{δi(Xk-1),δj(Xk)}gkpk=0,ω∈A.(2.20)
根据(2.20)可知(2.1)和(2.2)成立.
定理2.2 设{Xn,n≥0}具有初始分布(1.6)与转移矩阵(1.7)的马氏链,则有
n
n→∞
n
k
m
m
i
k-1
lim(1/n)
k=1
∑lnp
(Xk-1,Xk)-
k=1
∑∑∑max{δ(X
j=1
i=1
(i,j)|
),δj(Xk)}pk(i,j)lnpk(i,j)=0.
|g
证明 取gk(i,j)=-lnpk(i,j),则0≤pk(i,j)ek
n
=1,Πk∈N,再取β∈(0,1)则有
n
tβ(i,j)=limsup(1/n)
n→∞
k=1
n
∑g
k=1
2k
(i,j)pk(i,j)e
2
β|gk(i,j)|
=limsup(1/n)
n→∞
k=1
∑p
k
(i,j)e
|gk(i,j)|
gk(i,j)e
2
(β-1)|gk(i,j)|
=
n→∞
limsup(1/n)
(β-1)|gk(i,j)|
∑
2
gk(i,j)e
(β-1)x
(β-1)|gk(i,j)|
.
2
又因为gk(i,j)e2
是有界量,事实上,令x≥0,取M(M>2/(1-β)),则可以证明
2
≤M,从而说明gk(i,j)e
n
(β-1)|gk(i,j)|
f(x)=Me
(1-β)x
-x≥0,即xe
tα
2
是有界量.所以有
<∞.
(i,j)=limsup(1/n)
n→∞
k=1
∑g
2k
(i,j)pk(i,j)e
α|gk(i,j)|
从而定理2.1的条件(1.1)成立,根据定理2.1,定理2.2的结论显然成立.
参 考 文 献
[1] LiuWen.Somestronglimittheoremsrelativetothegeometricaverageofrandomtransitionprobabilitiesofarbitraryfinitenon2homogeneousMarkovchains[J].Stat.Probab.Letts,1994,21(1):77-83.[2] LiuWenandYangWeiguo.AnextentionofShannon2McMillantheoremandsomelimitpropertiesfornonhomogenousMarkovchains[J].StochasticProc.Appl,1996,61(1):129-145.[3] LiuWenandWangZhongzhi.AstronglimittheoremonrandomselectionforcountablenonhomogenousMarkovchains[J].
ChineseJ.Math(Taiwan),1996,24(2):187-197.[4] LiuWen.Alimitpropertyofarbitrarydiscreteinformationsources[J].TaiwaneseJ.Math,1999,3(4):539-546.[5] Kailaichung.Acourseinprobabilitytheory[M].NewYork:Academicpress,1968:354-360.
ThestronglimittheoremsforfinitenonhomogeneousMarkovchains
WANGXue2wu
(DepartmentofMathematicsandInformationScience,ShandongIndustrialand
CommercialCollege,Yantai2005,China)
Abstract:Themanypropertiesoftherelativeentropydensitywerestudiedbyusinganalysismethod.Thetheo2remsofShannon2McMillanwereextended.Mainresultsofarticle[1]～[3]wereimproved.ThestronglimittheoremsoffinitenonhomogeneousMarkovchainweresetup.
Keywords:stronglimittheorem;Markovchain;entropy;relativeentropydensity
© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
