CH13 马尔可夫链
2014年8月23日星期六
Page 4
定义1：具有标号的随机变量组{Xi}称为随 机过程，其中i∈I。 随机过程中，随机变量可取到的值称 为状态，其全部可能取值的集合称为状 态空间。标号（指标参数）全部可能取 值组成的集合I称为参数空间，参数空间I 常表示时刻。
CH13 马尔可夫链
二步平稳转移概率矩阵的第
一行的三个数p00(2),p01(2), p02(2)分别为一步转移矩阵 p11
p02
1
p21
p12
2
p22
的第一行乘以第一，二，三列所得，同样第二行的三个数
CH13 马尔可夫链
2014年8月23日星期六
Page 17
P10(2),p11(2),p12(2) 分别为二步转移矩阵的第二行乘以第一，二， 三列所得，p20(2),p21(2),p22(2)分别为第三行乘以第一，二，三列 所得， 一般地：prs(2) = prTps , 如果定义两步平稳转移概率矩阵 P(2)=(prs(2)) , 则我们有： P(2)=P(1) * P(1) = P2 n步平稳转移概率
CH13 马尔可夫链
2014年8月23日星期六
Page 8
这些问题的研究是很有现实意义的，例如： 根据市场统计了解到，目前某公司生产的商品占 有一定的销路比例，我现在要预测，n步以后， 该公司将占有的销路比例是多少？另外，参加竞 争的商品占有销路的比例会稳定吗？ 我们关心的是分析这样一类系统，即系统的 下一个状态与当前状态有关，而与系统以前状态 完全无关，这样的随机过程称为马尔可夫过程。 或马尔可夫链，它可用来回答上述问题和其它许 多与动态系统有关的问题。 人们已用马尔可夫链来分析库存问题、商 品销路问题、设备更新问题、人口增长问题、会 计问题、工厂布局问题及有关动态系统的其它问 题。
CH13 马尔可夫链
2014年8月23日星期六
Page 15
P(0) =
( 0) p0 ( 0) p1 ( 0) p2
(1) ,P =
(1) p0 (1) 分别为初始的和一步 p1 (1) p2
分配比例向量。 定义5：n 步平稳转移概率 prs (n) =p(x i+n = s|x i= r ) = p(xn=s| x0=r) 式中 p rs (n)>=0 对所有的状态r和s均成立 n=1,2……..
CH13 马尔可夫链
2014年8月23日星期六
Page 11
这就是说，对任意i, i +1步随机变量xi+1所 处的某一状态的概率，仅受紧接在它前 面的随机变量 xi 所处的状态影响，而与 再前面的随机变量x0,x1,……xi-1所处的状 态无关，这种性质就是所谓的“无后效 性”。 概率p(xi+1 ＝s| xi=r)称为第i步的状态r转移到 第i+1步的状态s的一步转移概率（One step probability）,它是已知xi 时xi+1 的条 件概率。
由此，第２步商品销路分配比例
CH13 马尔可夫链
2014年8月23日星期六
Page 21
ＲＭ型：
p
(2) 0

p p
0
(0)
(2) 00

p p
1
(0)
(2) 10

