随机过程-7马尔科夫链的概念和转移概率1课件.ppt

1、马尔科夫链的概念和转移概率马尔科夫链的概念和转移概率 例例1 某地只有甲、乙、丙三家公司的产品在某地只有甲、乙、丙三家公司的产品在该地销售，据统计一个月后，使用甲产品该地销售，据统计一个月后，使用甲产品的用户有的用户有10%转向乙，转向乙，20%转向丙；使用转向丙；使用乙产品的用户有乙产品的用户有10%转向甲，转向甲，20%转向丙；转向丙；使用丙产品的用户有使用丙产品的用户有8%转向甲，转向甲，4%转向转向乙。已知甲、乙、丙现在的市场占有率是乙。已知甲、乙、丙现在的市场占有率是30%,20%,50%,问四个月后的各自市场占有问四个月后的各自市场占有率是多少？经过足够长的时间，市占率是率是多少？

2、经过足够长的时间，市占率是否会稳定？稳定到多少？否会稳定？稳定到多少？例例2(蜘蛛和苍蝇蜘蛛和苍蝇)一只苍蝇在一条直线上移动，每一只苍蝇在一条直线上移动，每次移动一个单位长度。每单位时间，它以次移动一个单位长度。每单位时间，它以0.3的概的概率向左移动一个单位，以率向左移动一个单位，以0.3的概率向右移动一个的概率向右移动一个单位，且以单位，且以0.4的概率停留在原地，并且它们独立的概率停留在原地，并且它们独立于过去的移动。两只蜘蛛等在位置于过去的移动。两只蜘蛛等在位置1和位置和位置m：如：如果苍蝇达到这个位置，它将被蜘蛛捕捉，于是过果苍蝇达到这个位置，它将被蜘蛛捕捉，于是过程结束。问：苍蝇平

3、均能活多长时间？被某个蜘程结束。问：苍蝇平均能活多长时间？被某个蜘蛛吃掉的概率是多少？蛛吃掉的概率是多少？引例引例3(赌徒破产问题赌徒破产问题)一个赌徒每局以概率一个赌徒每局以概率p赢一元，同时以概率赢一元，同时以概率1-p输掉一元。假设输掉一元。假设不同的赌局之间是相互独立的。赌徒会一不同的赌局之间是相互独立的。赌徒会一直赌博直到资金到达某个目标总数直赌博直到资金到达某个目标总数m时，时，或者输掉全部的钱。或者输掉全部的钱。请问最终资金到达目标请问最终资金到达目标m或者输掉他全部或者输掉他全部资金的概率是多少？资金的概率是多少？到达目标到达目标m或者输掉他全部资金时，平均或者输掉他全部资金时

4、，平均可以玩多少局？可以玩多少局？4.1 马尔可夫链与转移概率马尔可夫链与转移概率 定义定义 设设 X(t)，t T 为随机过程，若对任意为随机过程，若对任意正整数正整数n及及t1 t20，且条件分布且条件分布PX(tn)xn|X(t1)=x1,X(tn-1)=xn-1=PX(tn)xn|X(tn-1)=xn-1，则称则称X(t)，t T 为为马尔可夫过程马尔可夫过程。若若t1,t2,tn-2表示过去，表示过去，tn-1表示现在，表示现在，tn表表示示将来，马尔可夫过程表明：在已知现在状态将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与过去状态无关。的条件下，将来所处的状态与过

5、去状态无关。4.1 马尔可夫链与转移概率 常见马尔可夫过程通常有三类：常见马尔可夫过程通常有三类：(1)(1)时间、状态都是离散的，称为时间、状态都是离散的，称为马尔可夫链马尔可夫链(2)时间连续时间连续、状态离散的，称为连续时间状态离散的，称为连续时间马尔马尔可夫链可夫链(3)时间、状态都是连续的，称为时间、状态都是连续的，称为马尔可夫过程马尔可夫过程（时间离散时间离散、状态连续的状态连续的马尔可夫过程，通常马尔可夫过程，通常用泛函中二元函数的范数进行研究）用泛函中二元函数的范数进行研究）随机过程随机过程Xn，n T，参数参数T=0,1,2,状态空间状态空间I=i0,i1,i2,定义定义 若

