信息论汇总马尔科夫信源

1信源与信息熵第二章信息论汇总马尔科夫信源1/322信源分类2、离散信源{离散无记忆信源离散有记忆信源{{发出单个符号无记忆信源发出符号序列无记忆信源发出符号序列有记忆信源发出符号序列马尔可夫信源1、连续信源信息论汇总马尔科夫信源2/323表述有记忆信源需在N维随机矢量联合概率分布中，引入条件概率分布来说明它们之间关联。信息论汇总马尔科夫信源3/3242.1.3马尔可夫信源马尔可夫信源一类相对简单离散平稳有记忆信源该信源在某一时刻发出字母概率除与该字母相关外,只与以前发出有限个字母相关m阶马尔可夫信源：信源输出某一符号概率仅与以前m个符号相关，而与更前面符号无关。条件概率信息论汇总马尔科夫信源4/325马氏链基本概念一阶马尔可夫信源：若把有限个字母记作一个状态S，则信源发出某一字母概率除与该字母相关外，只与该时刻信源所处状态相关。信源未来状态及其送出字母将只与信源现在状态相关，而与信源过去状态无关。引入状态变量好处：使得高阶马尔科夫过程能够转化为一阶马尔科夫过程处理。信息论汇总马尔科夫信源5/326马氏链基本概念令si

=(xi1,

xi2,

…xim)xi1,,xi2,

…xim

∈(a1,

a2,

…an)状态集S={s1,s2,…,sQ}Q=nm信源输出随机符号序列为：x1,x2,…xi-1,xi…信源所处随机状态序列为：s1,s2,…si-1,si

…例：二元序列为…01011100…考虑m=2，Q=nm=22=4s1=00s2=01s3=10s4=11变换成对应状态序列为

…s2s3s2s4s4s3s1…信息论汇总马尔科夫信源6/327马尔可夫信源设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj转移概率为：

pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}pij(m)：基本转移概率（一步转移概率）若pij(m)与m取值无关,则称为齐次马尔可夫链

pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}pij含有以下性质：

pij≥0信息论汇总马尔科夫信源7/328若信源处于某一状态si,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻状态和发出符号决定。系统在任一时刻可处于状态空间S={s1,s2,…,sQ}中任意一个状态,状态转移时,转移概率矩阵符号条件概率矩阵区分信息论汇总马尔科夫信源8/329例2-1，如图所表示是一个相对码编码器,输入码Xr(r=1,2,…)是相互独立，取值0或1，且已知P(X=0)=p,P(X=1)=1－p=q，输出码是Yr，显然TXrYrYr-1+Yr是一个马氏链,Yr确定后,Yr+1概率分布只与Yr相关,与Yr-1

、Yr-2…等无关,且知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

状态转移矩阵与时刻无关，所以是齐次。信息论汇总马尔科夫信源10/3211马尔可夫信源状态转移图齐次马尔可夫链能够用其状态转移图(香农线图)表示每个圆圈代表一个状态

状态之间有向线代表某一状态向另一状态转移有向线一侧符号和数字分别代表发出符号和条件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.7信息论汇总马尔科夫信源11/32例2设一个二元一阶马尔科夫信源，信源符号集X={0,1}，信源输出符号条件概率为p(0|0)=0.25,p(0|1)=0.5,p(1|0)=0.75,p(1|1)=0.5求状态转移概率，画出状态转移图。12011：0.750：0.50：0.251：0.5信息论汇总马尔科夫信源12/32例3设有一个二元二阶马尔科夫信源，其信源符号集X={0,1}，信源输出符号条件概率为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求状态转移概率矩阵，画出状态转移图解：13因为信源只可能发出0或者1，所以信源下一时刻只可能转移到其中两种状态之一。如当前所处状态为00，那么下一时刻信源只可转移到00或者01。而不会转到10或者11状态。信息论汇总马尔科夫信源13/3214000110110：0.80：0.51：0.20：0.51：0.51：0.50：0.21：0.2信息论汇总马尔科夫信源14/3215齐次马尔可夫链中状态能够依据其性质进行分类:1、如状态si经若干步后总能抵达状态sj，即存在k,使pij(k)＞0，则称si可抵达sj;若两个状态相互可抵达,则称此二状态相通；2、过渡态：一个状态经过若干步以后总能抵达某一其它状态，但不能从其它状态返回；3、吸收态：一个只能从本身返回到本身而不能抵达其它任何状态状态；4、常返态：经有限步后迟早要返回状态；5、周期性：在常返态中，有些状态仅当k能被某整数d＞1整除时才有pii(k)＞0；6、非周期性：对于pii(k)＞0全部k值，其最大条约数为1。信息论汇总马尔科夫信源15/3216s3s2s4s5s1s6周期性：在常返态中,有些状态仅当k能被某整数d＞1整除时才有pii(k)＞0,图中周期为2；x5:1非周期性：对于pii(k)＞0全部k值，其最大条约数为1。常返态：经有限步后迟早要返回状态，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4过渡态吸收态相通信息论汇总马尔科夫信源16/3217马尔可夫信源遍历状态：非周期、常返状态,如图中状态s2和s3闭集：状态空间中某一子集中任何一状态都不能抵达子集以外任何状态不可约：闭集中除本身全体外再没有其它闭集特殊结论信息论汇总马尔科夫信源17/3218马尔可夫信源一个不可约、非周期、状态有限马尔可夫链其k步转移概率pij(k)在k→∞时趋于一个和初始状态无关极限概率Wj，它是满足方程组唯一解；Wj

：马尔可夫链一个平稳分布，

Wj[或p(sj)]就是系统此时处于状态sj概率。不论随机点从哪一个状态si出发，当转移步数k足够大时，转移到状态sj概率pij(k)都近似于一个常数Wj信息论汇总马尔科夫信源18/3219sos11/0.60/0.30/0.4s21/0.20/0.81/0.7例4信息论汇总马尔科夫信源19/3220例5：有一个二元二阶马尔可夫信源,其信源符号集为{0，1}，已知符号条件概率：

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求：⑴信源全部状态及状态转移概率⑵画出完整二阶马尔可夫信源状态转移图。⑶求平稳分布概率

信息论汇总马尔科夫信源20/3221状态转移概率矩阵符号条件概率矩阵(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稳态分布概率稳态后符号概率分布信息论汇总马尔科夫信源22/3223例6

一个二元二阶马尔可夫信源,其信源符号集为{0,1}信源开始时：p(0)=p(1)=0.5发出随机变量X1。

下一单位时间：输出随机变量X2与X1有依赖关系x2x10100.30.410.70.6p(x2|x1)再下一单位时间：输出随机变量X3与X2X1有依赖关系x3x1x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)信息论汇总马尔科夫信源23/32从第四单位时间开始，随机变量Xi只与前面二个单位时间随机变量Xi-2Xi-1有依赖关系: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)求：⑴信源状态转移情况和对应概率；⑵画出完整二阶马尔可夫信源状态转移图；⑶求平稳分布概率；

