二阶非齐次马氏信源关于广义随机选择系统的一类Shannon-McMillan定理

王康康, 李 芳, 孟义平

(1.江苏科技大学 数理学院, 江苏 镇江 212003)(2.安徽师范大学 数学与计算科学学院, 安徽 芜湖 241000)(3.上海交通大学 数学系, 上海 200240)

设(Ω,F,P)为一概率空间,而{Xn,n≥0}是定义在该概率空间上并于可列字母集S={s1,s2,…,sn,…}上取值的任意信源,其联合分布为

P(X0=x0,…,Xn=xn)=p(x0,…,xn)>0

xi∈S, 0≤i≤n

(1)

令

(2)

式中：log为自然对数,fn(ω)称为{Xi,0≤i≤n}的相对熵密度．

如果{Xn,n≥0}为二阶非齐次马氏信源,其二维初始分布与二阶转移概率矩阵分别为

q(i,j)>0i,j∈S

(3)

Pn=(pn(h|i,j)),pn(h|i,j)>0

i,j,h∈S,n≥2

(4)

式中：pn(h|i,j)=P(Xn=h|Xn-2=i,Xn-1=j)(n≥2)．则有

(5)

则二阶非齐次马氏信源{Xn,n≥0}的相对熵密度为

(6)

定义1给出广义随机选择的概念,先给出一组定义在Sn+1(n=0,1,2,…)上的非负实值函数列fn(x0,…,xn)．令

Y0=y(y为任意实数)

Yn+1=fn(X0,…,Xn),n≥0

fn(x0,…,xn)称为选择函数.如果{Yn,n≥0}在区间[0,b]取值,{Yn,n≥0}称为广义赌博系统或广义随机选择系统．而传统的赌博系统或随机选择系统在两点集{0,1}中取值．

定义2设{Xn,n≥0}如上定义的二阶非齐次马氏信源,{Yn,n≥0}为广义随机选择系统,称

(7)

为二阶非齐次马氏信源{Xn,n≥0}关于随机选择系统的相对熵密度,也称其为广义相对熵密度．显然,当Yn≡1,n≥0时,该广义相对熵密度Sn(ω)即为一般的相对熵密度fn(ω)．

关于fn(ω)的极限性质是信息论中的重要问题,在信息论中称为Shannon-Mcmillan定理或信源的渐近均匀分割性(S-M定理),它是信息论中编码的基础．文献[1]中首先证明了齐次遍历马氏信源的S-M定理．文献[2-3]则证明了平稳遍历信源的S-M定理．文献[4]考虑了字母集为可列集的情况．以后又有许多作者将上述结果推广到一般的随机过程[5-6]．文献[7]通过任意信源与无记忆信源比较,用特有的分析方法给出了一类任意离散信源相对熵密度用不等式给出的强极限定理,也称为小偏差定理．文献[8]研究了有限状态集合下非齐次马氏信源的一类Shannon-Mcmillan定理．文献[9-10]分别讨论了任意信源的一类Shannon-McMillan偏差定理和任意信源关于赌博系统的Shannon-McMillan定理．

高阶马尔可夫链是一般马尔可夫链概念的自然推广,随着马氏链理论的不断发展和应用,人们对高阶马尔可夫链的理论和应用也越来越有兴趣,如信息论中关于Shannon-McMillan定理的研究便是其核心问题之一．而高阶马尔可夫链也是一类非常重要的信源,如语声,电视信号等往往都是高阶马尔可夫信源．因此,研究高阶马尔可夫链的极限理论具有非常广泛的理论和实际意义．文献[11]首先研究了二重非齐次马氏链泛函关于可预报序列的若干极限定理及AEP性质．文献[12]讨论了m阶非齐次马氏链的一些Shannon-Mcmillan小偏差定理．

文中将文献[8]的结果推广到随机选择系统，即通过构造相容分布和非负上鞅的方法,研究二阶非齐次马氏信源关于广义赌博系统的一类广义Shannon-Mcmillan定理．并由此得出已有的非齐次马氏信源的Shannon-Mcmillan定理．将文献[7]中所用的方法加以改进,并作为推论得到了文献 [8] 的主要结果．

定义3设

(8)

1 主要定理及证明

(9)

(10)

则有

(11)

证明:考虑概率空间(Ω,F,P), 设λ为任意实数,记

(12)

(13)

(14)

