任意非齊次可列馬氏信源關(guān)于廣義隨機選擇系統(tǒng)的廣義Shannon-McMillan定理

王康康， 宗德才， 李 芳， 黃輝林

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

設(shè)(Ω,F,P)為一概率空間,設(shè){Xn,n≥0}是定義在該概率空間上并于字母集S={s1,s2,…}上取值的任意信源,其聯(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(s1),q(s2),…,q(sn),…),q(si)>0,si∈S

(3)

Pn=(pn(sj|si)),pn(sj|si)>0,si,sj∈S,n≥1

(4)

式中：pn(sj|si)=P(Xn=sj|Xn-1=si)n≥1

(5)

則非齊次馬氏信源{Xn,n≥0}的相對熵密度為：

(6)

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

定義1我們給出廣義隨機選擇的概念,先給出一組定義在Sn+1(n=0,1,2,…)上的非負實值函數(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}中取值．

(7)

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

(8)

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

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

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

定義3設(shè)

(9)

稱H(pk(s1|Xk-1),pk(s2|Xk-1),…)為Xk關(guān)于Xk-1的隨機條件熵．

1 主要定理

定理1設(shè){Xn,n≥0}是具有初始分布(3)與轉(zhuǎn)移概率(4)并取值于可列集S的非齊次馬氏信源,Sn(ω)與H(pk(s1|Xk-1),pk(s2|Xk-1),…)分別由式(8，9)定義,{Yn,n≥0}如前定義．設(shè)α>0,

(10)

(11)

則有

a.s.ω∈D

(11)

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

Qk(λ)=E[pk(Xk|Xk-1)-λYk|Xk-1=xk-1]=

(13)

(14)

(15)

由式(13，14，15)可知：

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

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

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

(16)

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

(17)

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

(18)

因而由式(10，18)有

(19)

由式(5,13～15，17，19)有

logE(pk(Xk|Xk-1)-λYk|Xk-1)]≤0

a.s.ω∈D

(20)

易知由不等式

有

(21)

又由不等式logx≤x-1.(x≥0)及式(11,20，21),且注意到

當0<|λ|

pk(Xk|Xk-1)-|λ|b|Xk-1=

pk(Xk|Xk-1)(α-|λ|)bpk(Xk|Xk-1)-αb|Xk-1]≤

(22)

當0<λ

a.s.ω∈D

(23)

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

a.s.ω∈D

(24)

類似的,當-α<-t<λ<0時,利用式(22)可證有

a.s.ω∈D

(25)

由式(24,25)即證有

logpk(Xk|Xk-1)|Xk-1)]=0

a.s.ω∈D

(26)

又注意到

H(pk(s1|Xk-1),pk(s2|Xk-1),…)=

E(-logpk(Xk|Xk-1)|Xk-1).

于是由式(8，26)便有

a.s.ω∈D

(27)

從而,定理證畢．

推論1設(shè){Xn,n≥0}是具有分布(1)的任意信源,fn(ω)與H(pk(s1|Xk-1),pk(s2|Xk-1),…)分別由式(6，9)定義．設(shè)α>0,

(28)

則有

(29)

2 狀態(tài)有限空間下的若干隨機Shannon-McMillan定理

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

Hk(pk(s1|Xk-1),…,pk(sN|Xk-1))=

則有

a.s.ω∈D

(30)

(31)

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

推論2[8]設(shè){Xn,n≥0}是如上定義的非齊次馬氏信源,fn(ω)如式(6)定義, 則有

pk(sN|Xk-1))=0 a.s.

(32)

證明: 定理2中令Yn≡1,n≥0,即有

該推論便是文獻[8]中的定理2．

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

(33)

則有

(34)

證明: 由推論2知這時pk(Xk|Xk-1)=pk(Xk),從而

Hk(pk(s1|Xk-1),…,pk(sN|Xk-1))=

H(pk(1),…,pk(N))

由式(32)即得式(34)成立．

3 衍生結(jié)論

定理3設(shè){Xn,n≥0}是具有初始分布式(3)與轉(zhuǎn)移概率式(4)并取值于可列集S的非齊次馬氏信源,Sn(ω)與H(pk(s1|Xk-1),pk(s2|Xk-1),…)分別由式(8，9)定義,{Yn,n≥0}如前定義．設(shè)α>0,0

Xk-1]<∞ a.s.

(35)

則有

a.s.ω∈D

(36)

證明: 由式(11，35),簡記pk(Xk|Xk-1)=pk．則有

(37)

由定理1即可得式(36)成立．

[1] Shannon C E. A mathematical theory of communication [J].BellSystemTechnicalJournal，1948,27(3): 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(2): 612-614.

[5] Kieffer J C. A simple proof of the Moy-Perez generalization of Shannon-Mcmillan theorem[J].PacificJMath， 1974,51(2):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定理的若干研究，數(shù)學物理學報[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].StochasticProcessandtheirApplications, 1996,61(1):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 Kangkang, Ye Hui, Li Fang. A class of generalized Shannon-Mcmillan theorems for arbitrary discrete information source [J].JournalofMathematics, 2011, 31(2): 307-313.

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