二根樹指標馬氏信源關于賭博系統的極限定理

顧小萍

（無錫市廣播電視大學五年制高職部，江蘇無錫214011）

二根樹指標馬氏信源關于賭博系統的極限定理

顧小萍

（無錫市廣播電視大學五年制高職部，江蘇無錫214011）

研究任意二根樹圖上二階非齊次馬氏信源的極限性質。通過構造相容分布和非負上鞅的方法，得到了任意無限連通二根樹上二階非齊次馬氏信源關于廣義賭博系統的一類廣義漸近均勻分割性定理，也稱廣義Shannon-McMillan定理，并推廣了已有的結果。

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

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

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

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

圖1 二根樹TC，3

分別為定義在G2上的二維概率分布和G3上的二階隨機轉移矩陣族，如果對于任意頂點t，

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

由（1），（2）式可得樹指標二階非齊次馬氏鏈的聯合分布為

這里|T（n）|表示從第－1層到第n層的所有頂點的個數，則稱fn（ω）為樹T的子圖T（n）上關于測度P的相對熵密度。

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

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

令Y0=y（y為任意實數），Yt=f|t|（X1t，X2t，…，X0，X－1），|t|≥2。其中|t|代表從頂點t到根頂點-1的邊數或者距離。fn（x1，…，xn）稱為廣義隨機選擇函數，{Yt，t∈T{0，－1}}稱為二根樹指標廣義賭博系統或廣義隨機選擇系統，傳統的鏈式賭博系統{Yn，n≥0}在兩點集{0，1}中取值。

定義3設{Xt，t∈T}如上定義的樹指標二階非齊次馬氏鏈，{Yt，t∈T{0，－1}}為如上定義的廣義隨機選擇系統，稱

為樹指標二階非齊次馬氏鏈{Xt，t∈T}關于廣義隨機選擇系統的相對熵密度，也稱其為廣義相對熵密度。顯然，當Yt≡1，t∈T（n）時，該廣義相對熵密度即為一般的相對熵密度。

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

1 主要結果及證明

定義4設

稱Ht（Xt|X1t，X2t）為Xt關于X1t，X2t的隨機條件熵。

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

則有

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

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

注在推論1中當{Xt，t∈T}退化為單根樹指標一階非齊次馬氏信源時，有

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

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

由（11）式，令

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

因而，有

由Doob鞅收斂定理[12]可知{Un（λ，ω），Fn，n≥1}是一非負上鞅。且有

由（9）與（15）式，有

又由（13）與（16）式有

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

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

設0＜λ＜1，由（18）式有

考慮函數

求導得

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

由（21）與（19）式，當0＜λ＜1時有

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

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

當-1＜λ＜0時，由（18）式有

這時，由（21）和（25）式有

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

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

由（24）與（28）式有

于是（10）式成立。

2 結語

通過構造非負上鞅和相容分布的方法，研究了任意局部有限二根樹指標二階非齊次非齊次馬氏鏈關于廣義賭博系統的熵定理，即Shannon-McMillan定理，推廣了已有的結果。樹形圖上的信息熵定理目前國內外的研究結果較少，文中的結果對于樹形圖上的信息論編碼理論具有一定的指導意義。

[1]劉文，楊衛國.任意信源二元函數一類平均值的極限性質[J].應用概率統計，1995，11（2）：195-203.

[2]劉文，楊衛國.任意信源與馬氏信源的比較及小偏差定理[J].數學學報，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

責任編輯：謝金春

2014－09－05

江蘇城市職業學院“十二五”規劃課題項目（12SEW-Y-039）

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