马尔可夫链的概念及转移概率.doc

第四章
4.1 马尔可夫链的的概念及转移概率
一、知识回顾
二、马尔可夫链的的定义
三、转移概率
四、马尔可夫链的一些简单例子
五、总结

一、知识回顾
1. 条件概率
定义：设A，B为两个事件，且P(A)>0，称
PBA=P(AB)P(A)
为事件A发生条件下B事件发生的条件概率。
将条件概率公式移项即得到所谓的乘法公式：
PAB=P(A)P(B|A)
2.全概率公式
设试验E的样本空间为S，A为E的事件，若B1,B2，⋯，Bn为S的一个完备事件组，既满足条件：
1). B1,B2，⋯，Bn两两互不相容，即BiBj=∅，i≠j,i,j=1,2,⋯,n
2). B1∪B2∪⋯∪Bn=S，且有PBi>0,i=1,2,⋯,n，则
PA=i=1nPBiPA|Bi
此式称为全概率公式。
3.矩阵乘法
矩阵乘法的定义
A=a11a12a13a21a22a23，B=b11b12b21b22b31b32C=c11c12c21c22
如果c11=a11×b11+a12×b21+a13×b31
c12=a11×b12+a12×b22+a13×b32
c21=a21×b11+a22×b21+a23×b31
c22=a21×b12+a22×b22+a23×b32
那么矩阵C叫做矩阵A和B的乘积，记作C=AB
4.马尔可夫过程的分类
马尔可夫过程按其状态和时间参数是连续的或离散的，可分为三类：
（1） 时间、状态都是离散的马尔科夫过程，称为马尔可夫链；
（2） 时间连续、状态离散的马尔科夫过程称为连续时间的马尔可夫链的；
（3） 时间、状态都连续的马尔科夫过程。
二、马尔科夫链的定义
定义4.1 设有随机过程{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} (4.1.1)
则称{Xn,n∈T}为马尔科夫链，简称马氏链。
式(4.1.1)即为马氏链，他表明在状态X(0)=i0,X(1)=i1,…X(n)=in已知的条件下，X(n+1)=j的条件概率与X(0)=i0,X(1)=i1,…X(n-1)=in-1无关，而仅与X(n)所处的状态in有关。
式(4.1.1)是马尔科夫链的马氏性（或无后效性）的数学表达式。由定义知
P{X0=i0,X1=i1,…,Xn=in}
=PXn=inX0=i0,X1=i1,…,Xn-1=in-1
∙P{X0=i0,X1=i1,…,Xn-1=in-1}
=PXn=inXn-1=in-1 PX0=i0,X1=i1,…,Xn-1=in-1=…
=PX1=i1X0=i0P{X0=i0}
可见，马尔科夫链的统计特性完全由条件概率
P{Xn+1=in+1|Xn=in}
所决定。如何确定这个条件概率，是马尔科夫链理论和应用中的重要问题之一。

现举一例说明上述概念：
例4.1.1 箱中装有c个白球和d个黑球，每次从箱子中任取一球，抽出的球要到从箱子中再抽出一球后才放回箱中，每抽出一球作为一次取样试验。
现引进随机变量序列为{Xn,n=1,2,⋯},每次取样试验的所有可能结果只有两个，即白球或黑球。若以数a1代表白球，以数a2代表黑球则有
Xn=a1，第n次抽球结果为白球a2，第n次抽球结果为黑球
由上所述的抽球规则可知，任意第n次抽到黑球或白球的概率只与第n-1次抽得球的结果有关，而与第n-2次，第n-3次，⋯，第1次，抽的球的结果无关，
由此可知上述随机变量序列{Xn,n=1,2,⋯},为马氏链。

