二根樹指標(biāo)馬氏信源關(guān)于賭博系統(tǒng)的極限定理

顧小萍

（無(wú)錫市廣播電視大學(xué)五年制高職部，江蘇無(wú)錫214011）

二根樹指標(biāo)馬氏信源關(guān)于賭博系統(tǒng)的極限定理

顧小萍

（無(wú)錫市廣播電視大學(xué)五年制高職部，江蘇無(wú)錫214011）

研究任意二根樹圖上二階非齊次馬氏信源的極限性質(zhì)。通過(guò)構(gòu)造相容分布和非負(fù)上鞅的方法，得到了任意無(wú)限連通二根樹上二階非齊次馬氏信源關(guān)于廣義賭博系統(tǒng)的一類廣義漸近均勻分割性定理，也稱廣義Shannon-McMillan定理，并推廣了已有的結(jié)果。

二階非齊次馬氏信源；二根樹；Shannon-McMillan定理；廣義賭博系統(tǒng)；相對(duì)熵密度

設(shè)T為一無(wú)限連通二根樹圖，σ，t（σ≠t）是T中任意兩個(gè)頂點(diǎn)。則存在唯一的從σ到t的路徑σ=x1，x2，…，xm=t，其中x1，x2，…，xm互不相同，且xi與xi+1為相鄰兩個(gè)頂點(diǎn)。m-1稱為σ到t的距離。為給T中頂點(diǎn)編號(hào)，選定兩個(gè)頂點(diǎn)作為根頂點(diǎn)（簡(jiǎn)稱根），分別記為-1和o。如果一個(gè)頂點(diǎn)t位于根頂點(diǎn)o到頂點(diǎn)σ的唯一路徑上，則記t≤σ。若σ，t為T上兩個(gè)不同的頂點(diǎn)，記σ∧t為同時(shí)滿足σ∧t≤σ和σ∧t≤t，且離根頂點(diǎn)o最遠(yuǎn)的頂點(diǎn)。

文中T表示任意局部有限無(wú)窮二根樹。為了更好地解釋二根樹的概念，筆者以二根Cayley樹TC，N為例，即除根頂點(diǎn)－1外，每個(gè)頂點(diǎn)均有N+1個(gè)頂點(diǎn)相連，如圖1所示。記t為T中從根頂點(diǎn)o向上，從左向右數(shù)第t個(gè)頂點(diǎn)，記|t|為頂點(diǎn)t到根o的距離，若|t|=n，則t位于二根樹的第n層。記T（n）表示從根o到第n層所有頂點(diǎn)的子圖，Ln表示第n層上所有頂點(diǎn)的集合，表示T從第m層到第n層上所有頂點(diǎn)的集合。對(duì)于任意頂點(diǎn)t，從根頂點(diǎn)o到頂點(diǎn)t的路徑上存在唯一一個(gè)離頂點(diǎn)t最近的頂點(diǎn)稱為t的第一代父代，記為1t，且稱t為1t子代，t的第二代父代記為2t。類似的，t的第n代父代記為nt。設(shè)B是樹圖T的子圖，記XB={Xt，t∈B}，且xB為XB的實(shí)現(xiàn)。

定義1設(shè)G={s1，s2，…，sM}為一有限狀態(tài)空間，{Xt，t∈T}是定義在概率空間{Ω，F(xiàn)，P}上且于G中取值的隨機(jī)變量集合。設(shè)

圖1 二根樹TC，3

分別為定義在G2上的二維概率分布和G3上的二階隨機(jī)轉(zhuǎn)移矩陣族，如果對(duì)于任意頂點(diǎn)t，

則稱{Xt，t∈T}為具有二維初始分布p和二階轉(zhuǎn)移矩陣族P的G值樹指標(biāo)二階非齊次馬氏鏈。

由（1），（2）式可得樹指標(biāo)二階非齊次馬氏鏈的聯(lián)合分布為

這里|T（n）|表示從第－1層到第n層的所有頂點(diǎn)的個(gè)數(shù)，則稱fn（ω）為樹T的子圖T（n）上關(guān)于測(cè)度P的相對(duì)熵密度。

