当前位置:首页 >> 理学 >>

随机过程Chapter 3.1 Definition and Examples of Markov Chain


第三章 Markov 过程
3.1 Markov链的定义和例子

3.2 Markov链的状态分类
3.3 Markov链的极限定理和平稳分布

2013-8-14

1

考虑一个随机过程{Xt, t?T}. 我们假设随机变量
Xt的取值在某个集合E中, 则集合E称为状态空间.

独立随机试验模型最直接的推广就是Markov模
型. 粗略地说, 一个随机过程如果给定了当前时刻t的

值Xt, 未来s>t的值Xs不受过去Xu (u<t)的影响就称为
是有Markov性. 如果一个过程具有Markov性, 则称

该过程为Markov过程. 特别地, 当状态空间E为至多
可列集时, Markov过程称为Markov链.

对于Markov链, 当指标集T是非负整数时, 称为 离散时间Markov链; 当指标集T是连续时间时, 称为 连续时间Markov链.

3.1 Markov链的定义和例子
对于离散时间Markov链{Xn, n=0,1,…}, 状态空

间也可记为E={0,1, 2, …}. 此时, “Xn=i”就表示过程
在n时刻处于状态i.

定义3.1 如果对任何一列状态i0, i1, …, in-1, i, j, 及对 任何n?0, 随机过程{Xn, n?0}满足Markov性质:
P { X n ? 1 ? j | X 0 ? i0 , L , X n ? 1 ? i n ? 1 , X n ? i } ? P{ X n ?1 ? j | X n ? i }

则称随机过程{Xn, n?0}为离散时间Markov链.

定义3.2 设{Xn, n?0}为一离散时间Markov链. 对于

任意i, j?E, 则 P{Xn?1 ? j | Xn ? i} 称为Markov链的
n 一步转移概率, 记作 pij,n.?1

当这一概率与n无关时, 称该Markov链为有平稳
转移概率,并记为 pij .

有 平 稳 转 移 概 率 的 Markov 链 , 也 称 为 时 齐 Markov链. 它的平稳转移概率具有下面性质:
(1)
(2)

pij ? 0 ,

?i, j
?i

?p
j

ij

? 1,

通常把转移概率排成一个(无穷维的)方阵, 记作
? p00 ? ? p10 P ? ?L ? ? pi 0 ? ?L p01 L p11 L L L L L pi 1 L p0 j L ? ? p1 j L ? L L? ? pij L ? ? L L?

称为Markov链的转移概率矩阵.

定义3.3 设{Xn, n?0}为任一时齐的离散时间Markov
链. 则对于任意i, j?E, P{Xm?n ? j | Xm ? i}都与m无
(n 关, 称为Markov链的n步转移概率, 记作 pij ) 即:
( pijn) ? P{ Xm?n ? j | Xm ? i }.
( ( pijn)为元素的矩阵 [ pijn ) ]称为n步转移概 通常把以 ( 率矩阵, 记作P ( n) ? [ pijn) ].

若时齐Markov链的n步转移概率矩阵为 P(n) , 初 始概率向量为p0, 则经过n步转移后的概率向 量为: p0 P ( n) .

定理3.1 对于任意的n, m?0 及 i, j?E,

p

( n? m ) ij

?

k?E

?p

( n) ik

p

(m) kj

.

证: 按时刻n的状态进行分解, 再用Markov性, 有
( pijn? m ) ? P{ Xn?m ? j | X0 ? i }

? ? P{ X n? m ? j , X n ? k | X 0 ? i }
k?E

? ? P{ X n ? k | X 0 ? i }P{ X n? m ? j | X n ? k , X 0 ? i }
k?E

? ? P{ X n ? k | X 0 ? i }P{ X n? m ? j | X n ? k }
k?E ( ( ? ? pikn ) pkjm ) . k?E

注: 定理3.1称为Chapman-Kolmogorov方程.

它的直观意义十分明显, 从状态i出发经过
n+m步到达状态j可分成两阶段走: 先从状态i 出发经过n步到达状态k, 然后从状态k出发经 过m步到达状态j. 由Markov性, 后一阶段的状 态转移与前一阶段的状态转移独立, 故两个 阶段的转移概率相乘. 由于状态k不受任何限

制, 因此应对全部的k求和.

推论1 对于任意的n, m?0,

P

(n ? m)

?P P .
(n) (m)

注: 推论中的矩阵可以是无穷阶的, 但是乘法

规则与有限矩阵一样.
推论2 对于任意的n?0,

P ?P .
(n) n

定理. 时齐Markov链{ X n }的任意有限维分布族由
其初始分布和转移概率唯一确定.

