第三章马尔科夫源

1、第三章 马尔科夫源本节分析问题：马尔科夫源的定义马尔科夫源的编码定理内容：一、马尔科夫源的定义1马尔科夫源是有记忆源；2有记忆信源的“状态”概念，信源产生消息符号与信源所处的状态有关。信源状态要合理设置，有利于描述信源输出特性。 举例：某信源U=0,1,其任一时刻的输出由它前面输出的两个字母决定。则可设置两个字母构成其状态，共有00，01，10，11四个状态。若进一步规定其状态转移概率矩阵为： 00 01 10 11Q=Qji=则可画出该信源的状态转移图如下：011000110(0.8)1(0.2)0(0.5)1(0.5)0(0.5)1(0.5)0(0.2)1(0.8)3状态转移概率表示：，设

2、信源输出表示为：1，2，l，其中l为随机变量，取值范围：， 信源的随机状态序列为：S1，S2，Sl， 则用：Pj(ak)=P(ul= akSl=j)第l时刻（前一时刻）信源处于j状态下产生符号为ak的概率； Qji=P(Sl=iSl-1=j)第l-1时刻信源处于第j个状态，而第l时刻转到第i个状态的概率。4马氏链的定义某随机状态序列S1，S2，Sl，满足下述条件时，称为有限状态齐次马尔科夫链，简称马氏链。（1） 可能的总状态数J有限，J；（2） 状态转移概率Qji只由状态j和i而定，与时间无关（时齐性）；（3） 进入某一状态的概率只与前一时刻有关，而与更早状态无关（马氏性），即 P(SlSl-

3、1，Sl-2，)= P(SlSl-1) （1）注：满足P(SlSl-1，Sl-2，)= P(SlSl-1，Sl-2，Sl-m)，即Sl仅与前m个状态有关时，为m阶马氏链，而前者为简单马氏链。5马尔科夫源的定义 信源的状态及其输出序列满足下述条件时，称为马尔科夫源（1） 某一时刻信源的输出仅与该时刻信源状态有关，而与此前状态无关，即Pj(ak)=P(ul= akSl=j，ul-1，Sl-1，)= P(ul= akSl=j) （2）（2） 信源状态由当前输出字母及前一时刻的信源状态唯一确定，即：P(Sl=iul= ak，Sl-1=j)= （3）注：（3）式不代表从Sl-1状态只能转到Sl状态，因为

4、还有一个ul= ak条件。二、马氏过程的几个概念1过渡状态：可到达其它状态而不能返回自身的状态；2闭集：是某个状态子集，该集中任一状态不可能转到任何集外状态；3既约状态集：任一状态皆可到达集中任何其它状态的闭集；4吸收状态：闭集仅有一个状态时，该状态为吸收状态；5闭包：若干闭集的交集称为闭包，闭包仍是闭集；6既约（不可分）马氏链定义：整个状态集S是唯一既约状态集的马氏链；7n步转移概率矩阵 马氏链可由状态转移概率矩阵描述，即：Q=Qji= 其中，Qji0，Qji=1，i=1,2, ,J 其n步转移概率矩阵为：Q(n)=Q Q(n-1)=Q(n-1) Q= Q(k) Q(n-k) , kn 也就

5、是：=切普曼柯尔莫果洛夫方程 （5）8从状态i出发返回到状态i的概率fi 设=PSli, l=1,2, ,n-1, Sl=iS0=i 为从状态i出发经过n步后返回状态i的条件概率；则fi= （6）9从状态i出发返回到状态i的所需平均步数i i=n (7)10fi1状态i为非常返状态（过渡状态）；fi=1状态i为常返状态；其中i=为消极常返状态，i为积极常返状态。110的所有可能步数n的最大公约数t1时，状态i为周其状态；t=1时，状态i为非周其状态，或称各态历经状态。12定理：有限既约马氏链一定存在有平稳分布（P(sl=i)=qi0， l和i任意），其初始分布为其平稳分布的充要条件为： qi=qjQji0