第三章马尔科夫源

1第三章马尔科夫源本节分析问题：马尔科夫源的定义马尔科夫源的编码定理内容：一、马尔科夫源的定义1．马尔科夫源是有记忆源；2．有记忆信源的“状态”概念，信源产生消息符号与信源所处的状态有关。信源状态要合理设置，有利于描述信源输出特性。举例：某信源U={0,1},其任一时刻的输出由它前面输出的两个字母决定。则可设置两个字母构成其状态，共有00，01，10，11四个状态。若进一步规定其状态转移概率矩阵为：00011011Q={Qji}=111001008.02.000005.05.05.05.000002.08.0则可画出该信源的状态转移图如下：3．状态转移概率表示：，设信源输出表示为：Ｕ1，Ｕ2，…，Ｕl，…，其中Ｕl为随机变量，取值范围：Ａ＝｛ａ１，ａ２，…ａｋ｝011000110(0.8)1(0.2)0(0.5)1(0.5)0(0.5)1(0.5)0(0.2)1(0.8)2信源的随机状态序列为：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-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)=01（3）3注：（3）式不代表从Sl-1状态只能转到Sl状态，因为还有一个ul=ak条件。二、马氏过程的几个概念1．过渡状态：可到达其它状态而不能返回自身的状态；2．闭集：是某个状态子集，该集中任一状态不可能转到任何集外状态；3．既约状态集：任一状态皆可到达集中任何其它状态的闭集；4．吸收状态：闭集仅有一个状态时，该状态为吸收状态；5．闭包：若干闭集的交集称为闭包，闭包仍是闭集；6．既约（不可分）马氏链定义：整个状态集S是唯一既约状态集的马氏链；7．n步转移概率矩阵马氏链可由状态转移概率矩阵描述，即：Q={Qji}=QQQQQQQQQJJJJJJ212222111211其中，Qji≥0，Jj1Qji=1，i=1,2,…,J其n步转移概率矩阵为：Q(n)=QQ(n-1)=Q(n-1)Q=Q(k)Q(n-k),k＜n也就是：Qnji)(=kQlki)(Qlnjk)(——切普曼—柯尔莫果洛夫方程（5）8．从状态i出发返回到状态i的概率fi设fni)(=P{Sl≠i,l=1,2,…,n-1,Sl=iS0=i}为从状态i出发经过n步后返回状态i的条件概率；则fi=1nfni)(（6）49．从状态i出发返回到状态i的所需平均步数μiμi=1nnfni)((7)10．fi＜1——状态i为非常返状态（过渡状态）；fi=1——状态i为常返状态；其中μi=为消极常返状态，μi＜为积极常返状态。11．fni)(＞0的所有可能步数n的最大公约数t＞1时，状态i为周其状态；t=1时，状态i为非周其状态，或称各态历经状态。12．定理：有限既约马氏链一定存在有平稳分布（P(sl=i)=qi0，l和i任意），其初始分布为其平稳分布的充要条件为：qi=CjqjQji≥0Ciqi=1其中，C为状态集，当状态集是既约遍历的（常返的）时，有limnQnji)(=i1＞0，且{i1}就是平稳分布，平稳分布是唯一的。三、马尔可夫源的编码定理1．马尔可夫源的熵2．编码定理