证:设k为任意的正整数,对k个整数0 ? n1 ? n2 ? K
? nk 和任意的i1 ,K , ik ? E,

P{ X n1 ? i1 ,K , X nk ? ik }
? ? P{ X 0 ? i , X n1 ? i1 ,K , X nk ? ik }
i?E

? ? P{ X nk ? ik | X 0 ? i , X n1 ? i1 ,K , X nk ?1 ? ik ?1 }
i?E

? P{ X 0 ? i , X n1 ? i1 ,K , X nk ?1 ? ik ?1 }
12

? ? P{ X nk ? ik | X 0 ? i , X n1 ? i1 ,K , X nk ?1 ? ik ?1 }
i?E

? P{ X nk ?1 ? ik ?1 | X 0 ? i , X n1 ? i1 ,K , X nk ?2 ? ik ? 2 }K ? P{ X n1 ? i1 | X 0 ? i } ? P{ X 0 ? i }

? ? P{ X nk ? ik | X nk ?1 ? ik ?1 } ? P{ X nk ?1 ? ik ?1 | X nk ?2 ? ik ? 2 }K
i?E

? P{ X n1 ? i1 | X 0 ? i } ? P{ X 0 ? i }
( ? ? p0 (i ) piin1 ) pi(1n22 ? n1 ) K pi(knk1i? nk?1 ) i 1 ? k i?E

13

例3.1 (直线上的随机游动)考虑在直线上整数点上
运动的粒子. 当它处于位置j时, 这里姑且假定j

就是所处的状态, 向右游动到j+1的概率为p而向
左游动到j-1的概率为q=1-p. 假定时刻0时粒子

处在原点, 即X0=0, 于是粒子在时刻n所处的位
置Xn就是一个Markov链, 它有转移概率:

p jk

? p, ? ? ?q, ? 0, ?

k ? j ?1 k ? j ?1 其他 k

? ?L ? ?L ? ?L P ? ?L ? ?L ?L ? ?L ? ?

M M M M M M M ? ? 0 p 0 0 L 0 0 L? q 0 p 0 L 0 0 L? ? 0 q 0 p L 0 0 L? 0 0 q 0 L 0 0 L? ? L L L L L L L L? 0 0 0 0 L 0 p L? ? 0 0 0 0 L q 0 L? ? M M M M M M M ?

例3.2 (带吸收壁的随机游动) 一个粒子在直线上整数点
0,1,…,n上运动, 每次向右或左运动一步, 概率分别为p

和q=1-p. 如果粒子到达了0或n, 则停止运动. 用Xn表
示粒子经过n步运动后所在的位置, 则它是一个 Markov链, 状态空间为E={0,1,…,n}, 并且有转移概率:

? p, ? q, ? ? pij ? ? 1, ? 1, ? ? 0, ?

j ? i ? 1,1 ? i ? n ? 1 j ? i ? 1,1 ? i ? n ? 1 i ? 0, j ? 0 i ? n, j ? n 其他

?1 ?q ? ?0 ? ?0 P ? ?L ? ?0 ?0 ? ?0 ?0 ?

0 0 q 0 L 0 0 0 0

0 p 0 q L 0 0 0 0

0 0 p 0 L 0 0 0 0

0 0 0 p L 0 0 0 0

L L L L L L L L L

0 0 0 0 L p 0 q 0

0 0 0 0 L 0 p 0 0

0? ? 0? 0? ? 0? L? ? 0? 0? ? p? ? 1?

当p ? q ? 1 时, 称为简单对称随机游动. 它可 2
用于刻画公平赌博问题. 例如: 考虑出现正、反面概率均为0.5的扔硬币 游戏. 让粒子的位置Xn代表赌徒甲在第n次赌 博之后所赢的钱数(每扔硬币一次的输赢为1 元). 假如甲方有赌本a, 乙方有赌本b, 则可以

证明甲先输光的概率为

b . a?b

例3.3 下图为一个迷宫, 其中房间9放有一块 奶酪,而房间7里隐藏着一只猫. 现有一只老 鼠从房间1出发. 假设老鼠没有任何信息, 即: 当老鼠在一个给定房间时, 它进入相邻
1 房间的概率为 k , 其中k表示与该给定房间

相邻的房间个数. 假设一旦老鼠进入奶酪

或猫所在的房间, 则永远停留在该房间.

设Xn表示老鼠在时刻n时所处房间号, 则随机过程 {Xn, n=0,1,2,…}是一个以E={1,2,…,9}为状态空间的 Markov链, 并且初始概率向量为 p0 ? [1, 0, 0, ..., 0] , 转移概率矩阵为:

