【正文】 ? ?1 1( ) l o gNkq Niii kpp?? ??? ? ?11( ) l o gNkq Niiikpp????? ??11( ) l o gNkqNiikipp????? ??111l o gNk N kqNi i i ikip p p p???? ??111( l o g )Nk k NqNi i i ikip p p p???? ??111 1 1 1l o gk k NkNq q qNi i i ik i i ip p p p? ? ? ?????????? ? ? ?11l o gkkkqNiikipp???? ??11l o gkkkqNiikipp????????????1( ) ( )NkH X NH X????擴(kuò)展信源熵的例子 ?例 ?方法一 ?方法二 ???????????????16116181161161818181413323133222123121112 aaaaaaaaaaaaaaaaaaPX2 1 1 1( ) l o g 4 l o g 8 l o g 1 6 3 /4 8 1 6H X b it? ? ? ? ? 符 號(hào)2 111( ) 2 ( ) 2 ( l o g 2 l o g 4 l o g 4 ) 3 /244H X H X b it? ? ? ? ? 符 號(hào)1 2 31 1 12 4 4a a aXXP???? ?????????， 求 的 二 次 擴(kuò) 展 信 源 的 熵 。 ?含義： 信源所發(fā)符號(hào)序列的概率分布與時(shí)間起點(diǎn)無(wú)關(guān)， 概率是平穩(wěn)的 。 ? 平穩(wěn)： p(x)不變 ， x出現(xiàn)的概率與 時(shí)間 無(wú)關(guān)。 1211( ) ( ) ( , , , )NNNH X H X H X X XNN??( ) l i m ( )NNH X H X? ??? 極限熵 ?定理 1 2 11 2 1 1 2 1()l i m ( ) l i m ( | , , , ) ,1l i m ( , , , , ) l i m ( | , , , )NN N NNNN N N NNNHXH X H X X X XH X X X X H X X X XN?? ? ? ???? ? ? ?????對(duì) 任 意 離 散 平 穩(wěn) 信 源 ， 若 ， 則即 馬爾可夫信源 ?有限記憶信源：當(dāng)前要輸出的這個(gè)符號(hào)只與前面已經(jīng)輸出的 m個(gè)符號(hào)有關(guān)。 1 2 1 2( | , , , , ) ( | , , , )t t t t m t t t t mp x x x x p x x x x? ? ? ? ? ?? 有限狀態(tài)馬爾可夫鏈 ?定義 設(shè) {Xn,n∈ N+}為一隨機(jī)序列，時(shí)間參數(shù)集N+={0,1,2,…} ，狀態(tài)空間 S={S1, S2,…, SJ}，若對(duì)所有n∈ N+，有 則稱 {Xn,n∈ N+}為 馬爾可夫鏈 。 1 2 111 2 11{ | , , , }{ | }n n nnnn i n i n i in i n iP X S X S X S X SP X S X S??????? ? ? ?? ? ?轉(zhuǎn)移概率 ?在已知 m時(shí)刻系統(tǒng)處于狀態(tài) Si的條件下，在 n時(shí)刻系統(tǒng)處于狀態(tài) Sj的概率 , ?轉(zhuǎn)移概率： pij(m,n)=P{Xn=Sj|Xm=Si}=P{Xn=j|Xm=i} ?實(shí)質(zhì)：條件概率 ?一步轉(zhuǎn)移概率： nm=1的情況，馬爾可夫鏈最關(guān)心的轉(zhuǎn)移概率。一步轉(zhuǎn)移概率和 k步轉(zhuǎn)移概率 ?一步轉(zhuǎn)移概率（基本轉(zhuǎn)移概率）： nm=1 ?k步轉(zhuǎn)移概率 : ?規(guī)定 ?轉(zhuǎn)移矩陣： ? 所有的 pij(k)(m) 組成一個(gè)矩陣 () ( ) { | }kij m k mp m P X j X i?? ? ?( 1 ) ( ) ( )ij ijp m p m?( 0 ) 1 ( )()0 ( )i j i jijpmij????? ???( ) ( ) ( )1 1 1 2 1( ) ( ) ( )2 1 2 2 2( ) ( ) ( )12( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )k k kJk k kJk k kJ J J Jp m p m p mp m p m p mPp m p m p m?????????矩陣 P中每一個(gè)元素 都是非負(fù)的，并且 每行之和均為 1 1( , 1 ) ( ) { | }ij ij m mp m m p m P X j X i?? ? ? ? ?時(shí)齊馬爾可夫鏈 ?定義 如果在馬爾可夫鏈中 pij(m)=P{Xm+1=j|Xm=i}=pij 即從狀態(tài) i轉(zhuǎn)移到狀態(tài) j的概率與 m（時(shí)間）無(wú)關(guān)，則稱這類 馬爾可夫鏈為 時(shí)齊馬爾可夫鏈 ，或 齊次馬爾可夫鏈 ，或 具有平穩(wěn)轉(zhuǎn)移概率的馬爾可夫鏈 。 n時(shí)刻的狀態(tài)分布 () ( ) ( )nj j n jrW P t n S P X S? ? ? ?? 個(gè) 狀 態(tài) 的 馬 爾 可 夫 鏈 ， 令 時(shí) 刻 的 狀 態(tài) 為( ) ( 1 ) ( 1 ) ( 1 )1 1 2 2 , ( 1 , 2 , , )n n n nj j j r r jW W p W p W p j r? ? ?? ? ? ?? ? 11 12 121 22 2( ) ( ) ( ) ( 1 ) ( 1 ) ( 1 )1 2 1 212rrn n n n n nrrr r rrp p pp p pW W W W W Wp p p? ? ?????? ? ? ??? ? ? ?????? ( ) ( 1 )nnW W P??? ( ) ( 1 ) ( 2 ) 2 ( 0 )n n n nW W P W P W P??? ? ? ?? 初始狀態(tài)分布 轉(zhuǎn)移矩陣的 n次冪 n時(shí)刻的狀態(tài)分布 齊次馬爾可夫鏈的遍歷性 ?含義：無(wú)論初始分布是什么樣的，經(jīng)過(guò)足夠長(zhǎng)的轉(zhuǎn)移之后，每種狀態(tài)出現(xiàn)的概率 穩(wěn)定 下來(lái)。 其 中 為 該 馬 爾 可定 義遍 夫 鏈 的歷 性 平 穩(wěn) 分 布 初 始 分 布 。 ?等價(jià)于：存在一個(gè)狀態(tài) Sj和正整數(shù) N，使得從任意初始狀態(tài)出發(fā)，經(jīng)過(guò) N步轉(zhuǎn)以后，一定可以達(dá)到狀態(tài) Sj。( 2) ,。?定理 求解穩(wěn)態(tài)分布 —— 例子 0 0 11 / 2 1 / 3 1 / 6 ,1 / 2 1 / 2 0P?????????設(shè) 某 馬 爾 可 夫 鏈 的 狀 態(tài) 轉(zhuǎn) 移 矩 陣 為 其 穩(wěn) 態(tài) 分 布 存 在 嗎 ？ 若 存 在 則 求 之 。1 2 32 2 33 1 21 2 3.1 / 2 1 / 21 / 3 1 / 21 / 61W P WW W WW W WW W WW W W???????? ? ?2 根 據(jù) ，有 又 有 ，解： 1 2 31 2 8 .3 7 2 1W W W? ? ?求 得 穩(wěn) 態(tài) 分 布 為 ， ， 馬爾可夫信源 ?具有馬爾可夫鏈性質(zhì)的信源 ?狀態(tài)：符號(hào)序列 ?定義 若信源輸出的符號(hào)和