二階非齊次馬氏信源關(guān)于廣義隨機選擇系統(tǒng)的一類Shannon-McMillan定理

王康康, 李 芳, 孟義平

(1.江蘇科技大學(xué) 數(shù)理學(xué)院, 江蘇 鎮(zhèn)江 212003)(2.安徽師范大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院, 安徽 蕪湖 241000)(3.上海交通大學(xué) 數(shù)學(xué)系, 上海 200240)

設(shè)(Ω,F,P)為一概率空間,而{Xn,n≥0}是定義在該概率空間上并于可列字母集S={s1,s2,…,sn,…}上取值的任意信源,其聯(lián)合分布為

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

xi∈S, 0≤i≤n

(1)

令

(2)

式中：log為自然對數(shù),fn(ω)稱為{Xi,0≤i≤n}的相對熵密度．

如果{Xn,n≥0}為二階非齊次馬氏信源,其二維初始分布與二階轉(zhuǎn)移概率矩陣分別為

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,…)上的非負(fù)實值函數(shù)列fn(x0,…,xn)．令

Y0=y(y為任意實數(shù))

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

fn(x0,…,xn)稱為選擇函數(shù).如果{Yn,n≥0}在區(qū)間[0,b]取值,{Yn,n≥0}稱為廣義賭博系統(tǒng)或廣義隨機選擇系統(tǒng)．而傳統(tǒng)的賭博系統(tǒng)或隨機選擇系統(tǒng)在兩點集{0,1}中取值．

定義2設(shè){Xn,n≥0}如上定義的二階非齊次馬氏信源,{Yn,n≥0}為廣義隨機選擇系統(tǒng),稱

(7)

為二階非齊次馬氏信源{Xn,n≥0}關(guān)于隨機選擇系統(tǒng)的相對熵密度,也稱其為廣義相對熵密度．顯然,當(dāng)Yn≡1,n≥0時,該廣義相對熵密度Sn(ω)即為一般的相對熵密度fn(ω)．

關(guān)于fn(ω)的極限性質(zhì)是信息論中的重要問題,在信息論中稱為Shannon-Mcmillan定理或信源的漸近均勻分割性(S-M定理),它是信息論中編碼的基礎(chǔ)．文獻(xiàn)[1]中首先證明了齊次遍歷馬氏信源的S-M定理．文獻(xiàn)[2-3]則證明了平穩(wěn)遍歷信源的S-M定理．文獻(xiàn)[4]考慮了字母集為可列集的情況．以后又有許多作者將上述結(jié)果推廣到一般的隨機過程[5-6]．文獻(xiàn)[7]通過任意信源與無記憶信源比較,用特有的分析方法給出了一類任意離散信源相對熵密度用不等式給出的強極限定理,也稱為小偏差定理．文獻(xiàn)[8]研究了有限狀態(tài)集合下非齊次馬氏信源的一類Shannon-Mcmillan定理．文獻(xiàn)[9-10]分別討論了任意信源的一類Shannon-McMillan偏差定理和任意信源關(guān)于賭博系統(tǒng)的Shannon-McMillan定理．

高階馬爾可夫鏈?zhǔn)且话泷R爾可夫鏈概念的自然推廣,隨著馬氏鏈理論的不斷發(fā)展和應(yīng)用,人們對高階馬爾可夫鏈的理論和應(yīng)用也越來越有興趣,如信息論中關(guān)于Shannon-McMillan定理的研究便是其核心問題之一．而高階馬爾可夫鏈也是一類非常重要的信源,如語聲,電視信號等往往都是高階馬爾可夫信源．因此,研究高階馬爾可夫鏈的極限理論具有非常廣泛的理論和實際意義．文獻(xiàn)[11]首先研究了二重非齊次馬氏鏈泛函關(guān)于可預(yù)報序列的若干極限定理及AEP性質(zhì)．文獻(xiàn)[12]討論了m階非齊次馬氏鏈的一些Shannon-Mcmillan小偏差定理．

文中將文獻(xiàn)[8]的結(jié)果推廣到隨機選擇系統(tǒng)，即通過構(gòu)造相容分布和非負(fù)上鞅的方法,研究二階非齊次馬氏信源關(guān)于廣義賭博系統(tǒng)的一類廣義Shannon-Mcmillan定理．并由此得出已有的非齊次馬氏信源的Shannon-Mcmillan定理．將文獻(xiàn)[7]中所用的方法加以改進(jìn),并作為推論得到了文獻(xiàn) [8] 的主要結(jié)果．

定義3設(shè)

(8)

1 主要定理及證明

(9)

(10)

則有

(11)

證明:考慮概率空間(Ω,F,P), 設(shè)λ為任意實數(shù),記

(12)

(13)

(14)

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

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

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

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

(15)

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

(16)

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

(17)

因而由式(9，17)有

(18)

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

a.s.ω∈D

(19)

由式(19)與上極限的性質(zhì)有

(20)

易知由不等式

(21)

有

0≤x≤1

(22)

又由不等式logx≤x-1.(x≥0)及式(10,20，22),當(dāng)|λ|<α?xí)r有

(23)

當(dāng)0<λ<α?xí)r由式(23)有

(24)

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

(25)

類似的,當(dāng)-α<λ<0時,利用式(23)可證有

(26)

由式(25,26)即證有

(27)

又注意到

于是由式(7，27)便有

(28)

從而,定理證畢．

定理1的條件式(10)可以加強為

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

推論1設(shè){Xn,n≥0}是具有初始分布(3)與轉(zhuǎn)移概率(4)的二階非齊次馬氏信源,并于字母集S={s1,s2,…,sM}上取值,Sn(ω)由(7)定義,{Yn,n≥0}如前定義．設(shè)

(29)

則有

(30)

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

求導(dǎo)得

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

(31)

(32)

由式(10，32)有

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

推論2[8]設(shè){Xn,n≥0}是如上定義的二階非齊次馬氏信源,fn(ω)與H(pk(s1|Xk-1),…,pk(sM|Xk-1))分別由(6)與(29)定義．則有

(33)

推論3設(shè){Xn,n≥0}為無記憶信源．其中fn(ω)由(2)定義．設(shè)H(pk(1),…,pk(M))表示分布(pk(1),…,pk(M))的熵．即

(34)

則有

a.s.

(35)

2 衍生結(jié)論

(36)

則有

(37)

(38)

從而由定理1即得結(jié)論成立．

參考文獻(xiàn)(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] 劉文,楊衛(wèi)國.關(guān)于Shannon-Mcmillan定理的若干研究[J]．?dāng)?shù)學(xué)物理學(xué)報,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.