6、随机过程若随机过程Xn，n T，对任意，对任意n T和和i0,i1,in+1 I，条件概率条件概率PXn+1=in+1|X0=i0,X1=i1,Xn=in =PXn+1=in+1|Xn=in，则称则称Xn，n T 为为马尔可夫链马尔可夫链，简称，简称马氏链马氏链。4.1 马尔可夫链与转移概率4.1 马尔可夫链与转移概率马尔可夫链与转移概率 马尔可夫链的马尔可夫链的性质性质 PX0=i0,X1=i1,Xn=in=PXn=in|X0=i0,X1=i1,Xn-1=in-1 PX0=i0,X1=i1,Xn-1=in-1=PXn=in|Xn-1=in-1 PXn-1=in-1|X0=i0,X1=i1,X

7、n-2=in-2 PX0=i0,X1=i1,Xn-2=in-2=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-24.1 马尔可夫链与转移概率马尔可夫链与转移概率=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2 PX1=i1|X0=i0PX0=i0 马尔可夫链的统计特性完全由条件概率马尔可夫链的统计特性完全由条件概率PXn+1=in+1|Xn=in确定。确定。4.1 马尔可夫链与转移概率 定义定义 称条件概率称条件概率pij(n)=PXn+1=j|Xn=i 为为马尔可夫链马尔可夫链Xn，n T 在时刻

8、在时刻n的的一步一步转移概率转移概率，简称简称转移概率转移概率，其中其中i,j I。定义定义 若对任意的若对任意的i,j I，马尔可夫链马尔可夫链Xn,n T 的转移概率的转移概率pij(n)与与n无关，则无关，则称称马尔可夫链是齐次的马尔可夫链是齐次的，并记，并记pij(n)为为pij。可以用状态转移图和转移概率矩阵表示可以用状态转移图和转移概率矩阵表示齐次马尔科夫链：齐次马尔科夫链：例例1 某地只有甲、乙、丙三家公司的产品在某地只有甲、乙、丙三家公司的产品在该地销售，据统计一个月后，使用甲产品该地销售，据统计一个月后，使用甲产品的用户有的用户有10%转向乙，转向乙，20%转向丙；使用转向丙

9、；使用乙产品的用户有乙产品的用户有10%转向甲，转向甲，20%转向丙；转向丙；使用丙产品的用户有使用丙产品的用户有8%转向甲，转向甲，4%转向转向乙。已知甲、乙、丙现在的市场占有率是乙。已知甲、乙、丙现在的市场占有率是30%,20%,50%,问四个月后的各自市场占有问四个月后的各自市场占有率是多少？经过足够长的时间，市占率是率是多少？经过足够长的时间，市占率是否会稳定？稳定到多少？否会稳定？稳定到多少？例例1：甲、乙、丙三个状态用：甲、乙、丙三个状态用1,2,3表示表示状态转移图：状态转移图：231转移矩阵：转移矩阵：0.10.20.70.10.20.70.080.040.881111P7.0

10、212P1.0313P2.0221P22P23P331P32P33P1.02.07.008.004.088.0 矩阵每一行的和都等于矩阵每一行的和都等于1求一个用户从甲求一个用户从甲甲甲乙乙丙的概率丙的概率如果初始状态在如果初始状态在2，即，即 P(X0=2)=1,则则22234的概率为：的概率为：P(X0=2,X1=2,X2=2,X3=3,X4=4)=P(X0=2)P(X1=2|X0=2)P(X2=2|X1=2,X0=2)P(X3=3|X2=2,X1=2,X0=2)P(X4=4|X3=3,X2=2,X1=2,X0=2)=P(X0=2)P22 P22 P23 P34=223.04.0若若 P(

11、X0=2)=P0,则则22234的概率为：的概率为：2203.04.0P转移矩阵：转移矩阵：10000.3 0.40.3000.30.4 0.30001矩阵每一行的和都等于矩阵每一行的和都等于1例例2(蜘蛛和苍蝇蜘蛛和苍蝇)一般情况，我们令一般情况，我们令1，2，.,m表示苍蝇对应表示苍蝇对应的位置，于是非零转移概率为：的位置，于是非零转移概率为：P11=1，Pmm=1 转移概率矩阵如下：转移概率矩阵如下：1,.,24.011,3.0 miijijijpij其中其中，若，若或者或者若若 1000003.04.00000003.04.03.000003.04.03.0000001P 引例引例3(

12、赌徒破产问题赌徒破产问题)44434241403433323130242322212014131211100403020100ppppppppppppppppppppppppp444342414034333231302423222120141312111000001pppppppppppppppppppp444342414034333231302423222120000100001ppppppppppppppppp 444342414034333231300010000100001pppppppppppppp 444342414001000010000100001ppppppppppp 100