在概率論和信息論當(dāng)中，fn（ω）的收斂性具有重要的理論和實(shí)際意義。fn（ω）在一定意義下的收斂（L1收斂，依概率收斂，a.s.收斂）稱為Shannon-Mcmillan定理或信源的漸近均勻分割性（AEP）。關(guān)于整數(shù)集上信源的Shannon-Mcmillan定理已有廣泛和深入的研究[1-2]。近幾年來(lái)，由于信息論發(fā)展的需要，人們開始研究樹圖隨機(jī)場(chǎng)的Shannon-Mcmillan定理[3]。樹圖模型近年來(lái)已引起物理學(xué)、概率論及信息論界的廣泛興趣。Berger與葉中行[4]研究了齊次樹圖上某些平穩(wěn)隨機(jī)場(chǎng)的熵率。葉中行與Berger[5]又研究了齊次樹圖上PPG不變隨機(jī)場(chǎng)的遍歷性與漸近均勻分割性。但他們的收斂結(jié)果只涉及依概率收斂。楊衛(wèi)國(guó)，葉中行[6-7]近年來(lái)研究了齊次樹指標(biāo)與Cayley樹指標(biāo)馬氏鏈場(chǎng)上a.s.收斂的Shannon-Mcmillan定理。但楊，葉的結(jié)果僅涉及單根樹圖馬氏鏈場(chǎng)情況，而對(duì)賭博系統(tǒng)中二根樹指標(biāo)馬氏鏈場(chǎng)的Shannon-Mcmillan定理沒(méi)有考慮。最近，彭偉才和楊衛(wèi)國(guó)[8]研究了齊次樹指標(biāo)隨機(jī)場(chǎng)關(guān)于馬氏鏈場(chǎng)泛函的小偏差定理，石志巖與楊衛(wèi)國(guó)[9]研究了m根Cayley樹上m階非齊次馬氏鏈場(chǎng)的若干極限性質(zhì)，楊衛(wèi)國(guó)[10]又研究了任意隨機(jī)序列幾乎處處收斂的一些極限性質(zhì)。

定義2給出樹上廣義隨機(jī)選擇的概念，先給出一組定義在Sn（n=1，2，…）上并取值于區(qū)間[0，b]的非負(fù)實(shí)值函數(shù)列fn（x1，…，xn）。

令Y0=y（y為任意實(shí)數(shù)），Yt=f|t|（X1t，X2t，…，X0，X－1），|t|≥2。其中|t|代表從頂點(diǎn)t到根頂點(diǎn)-1的邊數(shù)或者距離。fn（x1，…，xn）稱為廣義隨機(jī)選擇函數(shù)，{Yt，t∈T{0，－1}}稱為二根樹指標(biāo)廣義賭博系統(tǒng)或廣義隨機(jī)選擇系統(tǒng)，傳統(tǒng)的鏈?zhǔn)劫€博系統(tǒng){Yn，n≥0}在兩點(diǎn)集{0，1}中取值。

定義3設(shè){Xt，t∈T}如上定義的樹指標(biāo)二階非齊次馬氏鏈，{Yt，t∈T{0，－1}}為如上定義的廣義隨機(jī)選擇系統(tǒng)，稱

為樹指標(biāo)二階非齊次馬氏鏈{Xt，t∈T}關(guān)于廣義隨機(jī)選擇系統(tǒng)的相對(duì)熵密度，也稱其為廣義相對(duì)熵密度。顯然，當(dāng)Yt≡1，t∈T（n）時(shí)，該廣義相對(duì)熵密度即為一般的相對(duì)熵密度。

該文筆者將文獻(xiàn)[7]的結(jié)果推廣到任意局部有限無(wú)窮二根樹上廣義隨機(jī)選擇系統(tǒng)的情況。即通過(guò)構(gòu)造相容分布和非負(fù)鞅的方法，研究二根樹上二階非齊次馬氏信源關(guān)于賭博系統(tǒng)的一類廣義Shannon-McMillan定理。并由此得出已有的樹上非齊次馬氏信源的Shannon-McMillan定理。文中將文獻(xiàn)[11]中所用的方法加以改進(jìn)，并作為推論得到了文獻(xiàn)[7]的主要結(jié)果。

1 主要結(jié)果及證明

定義4設(shè)

稱Ht（Xt|X1t，X2t）為Xt關(guān)于X1t，X2t的隨機(jī)條件熵。

定理1設(shè){Xt，t∈T}是如上定義的任意無(wú)窮連通二根樹指標(biāo)二階非齊次馬氏信源，{Yt，t∈T{0，－1}}為二根樹指標(biāo)廣義隨機(jī)選擇系統(tǒng)。Sn（ω）與Ht（Xt|X1t，X2t）分別由（7）與（8）式定義。設(shè)

則有

推論1設(shè){Xt，t∈T}是如上定義的樹指標(biāo)二階非齊次馬氏信源，為二根樹指標(biāo)廣義隨機(jī)選擇系統(tǒng)。fn（ω）與Ht（Xt|X1t，X2t）分別由（6）與（8）式定義。則有

證明在定理1中令Yt≡1，t∈T（n）{0}{－1}，則有。從而可知D（ω）＝Ω，由（10）式可得推論1成立。

注在推論1中當(dāng){Xt，t∈T}退化為單根樹指標(biāo)一階非齊次馬氏信源時(shí)，有

這時(shí)，推論1即為Yang and Ye[7]的定理2。

證明考慮概率空間{Ω，F(xiàn)，P}，設(shè)λ∈（－1，1）。設(shè)δj（·）表示Kronecker函數(shù)，即δi（j）=δij（i，j∈S）。并記gk（j）=-logPt（j|X1t，X2t），構(gòu)造如下的乘積分布

由（11）式，令

由（5），（11）與（12）式有

因而，有

由Doob鞅收斂定理[12]可知{Un（λ，ω），F(xiàn)n，n≥1}是一非負(fù)上鞅。且有