三、转移概率
定义4.2 称条件概率
pijn=P{Xn+1=j|Xn=i}
为马尔科夫链{Xn,n∈T}在时刻N的一步转移概率，其中i,j∈T，简称为转移概率。
条件概率pijn：随机游动的质点在时刻n处于状态i的条件下，下一步转移到状态j的你改率。
一般地，转移概率pijn不仅与状态i，j有关，而且与时刻n有关。当pijn不依赖与时刻n时，表示马尔科夫链具有平稳转移概率。

定义4.3 若对任意的i,j∈T，马尔科夫链{Xn,n∈T}的转移概率pijn与n无关则称马尔科夫链是齐次的，并记pijn为pij。
下面我们只讨论齐次马尔科夫链通常将“齐次”两个字省略。
设P表示一步转移概率pij所组成的矩阵，且状态空间I={1,2,…}，则
P=p11p12…p21p22………… p1n…p2n………
称为系统状态的一步转移概率矩阵。它具有性质：
(1) pij≥0，i，j∈I；
(2) j∈Tpij=1，i∈I.
(2)式中对j求和是对状态空间I的所有可能状态进行的，此性质说明一步转移概率矩阵中任一行元素之和为1.通常称满足上述（1）、（2）性质的矩阵为随机矩阵。

定义4.4 称条件概率
pij(n)=PXm+n=jXm=i, i,j∈I, m≥0, n≥1
为马尔科夫链{Xn,n∈T}的n步转移概率，并称
P(n)=(pij(n))
为马尔科夫链的n步转移矩阵，其中pijn≥0，j∈Tpijn=1，即P(n)也是随机矩阵。
当n=1是，pij(1)=pij，此时一步转移矩阵P(1)=P. 此外我们规定
pij0=0，i≠j，1，i=j.

定理4.1 设{Xn,n∈T}为马尔科夫链，则对任意整数n≥0，0≤l<n和i,j∈T，n步转移概率pij(n)具有下列性质：
(1) pij(n)=k∈Ipiklpkjn-l;
(2) pij(n)=k1∈I…kn-1∈Ipik1pk1k2…pkn-1j;
(3) P(n)=PP(n-1);
(4) P(n)=Pn.
证 (1)利用全概率公式及马尔科夫性，有
pij(n)=P{Xm+n=j|Xm=i}=P{Xm=i,Xm+n=j}P{Xm=i}
=k∈IP{Xm=i,Xm+l=k,Xm+n=j}P{Xm=i,Xm+l=k}∙P{Xm+l=k|Xm=i}
=k∈Ipkjn-lpikl(m)=k∈Ipiklpkjn-l
(2)在(1)中令l=1,k=k1得
pij(n)=k∈Ipik1pk1jn-l;
这是一个递推公式，故可递推得到
pij(n)=k1∈I…kn-1∈Ipik1pk1k2…pkn-1j;
(3)在(1)中令l=1,利用矩阵乘法可证。
(4)由(3)，利用归纳法可证。
定理4.1中(1)式称为切普曼——柯尔莫哥洛夫方程，简称C-K方程。它在马尔科夫链的转移概率的计算中起着重要的作用。(2)式说明n步转移概率完全由一步转移概率决定。(4)式说明齐次马尔科夫链的n步转移概率矩阵是一步转移概率矩阵的n次乘方。

定义4.5 设{Xn,n∈T}为马尔科夫链，称
pj=P{X0=j}和pjn=pXn=j，(j∈I)
为{Xn,n∈T}的初始概率和绝对概率，并分别成{pj,j∈I}和{pj(n),j∈I}为{Xn,n∈T}的初始分布和绝对分布，简记为{pj}和{pjn}。称概率向量
PTn=(p1n，p2n，…)
为n时刻的绝对概率向量，而称
PT0=(p1，p2，…)
为初始概率
定理4.2 设{Xn,n∈T}为马尔科夫链，则对任意j∈I和n≥1，绝对概率pj(n)具有下列性质：
（1）pjn=i∈Ipipij(n)；
（2）pjn=i∈Ipi(n-1)pij；
（3）PTn=PT(0)P(n)；
（4）PTn=PT(n-1)P.
证 (1) pjn=PXn=j=i∈IPX0=i, Xn=j
=i∈IPXn=j|X0=iPX0=i=i∈Ipipij(n)
(2)pjn=PXn=j=i∈IPXn=j, Xn-1=i
=i∈IPXn=j| Xn-1=iPXn-1=i
=i∈Ipi(n-1)pij
(3)与(4)中式是(1)与(2)中式的矩阵乘积形式，显然成立。证毕。

定理4.3 设{Xn,n∈T}为马尔科夫链，则对任意i1,…in∈I和n≥1，有
PX1=i1,…,Xn=in=i∈Ipipii1…pin-1in
证由全概率公式及马氏性质有
PX1=i1,⋯,Xn=in=Pi∈IX0=i, X1=i1,⋯,Xn=in
=i∈IPX0=i, X1=i1,⋯,Xn=in
=i∈IPX0=iPX1=i1X0=i⋯
∙PXn=in|X0=i, ⋯,Xn-1=in-1
=i∈IPX0=iPX1=i1X0=i⋯
PXn=in|Xn-1=in-1
=i∈Ipipii1⋯pin-1in
证毕

一、 马尔可夫链的的一些简单例子
马尔科夫链在研究质点的随机运动、自动控制、通信技术、生物工程、经济管理等领域中有着广泛的应用。
例4.1 无限制随机游动
设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动的概率为q=1-p，这种运动称为无限制随机游动。以Xn表示时刻n质点所处的位置，则{Xn,n∈T}是一个齐次马尔科夫链，试写出它的一步和k步转移概率。

解 显然{Xn,n∈T}的状态空间I={0,±1,±2,…}，其一步转移概率矩阵为
P=………q ……0p ……0……0…… q0…… p………
设在第k不转移中向右移了x步，向左移了y步，且经过k步转移状态从i进入j，则
x+y=k，x-y=j-i，
从而
x=k+(j-i)2，y=k-(j-i)2.
由于x，y都只能取整数，所以k±(j-i)必须是偶数。又在k步中哪x步向右，哪y步向左是任意的，选取的方法有ckx种。于是
pij(k)=ckxpxqy，k+j-i为偶数0，k+j-i为奇数。

例4.2 赌徒输光问题
两赌徒甲、乙一系列赌博。赌徒甲有a元。赌徒乙有b元，每赌一局输者给赢者1元，没有和局，直到两人中有一个输光为止。设在每一局中，甲赢的概率为p，输的概率为q=1-p，求甲输光的概率。
这个实质上是带有两个吸收壁的随机游动，其状态空间I={0,1,2,…,c}，c=a+b.故现在的问题是求质点从a点出发到达0状态先于到达c状态的概率.

解 设ui表示甲从状态i出发转移到状态0的概率，我们要计算的就是ua。由于0和c是吸收状态，故
u0=1，uc=0.
由全概率公式
ui=pui+1+qui-1，i=1,2,…c-1. （3.1）
上式的含义是，甲从有i元开始赌到输光的概率等于“他接下去赢了一局（概率为p），处于状态i+1后再输光”；和“他接下去输了一局（概率为q），处于状态i-1后再输光”这两个事件的和事件的概率。
由于p+q=1,（3.1）式实质上是一个差分方程
ui+1-ui=rui-ui-1，i=1,2,…,c-1， （3.2）
其中r=qp，其边界条件为
u0=1，uc=0. （3.3）
先讨论r=1，即p=q=12的情况，此时（3.2）为
ui+1-ui=ui-ui-1，
令i=1,2,…,c-1，u1=u0+a，得
u2=u1+a=u0+2a，
…
ui=ui-1+a=u0+ia，
…
uc=uc-1+a=u0+ca.
将u0=1，uc=0代入最后一式，得参数
a=-1c，
所以ui=1-ic，i=1,2,…,c-1.
令i=a，求得甲输光的概率为ui=1-ac=ba+b.
上述结果表明，在p=q情况下（即甲、乙每局比赛中输赢是等可能的情况下），甲输光的概率与乙的赌本b成正比，即赌本小者输光的可能性大。
由于甲、乙的地位是对称的，故乙输光的概率为
ub=aa+b.
由于ua+ub=1，表明甲、乙中必有一人要输光，赌博迟早要结束。
再讨论r≠1，即p≠q的情况。由（3.2）式得
uc-uk=i=kc-1r(ui-ui-1)=i=kc-1riu1-u0
=u1-1rk-rc1-r. （4.14）
令k=0，由于uc=0，有
1=1-u11-rc1-r
即 1-u1=1-r1-rc
代入（3.4）式，得
ua=rk-rc1-rc，k=1,2,…,c-1.
令k=a，的甲输光的概率
ua=ra-rc1-rc
由对称性，乙输光的概率为(r1=p/q)
ub=r1b-r1c1-r1c
由于ua+ub=1，因此在r≠1时，即p≠q时两个人中也总有一个人要输光的。

