信息論匯總馬爾科夫信源

1信源與信息熵第二章信息論匯總馬爾科夫信源1/322信源分類2、離散信源{離散無記憶信源離散有記憶信源{{發(fā)出單個(gè)符號(hào)無記憶信源發(fā)出符號(hào)序列無記憶信源發(fā)出符號(hào)序列有記憶信源發(fā)出符號(hào)序列馬爾可夫信源1、連續(xù)信源信息論匯總馬爾科夫信源2/323表述有記憶信源需在N維隨機(jī)矢量聯(lián)合概率分布中，引入條件概率分布來說明它們之間關(guān)聯(lián)。信息論匯總馬爾科夫信源3/3242.1.3馬爾可夫信源馬爾可夫信源一類相對(duì)簡單離散平穩(wěn)有記憶信源該信源在某一時(shí)刻發(fā)出字母概率除與該字母相關(guān)外,只與以前發(fā)出有限個(gè)字母相關(guān)m階馬爾可夫信源：信源輸出某一符號(hào)概率僅與以前m個(gè)符號(hào)相關(guān)，而與更前面符號(hào)無關(guān)。條件概率信息論匯總馬爾科夫信源4/325馬氏鏈基本概念一階馬爾可夫信源：若把有限個(gè)字母記作一個(gè)狀態(tài)S，則信源發(fā)出某一字母概率除與該字母相關(guān)外，只與該時(shí)刻信源所處狀態(tài)相關(guān)。信源未來狀態(tài)及其送出字母將只與信源現(xiàn)在狀態(tài)相關(guān)，而與信源過去狀態(tài)無關(guān)。引入狀態(tài)變量好處：使得高階馬爾科夫過程能夠轉(zhuǎn)化為一階馬爾科夫過程處理。信息論匯總馬爾科夫信源5/326馬氏鏈基本概念令si

=(xi1,

xi2,

…xim)xi1,,xi2,

…xim

∈(a1,

a2,

…an)狀態(tài)集S={s1,s2,…,sQ}Q=nm信源輸出隨機(jī)符號(hào)序列為：x1,x2,…xi-1,xi…信源所處隨機(jī)狀態(tài)序列為：s1,s2,…si-1,si

…例：二元序列為…01011100…考慮m=2，Q=nm=22=4s1=00s2=01s3=10s4=11變換成對(duì)應(yīng)狀態(tài)序列為

…s2s3s2s4s4s3s1…信息論匯總馬爾科夫信源6/327馬爾可夫信源設(shè)信源在時(shí)刻m處于si狀態(tài),它在下一時(shí)刻(m+1)狀態(tài)轉(zhuǎn)移到sj轉(zhuǎn)移概率為：

pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}pij(m)：基本轉(zhuǎn)移概率（一步轉(zhuǎn)移概率）若pij(m)與m取值無關(guān),則稱為齊次馬爾可夫鏈

pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}pij含有以下性質(zhì)：

pij≥0信息論匯總馬爾科夫信源7/328若信源處于某一狀態(tài)si,當(dāng)它發(fā)出一個(gè)符號(hào)后,所處狀態(tài)就變了,任何時(shí)候信源處于什么狀態(tài)完全由前一時(shí)刻狀態(tài)和發(fā)出符號(hào)決定。系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間S={s1,s2,…,sQ}中任意一個(gè)狀態(tài),狀態(tài)轉(zhuǎn)移時(shí),轉(zhuǎn)移概率矩陣符號(hào)條件概率矩陣區(qū)分信息論匯總馬爾科夫信源8/329例2-1，如圖所表示是一個(gè)相對(duì)碼編碼器,輸入碼Xr(r=1,2,…)是相互獨(dú)立，取值0或1，且已知P(X=0)=p,P(X=1)=1－p=q，輸出碼是Yr，顯然TXrYrYr-1+Yr是一個(gè)馬氏鏈,Yr確定后,Yr+1概率分布只與Yr相關(guān),與Yr-1

、Yr-2…等無關(guān),且知Yr序列條件概率注：⊕模2加信息論匯總馬爾科夫信源9/3210sos1pqqpp00=P(Y2=0/Y1=0)=P(X=0)=pp01=P(Y2=1/Y1=0)=P(X=1)=qp10=P(Y2=0/Y1=1)=P(X=1)=qp11=P(Y2=1/Y1=1)=P(X=0)=p

狀態(tài)轉(zhuǎn)移矩陣與時(shí)刻無關(guān)，所以是齊次。信息論匯總馬爾科夫信源10/3211馬爾可夫信源狀態(tài)轉(zhuǎn)移圖齊次馬爾可夫鏈能夠用其狀態(tài)轉(zhuǎn)移圖(香農(nóng)線圖)表示每個(gè)圓圈代表一個(gè)狀態(tài)

狀態(tài)之間有向線代表某一狀態(tài)向另一狀態(tài)轉(zhuǎn)移有向線一側(cè)符號(hào)和數(shù)字分別代表發(fā)出符號(hào)和條件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.7信息論匯總馬爾科夫信源11/32例2設(shè)一個(gè)二元一階馬爾科夫信源，信源符號(hào)集X={0,1}，信源輸出符號(hào)條件概率為p(0|0)=0.25,p(0|1)=0.5,p(1|0)=0.75,p(1|1)=0.5求狀態(tài)轉(zhuǎn)移概率，畫出狀態(tài)轉(zhuǎn)移圖。12011：0.750：0.50：0.251：0.5信息論匯總馬爾科夫信源12/32例3設(shè)有一個(gè)二元二階馬爾科夫信源，其信源符號(hào)集X={0,1}，信源輸出符號(hào)條件概率為P(0|00)=p(1|11)=0.8,p(1|00)=0.2p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5求狀態(tài)轉(zhuǎn)移概率矩陣，畫出狀態(tài)轉(zhuǎn)移圖解：13因?yàn)樾旁粗豢赡馨l(fā)出0或者1，所以信源下一時(shí)刻只可能轉(zhuǎn)移到其中兩種狀態(tài)之一。如當(dāng)前所處狀態(tài)為00，那么下一時(shí)刻信源只可轉(zhuǎn)移到00或者01。而不會(huì)轉(zhuǎn)到10或者11狀態(tài)。信息論匯總馬爾科夫信源13/3214000110110：0.80：0.51：0.20：0.51：0.51：0.50：0.21：0.2信息論匯總馬爾科夫信源14/3215齊次馬爾可夫鏈中狀態(tài)能夠依據(jù)其性質(zhì)進(jìn)行分類:1、如狀態(tài)si經(jīng)若干步后總能抵達(dá)狀態(tài)sj，即存在k,使pij(k)＞0，則稱si可抵達(dá)sj;若兩個(gè)狀態(tài)相互可抵達(dá),則稱此二狀態(tài)相通；2、過渡態(tài)：一個(gè)狀態(tài)經(jīng)過若干步以后總能抵達(dá)某一其它狀態(tài)，但不能從其它狀態(tài)返回；3、吸收態(tài)：一個(gè)只能從本身返回到本身而不能抵達(dá)其它任何狀態(tài)狀態(tài)；4、常返態(tài)：經(jīng)有限步后遲早要返回狀態(tài)；5、周期性：在常返態(tài)中，有些狀態(tài)僅當(dāng)k能被某整數(shù)d＞1整除時(shí)才有pii(k)＞0；6、非周期性：對(duì)于pii(k)＞0全部k值，其最大條約數(shù)為1。信息論匯總馬爾科夫信源15/3216s3s2s4s5s1s6周期性：在常返態(tài)中,有些狀態(tài)僅當(dāng)k能被某整數(shù)d＞1整除時(shí)才有pii(k)＞0,圖中周期為2；x5:1非周期性：對(duì)于pii(k)＞0全部k值，其最大條約數(shù)為1。常返態(tài)：經(jīng)有限步后遲早要返回狀態(tài)，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4過渡態(tài)吸收態(tài)相通信息論匯總馬爾科夫信源16/3217馬爾可夫信源遍歷狀態(tài)：非周期、常返狀態(tài),如圖中狀態(tài)s2和s3閉集：狀態(tài)空間中某一子集中任何一狀態(tài)都不能抵達(dá)子集以外任何狀態(tài)不可約：閉集中除本身全體外再?zèng)]有其它閉集特殊結(jié)論信息論匯總馬爾科夫信源17/3218馬爾可夫信源一個(gè)不可約、非周期、狀態(tài)有限馬爾可夫鏈其k步轉(zhuǎn)移概率pij(k)在k→∞時(shí)趨于一個(gè)和初始狀態(tài)無關(guān)極限概率Wj，它是滿足方程組唯一解；Wj