p p
2
(0)
(2) 20
0.35*0.8228 0.3*0.0843 0.35*0.2439 0.400525
ＭＨ型：
=
p( X
tI
mn
s, Xm k t | Xm r )
CH13 马尔可夫链
2014年8月23日星期六
Page 19
=
p( X
tI
mn
s | Xm k t , Xm r ) p( Xm k t | Xm r )
=
p( X
tI
mn
CH13 马尔可夫链
2014年8月23日星期六
Page 18
从计算n步转移概率的证明式中，可以引出一般的性质：
p rs（n）=

tI
prt(k)pts(n-k)
（
n
整数 ）
这就是切普曼－柯尔莫哥洛夫方程，这要将上述证明中用k代替 n-1即得：
p
(n) rs
p( X
mn
s|
X
m
r)
p
(2) 1

p p
0
(0)
(2) 01

p p
1
(0)
(2) 11

p p
2
(0)
(2) 21
0.35*0.0450 0.3*0.7685 0.35*0.1950 0.31455
CH13 马尔可夫链
2014年8月23日星期六
Page 22
其他型：
p
(2) 2

p p
0
(0)
(2) 02
CH13 马尔可夫链
2014年8月23日星期六
Page 7
我们要研究的问题是： 1、如果系统现在处于状态r,则从现在起n步以后， 系统处于状态s的概率是多少？即： n步 求状态r 状态s的概率p rs(n) 。 2、很多步以后，系统处于状态s的概率是多少？ 即求p s(n) 。 3、如果系统现在处于状态r，步数不断增加，系 统处于状态s的概率，或者说步数不断增加， 系统处于状态s的概率是否稳定。即：lim p rs(n) n ∞ (n) 或 lim p s 是否存在，条件是什么？怎样求值？ n ∞ 4、从状态r首次到达状态s的期望步数是多少？

p p
1
(0)
(2) 12

p p
CH13 马尔可夫链
2014年8月23日星期六
Page 6
例2：某电话总机在[0，t）这段时间内接到的呼 叫次数是随机变量，如果要了解总机的工作情 况，就要研究呼叫次数随时间变化的过程，参 数空间是时间区间[0，+∞),t在一段时间内连续 变化，而[0，t）内的呼叫次数是离散的非负整 数，因此它是参数空间连续、状态空间离散的 随机过程。 例3：如果在上例中，每隔五分钟统计电话总机 接到呼叫的次数，则参数空间、状态空间都是 离散的随机过程。 我们将要讨论的是参数空间、状态空间都是离散 的情况，且一个系统可能的状态是有限的。
r=0,1,2,…..n)
,p1,…….pn)T。(pr=p(x0=r)
则称随机过程{Xi}为一阶、有限状态马尔可夫链。
例6-1 商品销路分配（书p454）
冻干午餐一步平稳转移概率如下表：
RM 0 RM 0 0.9
MH 1 p01
p00 0.02
“其他” 2 0.08 p02
MH 1
0.04 p10 0.87 p11
运筹学
Operations Research
第十三章 马尔可夫链
13.1 引 言 13.2 马尔可夫链 13.3 首次到达时间 13.4 马尔可夫分析的计算机程序
11.1 引言
Introduction
CH13 马尔可夫链
2014年8月23日星期六
Page 3
根据当前的状态和发展趋向去预测 未来的状态，这是管理决策中重要的 环节之一，马尔可夫分析就是这方面 常用的方法。 我们不断观察一个系统所处的状 态，这可以用一簇随机变量来表示， 这就是随机过程。
(n) p rs =1对所有的状态r均成立 n=1,2…….. s 0 n
从现态必然要转到次态
CH13 马尔可夫链
2014年8月23日星期六
Page 16
请注意共有N+1种状态，下面来进一步推导一下n步平稳转移 概率的计算公式，先看一下三个状态的二步平稳转移概率计 p00 算，见右下图。 p00(2) =p00p00 +p01p10 + p02p20 p01(2) =p00p01 +p01p11 + p02p21 p02(2) =p00p02 +p01p12 + p02p22 p01 0 p10 0 p20
2014年8月23日星期六
Page 5
• 状态和参数，可以是离散的，也可以是连续的。 据此，可将随机过程分成四类： 即：1、参数空间，状态空间均离散； 2、参数空间离散，状态空间连续； 3、参数空间连续，状态空间离散； 4、参数空间、状态空间均连续。 例1：我们要了解某地区10月1日一昼夜气温的变 化情况，就要观察气温这个随机变量的变化过 程，参数空间是时间区间[0，24），状态空间 是气体实数，它们都是非离散的随机过程。
p( X p( X p( X p
tI tI ts tI
n
n
1
s | X 0 t ) p ( X n 1 t | X 0 r )
tI
( n 1) ( n 1) prt prt pts
所以，n步平稳转移概率矩阵P(n)=P(n-1)*P=…Pn (P是一步平稳 转移矩阵）
0.09 p12
CH13 马尔可夫链
2014年8月23日星期六
Page 14
上述随机过程为一阶、有限状态的马尔可夫链 第一步RM的销路分配比例p0(1) (第1步后处于状态0的概率) P0(1) =P0(0)P00(1) +P1(0)P10(1) +P2(0)P20(1) =0.35*0.9 +0.3*0.04 +0.35*0.15=0.3795 第一步MH的销路分配比例p1(1) p1(1) = p0(0)p01(1) + p1(0) p11(1) +p2(0)p21(1) =0.35*0.02 +0.3*0.87+0.35*0.12=0.31 第一步其他的销路分配比例 p2(1) p2(1) =p0(0)p02(1) +p1(0)p12(1)+p2(0)p22(1) =0.35*0.08 +0.3*0.09 +0.35*0.73 =0.3105 写成矩阵形式：P(1) =PTP (0) 其中