2014第六章马尔可夫链.

第六章马尔可夫过程（Ⅰ）马尔可夫链6.1马尔可夫过程当已知随机过程在时刻所处的状态的条件下，过程在时刻所处的状态与过程在时刻以前的状态无关，而仅与过程在所处的状态有关，则称该过程为马尔可夫过程。这种特性称为随机过程的“无后效性”或马尔可夫性。it)(ittitit111111|,,|mmmmmmmmxtxxtxPxtxxtxxtxP1|11,,||,,|111mmxxmmxxxxxFxxxFmmmm1|11,,||,,|111mmxxmmxxxxxfxxxfmmmm6.1.1马尔可夫过程的概念6.1.2分类1T和E都取连续集时，称为马尔可夫过程。2若T取连续集而E取离散集时，称为可列马尔可夫过程。3若T取离散集而E取连续集时，称为马尔可夫序列。4若T和E都取离散集时，称为马尔可夫链。状态可列的马尔可夫链称为可列马尔可夫链；状态有限的马尔可夫链称为有限马尔可夫链。6.2马尔可夫链1.马尔可夫链的表示},{TttX整数或者非负整数对应}0,{nnX},2,1,0{T},2,1,0{I状态：IiiXni任意时刻状态为40X4初始时刻状态为一、马尔可夫链6.2马尔可夫链2.马尔可夫链的定义},2,1,{nXn为一随机序列，其状态空间},,,{21NaaaE，若对于任意的n，满足}|{},,,|{)1(1)()1(1)2(2)1(1)(ninninininninninaXaXPaXaXaXaXP),,2,1(Ni则称}{nX为马尔可夫链（简称马氏链）。定义：设状态有限：有限状态马尔可夫链状态无限：可列无限状态马尔可夫链1k时，有)1(ijpijijpmmp)1,(由所有一步转移概率ijp构成的矩阵NNNNNNppppppppp212222111211P①定义：Ijiixjxpkmmpmkmij,),(3.转移概率称为一步转移概率矩阵，简称转移概率矩阵。②性质：10ijpNjijp11③一步转移概率④k步转移概率)(mpkijIjiiXjXPmkm,}|{为了数学处理便利，通常规定jijimpkmPmpkijijijij01)(1)(1014.转移概率矩阵)()()()()()()()()()(212222111211mpmpmpmpmpmpmpmpmpmkNNkNkNkNkkkNkkkP)(mpkij可构成k步转移概率矩阵由所有k步转移概率（1）1)(0mpkijNjkijmp11)(（2）)()(mpmkijkP二、齐次马尔可夫链)(mpijIjiPiXjXPijmm,}|{10000121021021212121P12011/21/21/21/2三、举例111010P1.天气预报有雨0无雨1今日下雨明日下雨α今日无雨明日下雨β2.数字传输0，1数字传输Ppppp111010P3.无限制的随机的随机游动某时刻位于i以p向右移i+111011ijijijqijppijp+q=1以q向左移i-1Xn表示i所处的位置，n≥0,齐次马尔可夫链,2,1,0I000001111qpqpiiiiiiPi-1i+1iqqpq1pqpp4.带有一个吸收壁的随机游动一旦到达0状态，停在此处不动（吸收态）其它0100011ijiiiippiqppp,2,1,0I000001210210qpqP021qpq1pq5.带有两个吸收壁的随机游动0，a吸收态aI,2,1,0100000000000000000000000000011221012210pqqqpqaaaaaaP021qpq1pqa-1a-2qppqp…a16.带有一个反射壁的游动,2,1,0I0000210210qpqpqP一旦到达0状态：P向右移一格q停在原处021qpqpqpq7.带有两个反射壁的随机游动0，a反射态aI,2,1,0pqpqqqpqpqqaaaaaa00000000000000000000000001221012210P0状态：P向右移一格q停在原处a状态：P向右移一格q停在原处021qpqpqa-1a-2qppqp…apqqp6.3切普曼-柯尔莫哥洛夫方程（C-K方程）)()()(mnpnpnprkjIkmikrmij一、马氏链的C-K方程,2,1,00,InXn的转移概率步的转移到达位置，经过时刻处jXrminrmnnn+mn+m+rij证明：iXjXPnpnrmnrmij)(iXPiXjXPnnrmn,iXPjXkXiXPnIkrmnmnn,,IknmnnmnnrmnmnniXPkXiXPkXiXPjXkXiXP,,,,6.3切普曼-柯尔莫哥洛夫方程（C-K方程）一、马氏链的C-K方程iXjXPnpnrmnrmij)(IknmnnmnnrmnmnniXPkXiXPkXiXPjXkXiXP,,,,IknmnnrmniXkXPiXjXPIkrkjmikmnPnP齐次的C-K方程IkrkjmikrmijPPp当2rmn时，有22)1()1()1()2()(][PPPPP同理可推出，当kn时，有kkkk)(][)1()1()1()(PPPPP即任意k步转移概率矩阵可由一步转移概率矩阵自乘k次来得到。C-K矩阵形式rmrmPPP例1在某数字通信系统中多级传输0、1两种数字信号。由于系统中存在干扰，在任一级输入0、1数字信号后，其输出不产生错误的概率为p，产生错误的概率为q=1-p，求两级传输时的概率转移矩阵。解：系统每一级的输入状态和输出状态构成一个两状态的马氏链，其一步转移概率矩阵为pqqppppp11100100P于是，两级传输时的概率转移矩阵等效于两步转移概率矩阵为22222)2(22qppqpqqppqqppqqpPP二、初始分布与绝对分布定义1设},2,1,0),({nnX为一马氏链，其状态空间},2,1,0{E或为有限子集。令EiiXPpi},)0({)0(，且对任意的Ei（1）0)0(ip（2）1)0(Eiip}),0({Eipi则称为该马氏链的初始分布，也称初始概率。初始概率是马氏链在初始时间时处于状态0ni的概率。1n当时，马氏链处于状态i的概率称为绝对概率或绝对分布。均有定义2设},2,1,0),({nnX为一马氏链，其状态空间},2,1,0{E或为有限子集。令EiinXPnpi},)({)(，且对任意的Ei（1）0)(npi（2）1)(npEii}),({Einpi则称为该马氏链的绝对分布，也称绝对概率。均有定理3马氏链的绝对概率由初始分布和相应的转移概率唯一确定。},2,1,0),({nnX为一马氏链，E为状态集，则对任意1,nEj时马氏链处于状态j的概率为)})0()()1({(})1({)1(iXjXPjXPpEijEiEiiXjXPiXjXP})0(,)1({)})0(,)1(({)1()0(})0(|)1({})0({ijEiEiippiXjXPiXP即:1n时,绝对概率)1(jp由初始概率}),0({Eipi及一步转移概率}),1({Eipij唯一确定。2n时，绝对概率由下式确定：)})0()()({(})({)(iXjnXPjnXPnpEijEiEiiXjnXPiXjnXP})0(,)({)})0(,)(({)()0(})0(|)({})0({nppiXjnXPiXPijEiEii即:绝对概率由初始概率及n步转移概率唯一确定。)(npj}),0({Eipi}),({Einpij利用C-K方程，则n步转移矩阵可由一步转移矩阵唯一确定。证：设当推论：马氏链的绝对概率由初始分布及一步转移概率唯一确定。由马氏链的转移概率和初始分布，不仅可以完全确定其绝对分布，也可以完全确定其有限维分布。即},,,{1010niniiaXaXaXP11001100{|}{|}{}nnniniiiiPXaXaPXaXaPXanniiiiippp1100,n}|,,{}{010010iiiniaXaXaXPaXPn三、举例6.04.03.07.01010111010P1.天气预报有雨0无雨1今日下雨明日下雨α今日无雨明日下雨β设今日有雨P0=0.4，求第四日有雨的概率？4P解：22P4P46.04.03.07.04332.05668.04251.05749.004XP000040XXXPP101040XXXPP5668.0*6.05749.0*4.04704.02.甲乙两人比赛，甲胜p，和r,甲负q，p+r+q=1，胜加1，和加0，负减1，当其中一人得2分后结束比赛。（1）写出状态空间（2）一步转移概率矩阵（3）甲获1分时，再比赛2局结束比赛的概率。解：10000000000000012101221012prqprqprqP（1）有两个吸收壁的随机游动2,1,0,1,2I1210122101222pprPP（2）（2）122nnXXP3.已知一独立的随机变量序列另外一个序列求证：具有马尔可夫性。,,,,21nXXXnnnXxPxPnniinXY10iEX1,nYn111111,,nnnnnnnnyYyYPyYyYyYP111,,111,,nnYYnnYYYyyPyyyPnnnn证：左边1112211,,nnnYYXYYXYX1JnXXnYYxxPJyyPnn,,,,1,,1,,11112211nnnyyPyyPyP左边111,,1,,,,,,111nnnnYYnYYyyPyyPyyPnn3.已知一独立的随机变量序列另外一个序列求证：具有马尔可夫性。,,,,21nXXXnnnXxPxPnniinXY10iEX1,nYn111111,,