：馬爾可夫鏈一個(gè)平穩(wěn)分布，

Wj[或p(sj)]就是系統(tǒng)此時(shí)處于狀態(tài)sj概率。不論隨機(jī)點(diǎn)從哪一個(gè)狀態(tài)si出發(fā)，當(dāng)轉(zhuǎn)移步數(shù)k足夠大時(shí)，轉(zhuǎn)移到狀態(tài)sj概率pij(k)都近似于一個(gè)常數(shù)Wj信息論匯總馬爾科夫信源18/3219sos11/0.60/0.30/0.4s21/0.20/0.81/0.7例4信息論匯總馬爾科夫信源19/3220例5：有一個(gè)二元二階馬爾可夫信源,其信源符號(hào)集為{0，1}，已知符號(hào)條件概率：

p(0|00)=1/2p(1|00)=1/2p(0|01)=1/3p(1|01)=2/3p(0|10)=1/4p(1|10)=3/4p(0|11)=1/5p(1|11)=4/5求：⑴信源全部狀態(tài)及狀態(tài)轉(zhuǎn)移概率⑵畫出完整二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖。⑶求平穩(wěn)分布概率

信息論匯總馬爾科夫信源20/3221狀態(tài)轉(zhuǎn)移概率矩陣符號(hào)條件概率矩陣(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/5信息論匯總馬爾科夫信源21/3222穩(wěn)態(tài)分布概率穩(wěn)態(tài)后符號(hào)概率分布信息論匯總馬爾科夫信源22/3223例6

一個(gè)二元二階馬爾可夫信源,其信源符號(hào)集為{0,1}信源開始時(shí)：p(0)=p(1)=0.5發(fā)出隨機(jī)變量X1。

下一單位時(shí)間：輸出隨機(jī)變量X2與X1有依賴關(guān)系x2x10100.30.410.70.6p(x2|x1)再下一單位時(shí)間：輸出隨機(jī)變量X3與X2X1有依賴關(guān)系x3x1x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)信息論匯總馬爾科夫信源23/32從第四單位時(shí)間開始，隨機(jī)變量Xi只與前面二個(gè)單位時(shí)間隨機(jī)變量Xi-2Xi-1有依賴關(guān)系:p(xi|xi-1

xi-2…x2

x1)=p(xi|xi-1

xi-2)(i＞3)且