?0 ? ?1 ?3 ?0 ?1 ?3 P?? 0 ? ?0 ? ?0 ?0 ? ?0 ?

1 2 0 1 2 0 1 4 0 0 0 0

0 1 3 0 0 0 1 3 0 0 0

1 2 0 0 0 1 4 0 0 0 0

0 1 3 0 1 3 0 1 3 0 1 3 0

0 0 1 2 0 1 4 0 0 0 0

0 0 0 1 3 0 0 1 1 3 0

0 0 0 0 1 4 0 0 0 0

0? ? 0? ? 0? ? 0? ? 0? 1? 3? 0? 1? 3? 1? ?

例3.4 甲乙两人进行比赛,设每局比赛中甲胜的概

率是p,乙胜的概率是q,和局的概率是r,
(p+q+r=1).设每局比赛后,胜者记“+1”分,负

者记“-1”分,和局不记分.当两人中有一人获
得2分结束比赛.以Xn表示比赛至第n局时甲获得 的分数. (1) 写出状态空间; (2) 求P(2); (3) 问在甲获得1分的情况下,再赛两局可以结束比 赛的概率是多少?

例3.5 (排队论问题) 顾客到服务台排队等候服务. 在
每一服务周期中只要服务台前有顾客在等待,就要

对排在队前的一位提供服务. 当然, 如果服务台前
是空的就不可能实施服务. 设在第n个服务周期中 到达的顾客数为一随机变量Yn,其分布不依赖于 n,为P{Yn=k}= pk, k=0,1,…,并且Yn 是相互独立 的. 记Xn为服务周期n开始时服务台前排队的顾客 数.

例3.6 考虑一个三状态的Markov链{Xn}, 其转移 概率矩阵为:

0 ?1 P ? 1 ?p ? 2 ?0 ?

0 q 0

0? r? , ? 1? ?

其中p, q, r>0, p+q+r=1. 这一Markov链从状态 1出发, 一旦进入状态0或2就被吸收了. 求: (1) 过程从状态1出发被状态0吸收的概率; (2) 平均要多长时间过程会进入吸收状态.

解: 令 T ? min{ ? 0 | Xn ? 0 or 2}. n

u ? P{XT ? 0 | X0 ? 1 } v ? E[T | X 0 ? 1]
注意到: 如果X1=0, 则T =1, 于是XT=0, 因此

P{XT ? 0 | X1 ? 0} ? P{X1 ? 0 | X1 ? 0} ? 1
如果X1=2, 则T =1, 于是XT=2, 因此

P{XT ? 0 | X1 ? 2} ? P{X1 ? 0 | X1 ? 2} ? 0

由全概率公式得:

u ? P{XT ? 0 | X0 ? 1 ? ? P{ XT ? 0, X1 ? k | X 0 ? 1} }
k ?0

2

? ? P{X1 ? k | X 0 ? 1 ? P{XT ? 0 | X 0 ? 1, X1 ? k} } ? ? P{XT ? 0 | X1 ? k} ? P{X1 ? k | X 0 ? 1 }
k ?0 k ?0 2

2

? 1? p ? u ? q ? 0 ? r
? p ? uq

求解上述方程得:

u?

p p ? 1? q p ? r .

由全概率公式得:
v ? E[T | X 0 ? 1]
? ? P{ X 1 ? k | X 0 ? 1} ? E[T | X 0 ? 1, X 1 ? k ]
k ?0
2

2

? ? P{ X 1 ? k | X 0 ? 1} ? E[T | X 1 ? k ]
k ?0

? p ?1 ? q ? (1 ? v) ? r ?1
?1 ? vq

求解上述方程得:

1 v? 1? q

.

练习 某市场上只有A, B, C三种啤酒. A种啤酒改 变广告方式后经市场调查发现: 买啤酒的顾 客每两个月平均转移率如下:

A? A A? B A?C 0.2 0.7 0.1 B ? A B ? B B ?C 0.3 0.2 0.5 C ? A C ? B C ?C
设A, B, C三种啤酒的目前市场份额为25%, 40%, 35%, 求半年后A种啤酒的市场份额.

0.8

0.1

0.1

?0.8 0.1 0.1? 解: 转移概率矩阵为: P ? ?0.2 0.7 0.1? ? ? ?0.3 0.2 0.5? ? ?
半年后顾客的转移概率矩阵为:

因此,

?0.628 0.216 0.156? ?0.412 0.432 0.156? (3) 3 P ?P ?? ? ?0.488 0.292 0.22 ? ? ? ?0.628? ?0.25, 0.4, 0.35? ?0.412? ? 0.4926 ? ? ?0.488? ? ?

即: 半年后A种啤酒占有的市场份额为49.26%.


