第四章 马尔可夫链

第四章马尔可夫链4.1马尔可夫链与转移概率定义设{X(t)，tT}为随机过程，若对任意正整数n及t1t2tn，P{X(t1)=x1,,X(tn-1)=xn-1}0，且条件分布P{X(tn)xn|X(t1)=x1,,X(tn-1)=xn-1}=P{X(tn)xn|X(tn-1)=xn-1}，则称{X(t)，tT}为马尔可夫过程。☆若t1,t2,,tn-2表示过去，tn-1表示现在，tn表示将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与过去状态无关。4.1马尔可夫链与转移概率•常见马尔可夫过程通常有三类：(1)时间、状态都是离散的，称为马尔可夫链(2)时间连续、状态离散的，称为连续时间马尔可夫链(3)时间、状态都是连续的，称为马尔可夫过程（时间离散、状态连续的马尔可夫过程，通常用泛函中二元函数的范数进行研究）随机过程{Xn，nT}，参数T={0,1,2,},状态空间I={i0,i1,i2,}定义若随机过程{Xn，nT}，对任意nT和i0,i1,,in+1I，条件概率P{Xn+1=in+1|X0=i0,X1=i1,,Xn=in}=P{Xn+1=in+1|Xn=in}，则称{Xn，nT}为马尔可夫链，简称马氏链。4.1马尔可夫链与转移概率4.1马尔可夫链与转移概率•马尔可夫链的性质P{X0=i0,X1=i1,,Xn=in}=P{Xn=in|X0=i0,X1=i1,,Xn-1=in-1}P{X0=i0,X1=i1,,Xn-1=in-1}=P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|X0=i0,X1=i1,,Xn-2=in-2}P{X0=i0,X1=i1,,Xn-2=in-2}=P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|Xn-2=in-2}P{X0=i0,X1=i1,,Xn-2=in-2}4.1马尔可夫链与转移概率==P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|Xn-2=in-2}P{X1=i1|X0=i0}P{X0=i0}马尔可夫链的统计特性完全由条件概率P{Xn+1=in+1|Xn=in}确定。4.1马尔可夫链与转移概率•定义称条件概率pij(n)=P{Xn+1=j|Xn=i}为马尔可夫链{Xn，nT}在时刻n的一步转移概率，简称转移概率，其中i,jI。•定义若对任意的i,jI，马尔可夫链{Xn,nT}的转移概率pij(n)与n无关，则称马尔可夫链是齐次的，并记pij(n)为pij。•齐次马尔可夫链具有平稳转移概率，状态空间I={1,2,3,}，一步转移概率为4.1马尔可夫链与转移概率•转移概率性质(1)(2)P称为随机矩阵mnmmnnpppppppppP212222111211Ijipij,,0IipIjij,14.1马尔可夫链与转移概率例4.1赌博问题。甲乙二人进行一系列赌博，甲有a元，乙的赌本无限，每赌一局输者给赢者1元，没有和局，如果甲输光，再输则赌本为负。设在每一局中，甲赢的概率为p，输的概率为q=1-p。设Xn表示第n次赌博结束后甲的赌本，则Xn，n≥1是马尔科夫链，求Xn的转移矩阵4.1马尔可夫链与转移概率例4.1无限制随机游动qp-101i-1ii+1一步转移概率:2||,0,011,1,jipppqpppijiiiiii4.1马尔可夫链与转移概率n步转移概率:i经过k步进入j,向右移了x步,向左移了y步则为奇数，为偶数)(0)(,2)(2)()(ijkijkqpCpijkyijkxijyxkyxyxxkkij4.1马尔可夫链与转移概率例4.4具有吸收壁和反射壁的随机游动状态空间{1,2,3,4}，1为吸收壁，4为反射壁状态转移图状态转移矩阵0100000001313131313131P1234313131313131114.1马尔可夫链与转移概率•定义称条件概率=P{Xm+n=j|Xm=i}为马尔可夫链{Xn，nT}的n步转移概率(i,jI,m0,n1)。•n步转移矩阵其中P(n)也为随机矩阵)(nijp)()(nijnpPIjippIjnijnij,,1,0)()(jijipnPPppnijijij,1,00,,1)0()1()1(时，规定当时当4.1马尔可夫链与转移概率•定理4.1设{Xn，nT}为马尔可夫链，则对任意整数n0,0ln和i,jI，n步转移概率具有性质(1)(2)(3)P(n)=PP(n-1)(4)P(n)=Pn)(nijpIklnkjliknijppp)()()(IkIkjkkkiknijnnpppp111211)(4.1马尔可夫链与转移概率证(1)IklnkjlikIkliklnkjIkmlmlmnmIkmlmmlmmnmlmmmnmmmnmnijppppiXkXPkXjXPiXPkXiXPkXiXPjXkXiXPiXPjXiXPiXjXPp)()()()()(||,,,,,|IklnkjlikIkliklnkjIkmlmlmnmIkmlmmlmmnmlmmmnmmmnmnijppmplmpiXkXPkXjXPiXPkXiXPkXiXPjXkXiXPiXPjXiXPiXjXPp)()()()()()()(||,,,,,|IklnkjlikIkliklnkjIkmlmlmmnmIkmlmmlmmnmlmmmnmmmnmnijppppiXkXPkXiXjXPiXPkXiXPkXiXPjXkXiXPiXPjXiXPiXjXPp)()()()()(|,|,,,,,|IkmnmlmmiXPjXkXiXP,,4.1马尔可夫链与转移概率(2)在(1)中令l=1,k=k1,得由此可递推出公式(3)矩阵乘法(4)由(3)推出说明：(1)此为C-K方程(切普曼-柯尔莫哥洛夫)(2)n步转移概率由一步转移概率确定，n步转移概率矩阵由一步转移概率矩阵确定(n次幂)Iknjkiknijppp)1()1()(114.1马尔可夫链与转移概率•初始概率•绝对概率•初始分布•绝对分布•初始概率向量•绝对概率向量}{0jXPpj}{)(jXPnpnjIjpj,Ijnpj,)(),,()0(21pppT)),(),(()(21npnpnpT定义4.1马尔可夫链与转移概率•设{Xn，nT}为马尔可夫链，则对任意整数jI和n1，绝对概率pj(n)具有性质(1)(2)(3)PT(n)=PT(0)P(n)(4)PT(n)=PT(n-1)PIinijijppnp)()(Iiijijpnpnp)1()(定理4.2nnIiniippppppn2121111·1)(p例如，设马氏链的状态空间I={1,2}，那么时刻n的绝对概率分布应满足PT(n)=(p1(n),p2(n))nnnnppppppnpn222112112121)()(p），（），（PT(n)=PT(0)P(n)nnIiniippppppn22212122)(p4.1马尔可夫链与转移概率证(1)IinijiIinIinnjppiXPiXjXPjXiXPjXPnp)(000}{}|{},{}{)(4.1马尔可夫链与转移概率(2)(3)(4)为(1)(2)的矩阵表示。IiijiIinnnIinnnjpnpiXPiXjXPjXiXPjXPnp)1(}{}|{},{}{)(1114.1马尔可夫链与转移概率•定理4.3设{Xn，nT}为马尔可夫链，则对任意整数i1,i2,,inI和n1，有性质证IiiiiiiiinnnnppppiXiXP1211},,{11IiiiiiiiinnnnIiIinnnnnnppppiXiXPiXiXPiXiXPiXPiXiXiXPiXiXP1211}|{}|{}|{}{},,,{},,{1111220110110114.1马尔可夫链与转移概率例4.2赌徒输光问题甲有赌资a元，乙有赌资b元，赌一局输者给赢者1元，无和局。甲赢的概率为p，乙赢的概率为q=1-p，求甲输光的概率。解状态空间I={0,1,2,,c}，c=a+bqpa-1aa+10a+b4.1马尔可夫链与转移概率设ui表示甲从状态i出发转移到状态0的概率，求ua显然u0=1，uc=0(u0表示已知甲输光情形下甲输光的概率，uc表示已知乙输光情形下甲输光的概率)ui=pui+1+qui-1(i=1,2,,c-1)（甲在状态i下输光：甲赢一局后输光或甲输一局后输光）4.1马尔可夫链与转移概率1,,2,1)()()()(111111ciuupquuuuquupqupuuqpiiiiiiiiiiiˆ21,1(1)012111uuuuuuuuqppqiiiiii即4.1马尔可夫链与转移概率baaubabcauciiuccuiiuuiuuiuuuuuuuubaiciiiiiiii同理可得即,111101)1(1)1()1()1()()()()(01010121114.1马尔可夫链与转移概率rrruuuruuruuuuruurpqqppqckckiiiickikciiii1)1()()()(,,1(2)10111111设即4.1马尔可夫链与转移概率ccbcbbccacaacckckkcccrrrrrruurrrrrruurrrrrruurrurrruuuk11)1(11)1(11)1(1111)1(0,1111010从而则令4.1马尔可夫链与转移概率例4.3天气预报问题RR表示连续两天有雨，记为状态0NR表示第1天无雨第2天有雨，记为状态1RN表示第1天有雨第2天无雨，记为状态2NN表示连续两天无雨，记为状态3p00=P{R今R明|R昨R今}=P{R明|R昨R今}=0.7p01=P{N今R明|R昨R今}=0p02=P{R今N明|R昨R今}=P{N明|R昨R今}=0.3p03=P{N今N明|R昨R今}=04.1马尔可夫链与转移概率类似地得到其他转移概率，于是转移概率矩阵为若星期一、星期二均下雨，求星期四下雨的概率8.002.006.004.0005.005.003.007.033323130232221201312111003020100ppppppppppppppppP4.1马尔可夫链与转移概率星期四下雨的情形如右，星期四下雨的概率2步转移概率矩阵为64.010.016.010.048.020.012.020.030.015.020.035.018.021.012.049.02)2(PP一二三四RRRR00RRNR0161.012.049.0)2(01)2(00ppp4.2马尔可夫链的状态分类•{X