1、標(biāo)準(zhǔn)數(shù)字電視（SDTV）的信息傳輸問題Quality Evolution通信系統(tǒng)的信息傳輸問題信源信道信宿01101111101011011000第三章 馬爾可夫鏈1.馬爾可夫鏈定義2.一步轉(zhuǎn)移概率及多步轉(zhuǎn)移概率3.初始概率及絕對概率4.Chapman-Kolmogorov方程5.馬爾可夫鏈狀態(tài)分類6.遍歷的馬爾可夫鏈及平穩(wěn)分布馬爾可夫鏈定義設(shè)有隨機過程Xn,nT，若對于任意的整數(shù)nT和任意的i0,i1, ,in+1I，條件概率滿足|,|11110011nnnnnnnniXiXPiXiXiXiXP則稱Xn,nT為馬爾可夫鏈，簡稱馬氏鏈將來的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，與過去狀態(tài)無關(guān)定義4.2稱條件概

2、率為馬爾可夫鏈Xn,nT在時刻n的一步轉(zhuǎn)移概率，其中i,jI，簡稱轉(zhuǎn)移概率。|)(1iXjXPnpnnij定義4.3若對任意的i,jI，馬爾可夫鏈Xn,nT的轉(zhuǎn)移概率與n無關(guān)，則稱馬爾可夫鏈?zhǔn)驱R次馬爾可夫鏈。設(shè)P表示一步轉(zhuǎn)移概率所組成的矩陣，則nnppppppP2122211211稱為系統(tǒng)狀態(tài)的一步轉(zhuǎn)移概率矩陣，它具有如下性質(zhì)：1. 2. Ijipij,0IjipIjij, 1隨機矩陣定義4.4稱條件概率為馬爾可夫鏈Xn,nT的n步轉(zhuǎn)移概率，并稱1, 0,|)(nmIjiiXjXPpmnmnij)()()(nijnpP為馬爾可夫鏈的n步轉(zhuǎn)移矩陣。例題設(shè)馬爾可夫鏈Xn,nT有狀態(tài)空間I=0,1，

3、其一步轉(zhuǎn)移概率矩陣為11100100ppppP求 和兩步轉(zhuǎn)移概率矩陣P(2)0| 02mmXXP定理4.1設(shè)Xn,nT為馬爾可夫鏈，則對任意整數(shù)n0，0L0非空，則稱該集合的最大公約數(shù)d=d(i)=G.C.Dn:pii(n)0為狀態(tài)i的周期。如d1就稱i為周期的，如d=1就稱i為非周期的。引理4.1如i的周期為d，則存在正整數(shù)M，對一切nM，有pii(nd)0。狀態(tài)轉(zhuǎn)移概率圖首中概率它表示質(zhì)點由i出發(fā)，經(jīng)n步首次到達j 的概率，表示為)|, 11 ,()(iXjXnvjXPfmnmvmnij同時我們令 表示質(zhì)點由i出發(fā)，經(jīng)有限步終于到達j 的概率。1)(nnijijff定義4.7稱狀態(tài)i為常返

4、的，如fii=1；稱狀態(tài)i為非常返的，如fii1。對于常返太i，由定義知fii(n),n1構(gòu)成一概率分布，此分布的期望值1)(nniiinf表示由i出發(fā)再返回的i的平均返回時間。定義4.8如ui0，（對一切i,jI ），則稱此馬爾可夫鏈遍歷。狀態(tài)空間的分解CiCk定義：狀態(tài)空間I的子集C稱為閉集，如果對任意 及 都有0ikp定義：閉集C稱為不可約的，如果C的狀態(tài)互通。定義：馬爾可夫鏈稱為不可約的，如果其狀態(tài)空間不可約。狀態(tài)空間的分解定理：任一馬爾可夫鏈的狀態(tài)空間I，可唯一的分解成有限個或可列個互不相交的子集D,C1,C2, 之和，使得 每一Cn是常返態(tài)組成的不可約閉集； Cn中的狀態(tài)同類，或全是正常返，或全是零常返。它們有相同的周期且fjk=1,j,kCn。 D由全體非常返狀態(tài)組成，自Cn中的狀態(tài)不能到達D中的狀態(tài)。定義4.11稱概率分布j,jI為馬爾可夫鏈的平穩(wěn)分布，若它滿足0, 1jIjjIiijijp若初始概率分布是平穩(wěn)分布，則對一切正整數(shù)n，絕對概率pj(n)等于初概率。定理4.16不可約非周期馬爾可夫鏈?zhǔn)钦７档某湟獥l件是存在平穩(wěn)分布，且此平穩(wěn)分布就是極限分布。定義：若存在一個概率分布（p1,p2, ,pk）使得(p1,p2, ,pk)= (p1,p2, ,pk)P，則稱(p1,p2, ,pk)為平穩(wěn)分布。定理：遍歷的馬爾可夫