p(xi|xi-1

xi-2)=p(x3|x2x1)(i＞3)求：⑴信源狀態(tài)轉(zhuǎn)移情況和對(duì)應(yīng)概率；⑵畫出完整二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖；⑶求平穩(wěn)分布概率；

（4）馬爾科夫信源到達(dá)穩(wěn)定后，0和1分布概率。

信息論匯總馬爾科夫信源24/3225解:設(shè)信源開始處于s0狀態(tài),并以等概率發(fā)出符號(hào)0和1,分別抵達(dá)狀態(tài)s1和s2

:若處于s1,以0.3和0.7概率發(fā)出0和1抵達(dá)s3和s4若處于s2,以0.4和0.6概率發(fā)出0和1抵達(dá)s5和s600011011(0)0.5(1)0.5(0)0.3(0)0.4(1)0.7(1)0.6s1s2s0s6s5s4s3信息論匯總馬爾科夫信源25/3226信源發(fā)完第2個(gè)符號(hào)后再發(fā)第3個(gè)及以后符號(hào)。從第3單位時(shí)間以后信源必處于s3

s4s5

s6四種狀態(tài)之一。在i≥3后,信源狀態(tài)轉(zhuǎn)移可用下列圖表示:10110100(0)0.3(0)0.4(1)0.7(0)0.2(1)0.8(1)0.6(0)0.4(1)0.6狀態(tài)s1和s5功效是完全相同狀態(tài)s2和s6功效是完全相同可將二圖合并成s3s4s5s6s0(0)0.5(1)0.5s0是過渡狀態(tài)s3