（4）马尔科夫信源到达稳定后，0和1分布概率。

信息论汇总马尔科夫信源24/3225解:设信源开始处于s0状态,并以等概率发出符号0和1,分别抵达状态s1和s2

:若处于s1,以0.3和0.7概率发出0和1抵达s3和s4若处于s2,以0.4和0.6概率发出0和1抵达s5和s600011011(0)0.5(1)0.5(0)0.3(0)0.4(1)0.7(1)0.6s1s2s0s6s5s4s3信息论汇总马尔科夫信源25/3226信源发完第2个符号后再发第3个及以后符号。从第3单位时间以后信源必处于s3

s4s5

s6四种状态之一。在i≥3后,信源状态转移可用下列图表示: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状态s1和s5功效是完全相同状态s2和s6功效是完全相同可将二图合并成s3s4s5s6s0(0)0.5(1)0.5s0是过渡状态s3

s4s5

s6组成一个不可约闭集,而且含有遍历性。发出0、1概率相同，状态转移改变相同信息论汇总马尔科夫信源26/3227由题意,此马尔可夫信源状态必定会进入这个不可约闭集,所以我们计算信源熵时能够不考虑过渡状态及过渡过程。由得稳态分布概率Wj=p(sj)信息论汇总马尔科夫信源27/3228当马尔可夫信源到达稳定后,符号0和符号1概率分布：信源到达稳定后，信源符号概率分布与初始时刻概率分布是不一样，所以，普通马尔可夫信源并非是平稳信源。但当初齐、遍历马尔可夫信源到达稳定后，这时就能够看成一个平稳信源。：信息论汇总马尔科夫信源28/3229习题2-12-2信息论汇总马尔科夫信源29/3230马尔可夫链马尔可夫链，因安德烈•马尔可夫（A.A.Markov，1856－1922）得名，是数学中含有马尔可夫性质离散时间随机过程。该过程中，在给定当前知识或信息情况下，过去（即当期以前历史状态）对于预测未来（即当期以后未来状态）是无关。

马尔可夫链是随机变量X_1,X_2,X_3...一个数列。这些变量范围，即他们全部可能取值集合，被称为“状态空间”，而X_n值则是在时间<math>n</math>状态。假如X_{n+1}对于过去状态条件概率分布仅是X_n一个函数，则

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

这里x为过程中某个状态。上面这个恒等式能够被看作是马尔可夫性质。

马尔可夫在1906年首先做出了这类过程。而将此普通化到可数无限状态空间是由柯尔莫果洛夫在1936年给出。

信息论汇总马尔科夫信源30/3231

马尔可夫链与布朗运动以及遍历假说这两个二十世纪早期物理学主要课题是相联络，但马尔可夫寻求似乎不但于数学动机，名义上是对于纵属事件大数法则扩张。物理马尔可夫链通惯用来建模排队理论和统计学中建模，还可作为信号模型用于熵编码技术，如算术编码（著名LZMA数据压缩算法就使用了马尔可夫链