13、0001000010000100001pppppp 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 转移概率转移概率性质性质(1)(2)P称为随机矩阵称为随机矩阵 性质性质(2)是说每次试验必定会出现某个转移。是说每次试验必定会出现某个转移。mnmmnnpppppppppP212222111211Ijipij,0IipIjij,1 齐次马尔可夫链具有平稳转移概率，齐次马尔可夫链具有平稳转移概率，状态空间状态空间I=1,2,3,，一步一步转移概率转移概率矩阵矩阵为为：4.1 马尔可夫链与转移概率马尔可夫链与转移概率 具有吸收壁和反射壁的随机游动具有吸收壁和反射壁的随机游动状态空间状态空间1,2

14、,3,4，1为吸收壁，为吸收壁，4为反射壁为反射壁 状态转移图状态转移图 状态转移矩阵状态转移矩阵0100000001313131313131P123431313131313111n步转移概率步转移概率n步转移概率矩阵步转移概率矩阵4.1 马尔可夫链与转移概率马尔可夫链与转移概率 定义定义 称条件概率称条件概率 =PXm+n=j|Xm=i 为为马尔可夫链马尔可夫链Xn，n T 的的n步转移概步转移概率率(i,j I,m 0,n 1)。)(nijp jijipnppnijijij,1,00,1)0()1(时时，规规定定当当时时当当 333231232221131211ppppppppp求状态求状

15、态1经过两次经过两次转移仍然处于状态转移仍然处于状态1的概率：的概率：12311311321121111)2(11ppppppp23111p12p13p21p22p23p31p32p33p11p12p13p11p21p31p)2(12p321322121211pppppp 331323121311)2(13ppppppp 312321221121)2(21ppppppp 322322221221)2(22ppppppp 332323221321)2(23ppppppp 313321321131)2(31ppppppp 323322321231)2(32ppppppp 333323321331)