s4s5

s6組成一個(gè)不可約閉集,而且含有遍歷性。發(fā)出0、1概率相同，狀態(tài)轉(zhuǎn)移改變相同信息論匯總馬爾科夫信源26/3227由題意,此馬爾可夫信源狀態(tài)必定會(huì)進(jìn)入這個(gè)不可約閉集,所以我們計(jì)算信源熵時(shí)能夠不考慮過渡狀態(tài)及過渡過程。由得穩(wěn)態(tài)分布概率Wj=p(sj)信息論匯總馬爾科夫信源27/3228當(dāng)馬爾可夫信源到達(dá)穩(wěn)定后,符號(hào)0和符號(hào)1概率分布：信源到達(dá)穩(wěn)定后，信源符號(hào)概率分布與初始時(shí)刻概率分布是不一樣，所以，普通馬爾可夫信源并非是平穩(wěn)信源。但當(dāng)初齊、遍歷馬爾可夫信源到達(dá)穩(wěn)定后，這時(shí)就能夠看成一個(gè)平穩(wěn)信源。：信息論匯總馬爾科夫信源28/3229習(xí)題2-12-2信息論匯總馬爾科夫信源29/3230馬爾可夫鏈馬爾可夫鏈，因安德烈?馬爾可夫（A.A.Markov，1856－1922）得名，是數(shù)學(xué)中含有馬爾可夫性質(zhì)離散時(shí)間隨機(jī)過程。該過程中，在給定當(dāng)前知識(shí)或信息情況下，過去（即當(dāng)期以前歷史狀態(tài)）對(duì)于預(yù)測未來（即當(dāng)期以后未來狀態(tài)）是無關(guān)。

馬爾可夫鏈?zhǔn)请S機(jī)變量X_1,X_2,X_3...一個(gè)數(shù)列。這些變量范圍，即他們?nèi)靠赡苋≈导?，被稱為“狀態(tài)空間”，而X_n值則是在時(shí)間<math>n</math>狀態(tài)。假如X_{n+1}對(duì)于過去狀態(tài)條件概率分布僅是X_n一個(gè)函數(shù)，則

P(X_{n+1}=x|X_0,X_1,X_2,\ldots,X_n)=P(X_{n+1}=x|X_n).

這里x為過程中某個(gè)狀態(tài)。上面這個(gè)恒等式能夠被看作是馬爾可夫性質(zhì)。

馬爾可夫在1906年首先做出了這類過程。而將此普通化到可數(shù)無限狀態(tài)空間是由柯爾莫果洛夫在1936年給出。

信息論匯總馬爾科夫信源30/3231

馬爾可夫鏈與布朗運(yùn)動(dòng)以及遍歷假說這兩個(gè)二十世紀(jì)早期物理學(xué)主要課題是相聯(lián)絡(luò)，但馬爾可夫?qū)で笏坪醪坏跀?shù)學(xué)動(dòng)機(jī)，名義上是對(duì)于縱屬事件大數(shù)法則擴(kuò)張。物理馬爾可夫鏈通慣用來建模排隊(duì)理論和統(tǒng)計(jì)學(xué)中建模，還可作為信號(hào)模型用于熵編碼技術(shù)，如算術(shù)編碼（著名LZMA數(shù)據(jù)壓縮算法就使用了馬爾可夫鏈