相关文章:
随机过程Chapter 3.1 Definition and Examples of Mark....ppt
随机过程Chapter 3.1 Definition and Examples of Markov Chain - 第三章 Markov 过程 3.1 Markov链的定义和例子 3.2 Ma...
...the stationary distribution of Markov chain_图文....ppt
随机过程Chapter 3.3 The limit theorem and the stationary distribution of Markov chain_教育学/心理学_人文社科_专业资料。第三章 Markov 过程 3.1 Markov链的...
马尔可夫链原理及应用实例探讨.pdf
马尔可夫过程数学定义如下[3]: X ( t ) , t ∈ T 为随机过程, 设 如果...OF PRINCIPLE AND EXAMPLES OF APPLICATION ON MARKOV CHAIN XueYan ZHU College ...
随机过程导论Introduction.pdf
随机过程导论Introduction_教育学_高等教育_教育专区。...definition of Poisson processes Many properties of ...Markov chain 14 Outline Chapter 6: Brownian ...
Stochastic Process_31_Markov Chain_图文.ppt
(状态离散时间离散的Markov过程 ) 3.1 基本概念 ? ...2007 C O Analysis of K... 20页 免费 Markov...Markov Chain Chapter5 101页 免费 北大随机过程课...
随机过程英语讲义-12_图文.pdf
随机过程英语讲义-12_研究生入学考试_高等教育_教育...Chapter 4 2 Andrey (Andrei) Andreyevich Markov ...10 4.1 Introduction and Examples Examples of stochastic...
随机过程英语讲义-11_图文.pdf
随机过程英语讲义-11_研究生入学考试_高等教育_教育...Chapter 4 2 Andrey (Andrei) Andreyevich Markov ...10 4.1 Introduction and Examples Examples of stochastic...
随机过程英语讲义-14_图文.pdf
随机过程英语讲义-14_研究生入学考试_高等教育_教育...from the results of Section 4.8 of Chapter 4, ...Markov chain is irreducible and Pj > 0 for all...
Markov Chain Chapter5_图文.ppt
随机过程Chapter 3.1 De... 29页 免费 Markov chain compariso... 23页...A Markov chain model f... 7页 1下载券 Matrix analysis of a M......
HHU Lecture 5 Markov chain_图文.pdf
and random process 第二章 随机变量与随机过程(邓安) Chapter 3 Bayesian ...2010-12-08 13 An example of Markov chain weather process p12 = 0.2...
随机过程matlab程序.doc
随机过程matlab程序_数学_自然科学_专业资料。% PPT...(Example 5.1.5) markov chain chushivec0=[0 ...('The average times of arriving 0 and 10 ...
08-模式识别-上下文分类汇总_图文.ppt
Markov Chain Models (for class dependence) P (?...在不同 的平稳过程之间进行有区别性的随机转移,使...20 ? Examples of HMM: ? The single coin case...
马尔可夫链模型在某些经济预测中的应用.pdf
马尔可夫链是一种有着广泛应用的随机过程模型,它对...and introduces two kinds of Markov chain ...19 3.1 状态空间分类(指标值的分级)方法 ......
模式识别课件-上下文分类_图文.ppt
M N 4 Markov Chain Models (for class dependence...平稳随机序列进行随机模型估计,在不同 的平稳过程...20 Examples of HMM: ? The single coin case: ...
II Stochastic process_图文.ppt
? Some examples of martingale Example2.2.2 Let...Inc 2.3 Markov Processes Definition 2.3.1 Let...在直线上作不规则运动的数学描述: 随机过程 Bt , ...
第04章 马尔可夫链S.ppt
=Pij 则随机过程称为马尔可夫链(a Markov chain)...状态分类(classification of states) 1.状态可达和...称为相通的(i and j are said to communicate),...
随机过程lunwen 文档.doc
关键词:马尔科夫链;一步状态转移概率矩阵;最优化模型;预测 Markov chain based on the optimal model of water quality test in the application Information and ...
基于前向-后向HMM的连续语音识别系统的研究.pdf
EngineeringandDesign 2009,30(18)4339 基于前向一...ofcontinuous established.Examplesshowthatthisvoice...Markov链是Markov随机过程的特殊情况,即Markov链 式...
马尔可夫链在天气预测中的应用_图文.doc
and get the distribution of the stable weather ...Markov chain;weather forecast 中图分类号:P45 文献...(Markov Process)是一个典型的随机过程,其基本概念...
概率论与数理统计专业硕博连读研究生培养方案.doc
of Modern Probability 第二外国语 Second Foreign Language 随机环境中的马氏过程 Markov processes in random environment 金融中的随机过程 Stochastic processes with...
更多相关标签: