p13――正在接受服务的顾客继续要求服务，且 在Δt间隔内有两个顾客进入系统的概率。由 假设，后者实际上是不可能发生的，p13=0. 类似地，有p21= p32 = p(1-q), p22 = pq+(1-p) (1-q), p23=q(1-p), pij= 0( | i-j |≧2 ). p33――或者一人将离去且另一人将进入系统， 或者无人离开系统的概率，p33= pq+(1-p).
P {X ( t n ) ≤ x n X ( t1 ) = x1 , X ( t 2 ) = x 2 ,
, X ( t n −1 ) = x n −1 }
= P{X ( t n ) ≤ x n | X ( t n −1 ) = x n −1 },
xn ∈ R
或 Ft n | t 1 t 2
t n −1
X n Δ X ( nΔ t )
表示时刻n时，系统内的顾客数，即系统的状 态。｛xn, n=0，1，2,…｝是一随机过程，状态 空间I＝｛0，1，2，3｝，而且仿照例1、例2的分 析，可知它是一个齐次马氏链。下面来计算此马 氏链的一步转移概率。 p00――在系统内没有顾客的条件下，以后仍没有顾 客的概率（此处是条件概率，以下同），p00=1-q. p01――系统内没有顾客的条件下, 经Δt后有一顾 客进入系统的概率, p01
若以Xn表示时刻n时Q的位置，不同的位置就是Xn的不同 状态，那么｛Xn,n=0，1,2,…｝是一随机过程，状态空 间就是I，而且当Xn=i,i∈I为已知时,Xn+1所处的状态的概 率分布只与Xn=i有关，而与Q在时刻n以前如何到达i是完 全无关的，所以｛Xn,n=0，1,2,… ｝是一马氏链，且是 齐次的。它的一步转移概率和一步转移概率矩阵分别为
即马氏链{Xn,n≥0}的转移概率Pij(n,n+1)与n无关， 则称转移概率具有平稳性，这时，马尔可夫链称为是 齐次的。
p ij Δ p ij (1) = P {X m +1 = a j | X m = a i }
称为马氏链的一步转移概率；
P Δ P (1) = ( p ij (1) )
a1 P (1) = a1 a2 ai p11 p 21 pi1 a2 p12 p 22 pi 2 aj p1 j p2 j p ij
j =1 ij j =1
∞
∞
m+n
= a j | X m = ai }
⎧ ⎫ = P ⎨ ∪{X m + n = a j }| X m = a i ⎬ = 1. ⎩ j ⎭
2.齐次马尔可夫链及一步转移概率
定义 若对任意的正整数m,n及任意的ai，aj，有
Pij (n, n + 1) = Pij (m , m + 1)
系 随机到达者 等候室
统 服务台 离去者
设P表示一步转移概率Pij所组成的矩阵，则 称P为一步转移概率矩阵，它具有如下性质 （1） Pij≥0；
( 2)
∑ P (m, m + n) = 1,
j =1 ij
∞
i = 1,2,
（2）式中对j求和是对状态空间I的所有可能的状态 进行的。此性质说明，一步转移概率矩阵中任一行元 素之和为1。
p10――系统内恰有一顾客正在接受服务的条件 下，经Δt后系统内无人的概率，它等于在 间隔内顾客因服务完毕而离去，且无人进入系 统的概率，p10=p(1-q). p11――系统内恰有一顾客的条件下，在Δt间隔 内，他因服务完毕而离去，而另一顾客进入系 统，或者正在接受服务的顾客将继续要求服 务，且无人进入系统的概率，这p11＝pq＋(1p) (1-q). p12――正在接受服务的顾客继续要求服务，且 另一个顾客进入系统的概率，p12=q(1-p).
定义3 称条件概率 Pij ( m , m + n) Δ P {X m + n = a j | X m = a i } 为马尔可夫链在时刻m处于状态ai的条件下，在时刻m+n步 转移到状态aj的n步转移概率，简称为转移概率。
例(一维随机游动) 设一醉汉Q（或看作一随机游动的质
点），在如图所示直线的点集I＝｛1，2，3，4，5｝上 作游动，仅仅在1秒、2秒…等时刻发生游动。游动的概 率规则是：如果Q现在位于点i (1<i <5)，则下一时刻各以 1/3的概率向左或向右移动一格，或以1/3的概率留在原 处；如果Q现在位于1（或5）这点上，则下一时刻就以概 率1移动到2（或4）点上。1和5这两点称为反射壁。上面 这种游动称为带有两个反射壁的随机游动。
由于Xn, n=0，1，2,…独立同分布，因而
P {X n +1 = j | X n = i } = P {X n +1 = j} = q j = P { X m +1 = j | X m = i }
所以{Xn}为齐次马氏链。其一步转移概率P:
p ij = q j , i , j ∈ I .
//例3 排队模型 设服务系统由一个服务员和只可 以容纳两个人的等候室组成，见图。服务规则 是：先到先服务，后来者需在等候室依次排队。 假定一个需要服务的顾客到达系统时发现系统内 已有3个顾客（一个正在接受服务，两个在等候 室排队）则该 顾客即离去。设时间间隔Δt内 将有一个顾客进入系统的概率为q，有一原来被 服务的顾客离开系统（即服务完毕）的概率为 p。又设当Δt充分小时，在这时间间隔内多于一 个顾客进入或离开系统实际上是不可能的。再设 有无顾客来到与服务是否完毕是相互独立的。现 用马氏链来描述这个服务系统。
0 1
0 11-p
0 1
i∈χ为已知时，Xn+1所处的状态的概率分
布只与Xn=i 有关，而与时刻n以前所处的状态无关，所以它
且一步转移概率和一步转移概率矩阵分别为
⎧p j = i p ij = P{X n+1 = j | X n = i } = ⎨ i , j = 0,1 ⎩q j ≠ i ⎡ p q⎤ P= ⎢ ,且是齐次马氏链. ⎥ q p ⎣ ⎦
第十一章 马尔可夫链
马尔可夫链及其概率分布
引言
过程（或系统）在时刻t0所处的状态为已知的 条件下,过程在时刻t＞t0所处状态的条件分布与过 程在时刻t0之前所处的状态无关。 用分布函数表达此性质，设随机过程 {X(t),t∈T}，状态空间为χ，若对于t 的任意n个值 t1<t2<…<tn,n≥3, 有
可见,｛Xn,n=0，1，2,…｝是一个马氏链。
2．转移概率的性质
(1) Pij≥0；
( 2)
∑ P (m, m + n) = 1,
j =1 ij
∞
i = 1,2,
事实上，因为链在m时刻从状态ai出发，到m+n时刻 必然转移到a1，a2，…状态中的一个，从而
∑ P (m, m + n) = ∑ P{X
对任意的 n 及 i 0 , i 1 ,
, i n , i n −1 ∈ x ,
, X n = in }
P {X n +1 = i n +1 X 0 = i 0 , X 1 = i1 ,
⎧ 0 i n +1 > i n ⎪ =⎨1 = P{X n +1 = i n +1 | X n = i n } i n +1 ≤ i n ⎪ ⎩ in
1.马氏链的定义
定义1
若对于任意的正整数n，r和任意的
< t r < m , t i , m , m + n ∈ T = {0,1,2, , n}, 有
0 ≤ t1 < t 2 <
= P{X n+m = a j | X m = ai }
P X n+m = a j X t1 = ai1 , X t2 = ai2 , , X tr = air , X m = ai
( x n , t n | x1 , x 2 ,
, x n −1 ; t 1 , t 2 ,
, t n −1 )
= Ft n | t n − 1 ( x n , t n | x n − 1 ; t n − 1 )
即在 X ( t i ) = x i , i = 1,2, 数。
则称过程{X(t),t∈T}具有马尔可夫性，或称 {X(t),t∈T}为马尔可夫过程。
于是该马氏链的一步转移概率矩阵为
0 ⎡ (1 − q) q 0 0 ⎤ ⎥ 1⎢ p ( 1 − q ) pq + ( 1 − p )( 1 − q ) q ( 1 − p ) 0 ⎥ p= ⎢ 2⎢ 0 p(1 − q) pq + (1 − p)(1 − q) q(1 − p) ⎥ ⎢ ⎥ 3⎣ 0 0 p(1 − q) pq + (1 − p)⎦
如果把1这一点改为吸收壁，即Q一旦到达1，就永远留 在点1上。此时，相应链的转移概率矩阵只须把P中第1横 行改为（1，0，0，0，0）。总之，改变游动的概率规 则，就可得到不同方式的游动和相应的马氏链。
例
设Xn,n=0，1，2,…是独立同分布的随机变量列,记 Xn可能取值的全体为I={i,i ≥1},则{Xn}为马氏链，并 求其一步转移概率。
其中a.∈χ, 称｛Xn,n=0,1，2，…｝为马氏链。
{
}
Pij (m, m + n)Δ P{X n+m = a j | X m = ai }
称为马氏链在时刻m系统处于状态ai的条件下，在时刻 m+n转移到状态aj的转移概率。
设{Xn,n≥0},其状态空间为χ,若对于任意的正 整数n和任意的 a i0 , a i1 , , a in , a in + 1 ∈χ, 定义2
⎧1 ⎪3 ⎪ = j | X n = i} = ⎨ 1 ⎪ 0 ⎪ ⎩ j = i − 1, i + 1,1 < i < 5, i = 1, j = 2或i = 5, j = 4 | j − i |≥ 2