由（9）與（15）式，有

又由（13）與（16）式有

由（17）式及上極限的性質(zhì)與不等式：1-1/x≤lnx≤x-1（x＞0），ex-1-x≤（1/2）x2e|x|

又注意到gt（j）=-logPt（j|X1t，X2t），有

設(shè)0＜λ＜1，由（18）式有

考慮函數(shù)

求導(dǎo)得

令φ′（x）=0得x＝e2/（λb-1），故φ（x）在[0，1]區(qū)間上的最大值為

由（21）與（19）式，當(dāng)0＜λ＜1時(shí)有

取0＜λi＜1（i=1，2，…），使得λi→0+（i→∞），則對(duì)一切i，由（22）式有

由（7），（8）與（23）式以及gt（j）=-logPt（j|X1t，X2t），有

當(dāng)-1＜λ＜0時(shí)，由（18）式有

這時(shí)，由（21）和（25）式有

取-1＜λi＜0（i=1，2，…），使得λi→0-（i→∞），則對(duì)一切i，由（26）式有

由（7），（8）與（27）式以及gt（j）=-logPt（j|X1t，X2t），類似于（24）式的推導(dǎo)過(guò)程，有

由（24）與（28）式有

于是（10）式成立。

2 結(jié)語(yǔ)

通過(guò)構(gòu)造非負(fù)上鞅和相容分布的方法，研究了任意局部有限二根樹指標(biāo)二階非齊次非齊次馬氏鏈關(guān)于廣義賭博系統(tǒng)的熵定理，即Shannon-McMillan定理，推廣了已有的結(jié)果。樹形圖上的信息熵定理目前國(guó)內(nèi)外的研究結(jié)果較少，文中的結(jié)果對(duì)于樹形圖上的信息論編碼理論具有一定的指導(dǎo)意義。

[1]劉文，楊衛(wèi)國(guó).任意信源二元函數(shù)一類平均值的極限性質(zhì)[J].應(yīng)用概率統(tǒng)計(jì)，1995，11（2）：195-203.

[2]劉文，楊衛(wèi)國(guó).任意信源與馬氏信源的比較及小偏差定理[J].數(shù)學(xué)學(xué)報(bào)，1997，40（1）：22-36.

[3]Ye Z，Berger T.Asymptotic equipartition property for random fields on trees[J].Chinese J Appl Probab Stst，1993（9）：296-309.

[4]Berger T，Ye，Z.Entropic aspects of random fields on trees[J].IEEE Trans Inform Theory，1990，36（5）：1006-1018.

[5]Ye Z，Berger T.Ergodic regularity and asymptotic equipartition property of random fields on trees[J].Combin Inform System Sci，1996，21（2）：157-184.

[6]Yang W G.Some limit properties for Markov chains indexed by homogeneous tree[J].Stat Probab Letts，2003，65：241-250.

[7]Yang W G，Ye Z.The asymptotic equipartition property for nonhomogeneous Markov chains indexed by a homogeneous tree[J].IEEE Trans Inform Theory，2007，53：3275-3280.

[8]Peng W C，Yang W G，Wang B.A class of small deviation theorems for functionals of random fields on a homogeneous tree[J].Journal of Mathematical Analysis and Applications，2010，361：293-301.

[9]Shi Z Y，Yang W G.Some limit properties for the mth-order nonhomogeneous Markov chains indexed by an m rooted Cayley tree[J].Statistics& Probability Letters，2010（15－16）：1223-1233.

[10]Yang W G，Tao L L，Cheng X J.On the almost everywhere convergence for arbitrary stochastic sequence[J].Acta Mathematica Scientia，2014，34：1634-1642.

[11]Liu W，Wang L Y.The Markov approximation of the random fields on Cayley tree and a class of small deviation theorems[J].Stat Probab Letts，2003，63：113-121.

[12]Chung K L.A Course in Probability Theory[M].New York：Academic Press，1974.

Limit theorems for Markov information source on gambling systems indexed by a double rooted tree

GU Xiaoping
（Department of Higher Vocational，Wuxi radio and TV University，Wuxi 214011，China）

This paper aims to study some limit properties of second-order nonhomogeneous Markov information source indexed by a double rooted tree.By constructing the consistent distribution and nonnegative super-martingale,the author obtained a class of generalized Shannon-McMillan theorems for the second-order nonhomogeneous Markov information source indexed by a double rooted tree on the generalized gambling system.And the existed results were generalized.

second-order nonhomogeneous Markov information source；double rooted tree；Shannon-McMillan theorem；generalized gambling system；relative entropy density

O211.6MR（2000）Subject Classification：60F15

A

1672－0687（2015）02－0024－06

責(zé)任編輯：謝金春

2014－09－05

江蘇城市職業(yè)學(xué)院“十二五”規(guī)劃課題項(xiàng)目（12SEW-Y-039）

顧小萍（1979-），女，江蘇無(wú)錫人，講師，碩士，研究方向：概率論。