由式(12,13,14)可知,

g(λ,x0,…,xn-1)·

g(λ,x0,…,xn-1)·

g(λ,x0,…,xn-1)

(15)

于是有g(λ,x0,…,xn),n=1,2,…是Sn上的一族相容分布．令

(16)

由于{Tn(λ,ω),n≥1}是a.s.收敛的非负上鞅，故由Doob鞅收敛定理[4]有

(17)

因而由式(9，17)有

(18)

由式(5，13，14，16),可将式(18)重新整理为

a.s.ω∈D

(19)

由式(19)与上极限的性质有

(20)

易知由不等式

(21)

有

0≤x≤1

(22)

又由不等式logx≤x-1.(x≥0)及式(10,20，22),当|λ|<α时有

(23)

当0<λ<α时由式(23)有

(24)

取0<λi<α(i=1,2,…),使得λi→0(i→∞)则对一切i,由式(24)有

(25)

类似的,当-α<λ<0时,利用式(23)可证有

(26)

由式(25,26)即证有

(27)

又注意到

于是由式(7，27)便有

(28)

从而,定理证毕．

定理1的条件式(10)可以加强为

显然bα<∞可以推出Bα<∞．

推论1设{Xn,n≥0}是具有初始分布(3)与转移概率(4)的二阶非齐次马氏信源,并于字母集S={s1,s2,…,sM}上取值,Sn(ω)由(7)定义,{Yn,n≥0}如前定义．设

(29)

则有

(30)

φ(x)=(logx)2x1-αb,0

求导得

φ′(x)=x-αb[2(logx)+(logx)2(1-αb)]

(31)

(32)

由式(10，32)有

所以式(10)自然成立．由式(11)即得式(30)式成立．

推论2[8]设{Xn,n≥0}是如上定义的二阶非齐次马氏信源,fn(ω)与H(pk(s1|Xk-1),…,pk(sM|Xk-1))分别由(6)与(29)定义．则有

(33)

推论3设{Xn,n≥0}为无记忆信源．其中fn(ω)由(2)定义．设H(pk(1),…,pk(M))表示分布(pk(1),…,pk(M))的熵．即

(34)

则有

a.s.

(35)

2 衍生结论

(36)

则有

(37)

(38)

从而由定理1即得结论成立．

参考文献(References)

[1] Shannon C.A mathematical theory of communication [J].BellSystemTechJ,1948,27: 379-423.

[2] Mcmillan B.The basic theorem of information theory[J].AnnMathStatist, 1953,24:196-219.

[3] Breiman L.The individual ergodic theorem of information theory[J].AnnMathStatist, 1957, 28: 809-811.

[4] Chung K.L.The ergodic theorem of information theory [J].AnnMathStatist, 1961,32: 612-614.

[5] Kieffer J C.A simple proof of the Moy-Perez generalization of Shannon-Mcmillan theorem[J].PacificJMath, 1974,51:203-204.

[6] Algoet P, Cover T.A sandwich proof of Shannon-Mcmillan theorem[J].AnnProbab, 1988,16: 899-909.

[7] 刘文,杨卫国.关于Shannon-Mcmillan定理的若干研究[J]．数学物理学报,1994,3:337-345.

Liu Wen, Yang Weiguo.Some research on Shannon-Mcmillan theorem [J].ActaMathematicaScientia, 1994,3: 337-345.(in Chinese)

[8] Liu Wen, Yang Weiguo.An extension of Shannon-Mcmillan theorem and some limit properties for nonhomogeneous Markov chains[J].StochasticProcess, 1996,61:129-145.

[9] Wang Kangkang, Yang Weiguo.A class of Shannon-Mcmillan approximation theorems for arbitrary discrete information source[J].JournalofMathematicalResearchandExposition, 2007, 27(4): 719-727.

[10] Wang Kangkang.A class of Shannon-Mcmillan theorems for arbitrary discrete information source on the gambling system[J].PureandAppliedMathematics, 2008, 28 (2): 353-357.

[11] Wang Zhongzhi, Yang Weiguo.Some strong limit theorems for both nonhomogeneous Markov chains of order two and their random transforms[J].JSystemSciandMathSci,2004,24: 451-462.

[12] Wang Kangkang.Some research on Shannon-McMillan theorem formth-order nonhomogeneous markov information source[J]．StochasticAnalysisandApplications, 2009, 27 (6):1117-1128.