16、2(33ppppppp 212p22p32p 333231232221131211ppppppppp求状态求状态i经过两次转经过两次转移仍然处于状态移仍然处于状态j的的概率：概率：i231jjijijiijppppppp332211)2(23111p12p13p21p22p23p31p32p33p1ip2ip3ipjp1jp2jp3一般情况：一般情况：31kkjikpp如果有如果有m个状态个状态1,2,.,m,则则 mkkjikijppp1)2(333231232221131211ppppppppp311321121111)2(11ppppppp 1231111p12p13p11p21p23p

17、321322121211)2(12ppppppp 331323121311)2(13ppppppp 312321221121)2(21ppppppp 322322221221)2(22ppppppp 332323221321)2(23ppppppp )2()2()2()2()2()2()2()2()2(333231232221131211ppppppppp131211ppp312111ppp322212ppp332313ppp232221ppp333231ppp2)2(PP 88.004.008.02.07.01.02.01.07.0P例例1：甲、乙、丙三个状态用：甲、乙、丙三个状态用1,2,

18、3表示表示 0.7984 0.0712 0.13040.3360 0.5080 0.15600.3360 0.1480 0.51602P两步转移概率矩阵：两步转移概率矩阵：333231232221131211ppppppppp求状态求状态i经过三次转经过三次转移处于状态移处于状态j的概率：的概率：jjjijpppppppiii3)2(2)2(1)2()3(321 23111p12p13p21p22p23p31p32p33pi231j)2(1ip)2(2ip)2(3ipjp1jp2jp2 31kkjikppjjjijpppppppiii3)2(2)2(1)2()3(321 )3(11p31)2(

19、21)2(11)2()3(11131211ppppppp i231j)2(1ip)2(2ip)2(3ipjp1jp2jp2 )2(13)2(12)2(11ppp312111ppp)3(12p32)2(22)2(12)2()3(12131211ppppppp 322212ppp)3(13p33)2(23)2(13)2()3(13131211ppppppp 332313ppp)3(21p31)2(21)2(11)2()3(21232221ppppppp )2(23)2(22)2(21ppp)3(22p32)2(22)2(12)2()3(22232221ppppppp 32)2(23)2(13)2(

20、)3(23232221ppppppp )3(23p)3(31p31)2(21)2(11)2()3(31333231ppppppp )2(33)2(32)2(31ppp)3(32p)3(33pPPP)2()3(PP2 3P PPPnn)1()(nP 88.004.008.02.07.01.02.01.07.0P例例1：甲、乙、丙三个状态用：甲、乙、丙三个状态用1,2,3表示表示 0.7984 0.0712 0.13040.3360 0.5080 0.15600.3360 0.1480 0.51602P两步转移概率矩阵：两步转移概率矩阵：三步转移概率矩阵：三步转移概率矩阵：0.7429 0.094

21、8 0.16230.4285 0.3846 0.18690.4285 0.1686 0.40293P10步转移概率矩阵：步转移概率矩阵：0.6329 0.1511 0.2160 0.6118 0.1684 0.2198 0.6118 0.1624 0.2258 10P查普曼查普曼科尔莫戈洛夫方程，即科尔莫戈洛夫方程，即C-K方程：方程：定理定理4.1 设设Xn，n T 为为马尔可夫链，则对马尔可夫链，则对任意整数任意整数n 0,0 ln和和i,j I，n步转移概率步转移概率 具有性质具有性质(1)(2)(3)P(n)=PP(n-1)(4)P(n)=PnIklnkjliknijppp)()()(

22、IkIkjkkkiknijnnpppp111211)(4.1 马尔可夫链与转移概率马尔可夫链与转移概率证证(1)IklnkjlikIkliklnkjIkmlmlmnmIkmlmmlmmnmlmmmnmmmnmnijppppiXkXPkXjXPiXPkXiXPkXiXPjXkXiXPiXPjXiXPiXjXPp)()()()()(|,|IklnkjlikIkliklnkjIkmlmlmnmIkmlmmlmmnmlmmmnmmmnmnijppmplmpiXkXPkXjXPiXPkXiXPkXiXPjXkXiXPiXPjXiXPiXjXPp)()()()()()()(|,|IklnkjlikIkli

23、klnkjIkmlmlmmnmIkmlmmlmmnmlmmmnmmmnmnijppppiXkXPkXiXjXPiXPkXiXPkXiXPjXkXiXPiXPjXiXPiXjXPp)()()()()(|,|,|IkmnmlmmiXPjXkXiXP,4.1 马尔可夫链与转移概率马尔可夫链与转移概率(2)在在(1)中令中令l=1,k=k1,得得由此可递推出公式由此可递推出公式(3)矩阵乘法矩阵乘法(4)由由(3)推出推出说明：说明：(1)此为此为C-K方程方程(切普曼切普曼-柯尔莫哥洛夫柯尔莫哥洛夫)(2)n步转移概率由一步转移概率确定，步转移概率由一步转移概率确定，n步转移概率矩阵由一步转移概率矩

24、阵确步转移概率矩阵由一步转移概率矩阵确定定(n次幂次幂)Iknjkiknijppp)1()1()(11例例2(蜘蛛和苍蝇蜘蛛和苍蝇)1 0 0 0 0.3 0.4 0.3 0 0 0.3 0.4 0.30 0 0 1 P求在位置求在位置2的苍蝇经过四步被位置的苍蝇经过四步被位置4的蜘蛛吃掉的概率的蜘蛛吃掉的概率 1.0000 0 0 0 0.5466 0.1201 0.1200 0.2133 0.2133 0.1200 0.1201 0.5466 0 0 0 1.0000 4P0.2133)4(24 P 1.0000 0 0 0 0.6667 0.0000 0.0000 0.3333 0.3333 0.0000 0.0000 0.6667 0 0 0 1.0000 30P即当即当n足够大时，足够大时，出现什么现象？出现什么现象？另外，另外，例：已知马氏链转移图如下，求从状态例：已知马氏链转移图如下，求从状态1出发出发再返回再返回1的的n步转移概率，步转移概率，n=1,2,8212112311 01021021010P 21021010210212PPP 010210210103 是偶数是偶数，是奇数是奇数nnPn21,0)(11