例4.3 天气预报有问题
设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨，今日有雨，明日有雨的概率为0.5；昨日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为0.2.若星期一、星期二均下雨，求星期四下雨的概率。

解 设昨日，今日连续两天有雨称为状态0(RR)；昨日无雨，今日有雨称为状态1(NR)；昨日有雨，今日无雨称为状态2(RN)；昨日，今日无雨称为状态3(NN)；。由于天气预报模型可看作一个四状态的马尔可夫链，其转移概率为
p00=PR今R明R昨R今}=P{连续三天有雨}
=PR明R昨R今}=0.7，
p01=PN今R明R昨R今}=0(不可能事件)，
p02=PR今N明R昨R今}=PN明R昨R今}=1-0.7=0.3，
p03=PN今N明R昨R今}=0(不可能事件)，
其中R代表有雨，N代表无雨。类似的可以得到所有状态的一步转移概率。于是它的一步转移概率矩阵为
P=p00p01p10p11p02p03p12p13p20p21p30p31p22p23p32p33=0.700.500.300.5000.400.200.600.8
其两步转移概率矩阵为:
P(2)=PP=0.700.500.300.5000.400.200.600.80.700.500.300.5000.400.200.600.8=0.490.120.350.200.210.180.150.300.200.120.100.160.200.480.100.64
由于星期四下雨意味着过程所处的状态为0或1，因此星期一，星期二连续下雨，星期四又下雨的概率为
P=p00(2)+p01(2)=0.49+0.12=0.61

例4.4 设质点在线段[1,4]上作随机游动，假设它只能在时刻n∈T发生移动，且只能停留在1,2,3,4点上。当质点转移到2,3点时，它以13的概率向左或向右移动一格，或停留在原处。当质点移动到点1时，它以概率1停留在原处。当质点移动到点4时，它以概率1移动到点3。若以Xn表示质点在时刻n所处的位置，则{Xn,n∈T}是一个齐次马尔科夫链，其转移概率矩阵为
P=101313 0013001300 131310
各状态之间的转移关系及相应的转移概率如图所示。
例中的点1称为吸收壁，即质点一旦到达这种状态后就被吸收住了，不再移动；点4称为反射壁，即质点一旦到达这种状态后，必然被反射出去。

例4.5 生灭链。观察某种生物群体，以Xn表示在时刻n群体的数目，设为i个数量单位，如在时刻n+1增生到i+1个数量单位的概率为bi，减灭到i-1个数量单位的概率为ai，保持不变的概率为ri=1-(ai+bi)，则{Xn,n≥0}为齐次马尔科夫链，I={0,1,2,…}，其转移概率为
pij=bi，j=i+1，ri，i=j，ai，j=i-1.
(a0=0)，称此马尔科夫链为生灭链。

总结