马尔可夫过程[应用材料]

1、马尔可夫过程 神和尧 1沐风书苑 2沐风书苑 一类随机过程（数学基础是随机过程理论）。一类随机过程（数学基础是随机过程理论）。 原始模型马尔可夫链，由俄国数学家原始模型马尔可夫链，由俄国数学家A.A.A.A.马尔可夫马尔可夫 于于19071907年提出。年提出。 该过程具有如下特性：在已知目前状态该过程具有如下特性：在已知目前状态 （现在）（现在） 的条件下，它未来的演变的条件下，它未来的演变 （将来）不依赖于它以往（将来）不依赖于它以往 的演变的演变 ( ( 过去过去 ) ) 。 例如森林中动物头数的变化构成例如森林中动物头数的变化构成马尔可夫过马尔可夫过 程程 。在现实世界中，有很多过程都

2、是马尔可夫过程，。在现实世界中，有很多过程都是马尔可夫过程， 如液体中微粒所作的布朗运动、传染病受感染的人如液体中微粒所作的布朗运动、传染病受感染的人 数、车站的候车人数等，都可视为马尔可夫过程。数、车站的候车人数等，都可视为马尔可夫过程。 马尔可夫过程简介 3沐风书苑 马尔可夫过程定义 马尔可夫特性马尔可夫特性 如果一个随机过程的概率分布函数具有以下特性如果一个随机过程的概率分布函数具有以下特性 PX(t) xn| X(tn) = xn, X(tn-1) = xn-1, , X(t0) = x0 = PX(t) x| X(tn) = xn,ttntn-1.t0 则称该随机过程具有马尔可夫特性

3、。则称该随机过程具有马尔可夫特性。 一个具有马尔可夫特性的随机过程被称为马尔可一个具有马尔可夫特性的随机过程被称为马尔可 夫过程。夫过程。 离散状态空间的马尔可夫过程也称为马尔可夫链。离散状态空间的马尔可夫过程也称为马尔可夫链。 4沐风书苑 值得指出的是，马尔可夫链既可以是连续时间的，值得指出的是，马尔可夫链既可以是连续时间的， 也可以是离散时间的，它取决于系统参数的设定。也可以是离散时间的，它取决于系统参数的设定。 以离散时间的马尔可夫链为例，其定义为：设一个离散以离散时间的马尔可夫链为例，其定义为：设一个离散 的随机序列的随机序列XnXn（n=1,2n=1,2，.,N.,N），若它满足），

4、若它满足 PXPXn+1 n+1=x =xn+1 n+1|X |Xn n=x=xn n，X Xn-1 n-1=x =xn-1 n-1，.,X .,X0 0=x=x0 0=PX=PXn+1 n+1=x =xn+1 n+1|X |Xn n=x=xn n 则称之为离散时间马尔可夫链。则称之为离散时间马尔可夫链。 5沐风书苑 马尔可夫特性的直观解释为：马尔可夫特性的直观解释为： 在给定在给定t t时刻随机过程的状态为时刻随机过程的状态为XnXn或或x xn n，则该过，则该过 程的后续状态及其出现的概率与程的后续状态及其出现的概率与t t之前的状态无关。之前的状态无关。 也就是说，过程当前的状态包括了

5、过程所有的历史也就是说，过程当前的状态包括了过程所有的历史 信息，该过程的进一步发展完全由当前状态所决定，信息，该过程的进一步发展完全由当前状态所决定， 与当前状态之前的历史无关，这种性质也称为无后与当前状态之前的历史无关，这种性质也称为无后 效性或无记忆性。效性或无记忆性。 此特性也可以理解为：随机过程此特性也可以理解为：随机过程XnXn在在“现在现在” 状态已知的条件下，过程状态已知的条件下，过程“将来将来”的情况与的情况与“过去过去” 无关。或者说，过去只影响现在，而不影响将来。无关。或者说，过去只影响现在，而不影响将来。 PP将来将来| |现在、过去现在、过去=P=P将来将来| |现在

6、现在 6沐风书苑 马尔可夫过程分类 按其状态空间按其状态空间E E和时间参数集和时间参数集T T是连续还是离散可分成四类：是连续还是离散可分成四类： （1 1）时间离散、状态离散的马尔可夫过程）时间离散、状态离散的马尔可夫过程马尔可夫链。马尔可夫链。 参数集参数集T=0,1,2,T=0,1,2,状态空间状态空间E=E=整数整数 （2 2）时间连续、状态离散的马尔可夫过程）时间连续、状态离散的马尔可夫过程可列马尔可夫过可列马尔可夫过 程、连续参数马尔可夫链。程、连续参数马尔可夫链。 参数集参数集T=0, ,T=0, ,状态空间状态空间E=E=整数整数 （3 3）时间离散、状态连续的马尔可夫过程）

7、时间离散、状态连续的马尔可夫过程马尔可夫序列。马尔可夫序列。 参数集参数集T= 0,1,2,T= 0,1,2,状态空间状态空间E= (-, +)E= (-, +) （4 4）时间连续、状态连续的马尔可夫过程。）时间连续、状态连续的马尔可夫过程。 参数集参数集T= 0, ,T= 0, ,状态空间状态空间E= (-, +)E= (-, +) 7沐风书苑 分类分类 名称名称 E T 离散离散连续连续 离散离散 （n=0,1,2,.,n)n=0,1,2,.,n) 马尔可夫链马尔可夫链马尔可夫序列马尔可夫序列 连续连续 （n=0,1,2,.,n)n=0,1,2,.,n) 可列马尔可夫过程可列马尔可夫过程

8、马尔可夫过程马尔可夫过程 表表1 1 马尔可夫过程的分类马尔可夫过程的分类 8沐风书苑 马尔可夫特性要求系统处于任何状态的时间分布具马尔可夫特性要求系统处于任何状态的时间分布具 有无记忆性。有无记忆性。 对于连续型随机变量对于连续型随机变量X X，满足无记忆特性的概率分布函数为：，满足无记忆特性的概率分布函数为： PXPXt+t+|X|Xt=t=PXPX 它的密度函数为指数分布它的密度函数为指数分布 f(x)=ef(x)=e-x -x 无记忆性要求在连续时间马尔科夫链状态的驻留时间为无记忆性要求在连续时间马尔科夫链状态的驻留时间为 服从指数分布的随机变量。同样的，对于离散时间马尔科服从指数分布

9、的随机变量。同样的，对于离散时间马尔科 夫链，驻留时间必定是满足几何分布的随机变量。夫链，驻留时间必定是满足几何分布的随机变量。 以以s s表示随机过程在一个状态表示随机过程在一个状态i i的驻留时间，则有的驻留时间，则有 Ps=i=pPs=i=pi-1 i-1（ （1-p1-p）（）（i=1,2,3i=1,2,3，.） 9沐风书苑 驻留时间是检验随机过程是否属于马尔可夫过程的驻留时间是检验随机过程是否属于马尔可夫过程的 重要标志。重要标志。 检验一个随机过程是否满足马尔可夫特性；检验一个随机过程是否满足马尔可夫特性； 状态驻留时间是否是无记忆的；状态驻留时间是否是无记忆的； 过程从一个状态到

10、另一个状态的概率是否仅依赖过程从一个状态到另一个状态的概率是否仅依赖 于要离开的状态和目的状态。于要离开的状态和目的状态。 10沐风书苑 马尔可夫过程的形式化定义为：马尔可夫过程的形式化定义为： 设设X(t),tX(t),t00是取值为是取值为E=0E=0，1 1，2 2，.离散状离散状 态空间的一个随机过程，若对任意自然数态空间的一个随机过程，若对任意自然数n n以及以及n n个时刻个时刻 点，均有点，均有 X(tX(tn n)=i)=in n|X(t|X(t1 1)=i)=i1, 1,X(t X(t2 2)=i)=i2,. 2,.X(t X(tn-1 n-1)=i )=in-1 n-1 =

11、X(t =X(tn n)=i)=in n|X(t|X(tn-1 n-1)=i )=in-1 n-1 i i1 1，i,2i,2，.i.in n E 其中，其中，X(ti)=ti表示处于表示处于ti（i=1,2，.n)时刻的状态，时刻的状态， 则称则称X(t),tX(t),t00为离散状态空间为离散状态空间E E上的连续时间马尔可上的连续时间马尔可 夫过程。夫过程。 11沐风书苑 转移概率函数转移概率函数 若对任意若对任意t t，u u00，均有，均有 PX(t+u)=j|X(u)=i=PPX(t+u)=j|X(u)=i=Pij ij(t) i,j (t) i,j E 与与u u无关，则称马尔可

12、夫过程无关，则称马尔可夫过程X(t),tX(t),t00是齐次的。即是齐次的。即P Pij ij(t) (t) 只与时间差只与时间差t t有关，而与时间起点有关，而与时间起点u u的位置无关。的位置无关。一般如不作一般如不作 特别说明，马尔可夫过程均假设是齐次的。特别说明，马尔可夫过程均假设是齐次的。 对固定对固定i,ji,j E，函数，函数P Pij ij(t) (t)称为转移概率函数。称为转移概率函数。 P(T)=(PP(T)=(Pij ij(t) (t)称为转移概率矩阵。称为转移概率矩阵。 此处，假定马尔可夫过程是正则的，即有此处，假定马尔可夫过程是正则的，即有 , 0 1 () ( )

13、 0 () lim i jij t ij Pt ij 12沐风书苑 ij ij ikkjij j jkkj 1 1 3) =tj jtj =t j E k E k E P P PPP P PPP 转移概率函数具有以下性质： ）（t) 0 2)（t) （u) （v)=（u+v) 若令（t) PX()= ， E。它表示时刻系统处于状态的概率，则有 （t)（0) （) 13沐风书苑 状态转移图和状态转移率矩阵状态转移图和状态转移率矩阵 马尔可夫模型常使用状态转移图来描述系统的运行情况。马尔可夫模型常使用状态转移图来描述系统的运行情况。 图1 马尔可夫过程的状态转移图 修复（q） 故障（p） 1-p1

14、-q SF 14沐风书苑 图图1 1所示为一个可修复系统的状态转移图，系统所示为一个可修复系统的状态转移图，系统 存在存在“正常（正常（S)S)”和和“故障（故障（F)F)”两种状态。当出两种状态。当出 现故障时，系统将从现故障时，系统将从“S S”状态转移到状态转移到“F F”状态；状态； 一旦修复成功，系统将会由一旦修复成功，系统将会由“F F”状态转移到状态转移到“S S” 状态。由于这两种状态出现的概率及其持续时间具状态。由于这两种状态出现的概率及其持续时间具 有随机性，它们的转移规律只能按照某种概率转移。有随机性，它们的转移规律只能按照某种概率转移。 图图1 1中中p p、q q为状

15、态的转移概率。显然，为状态的转移概率。显然，0 0 p 1,0 q 1。 根据上述分析，还可以得到系统状态的转移率矩阵：根据上述分析，还可以得到系统状态的转移率矩阵： 1 1 pp A qq 15沐风书苑 系统经过多次转移后，通常会达到一个与时间系统经过多次转移后，通常会达到一个与时间 无关的稳定状态。此时，系统在状态转移过程中，无关的稳定状态。此时，系统在状态转移过程中， 在各状态逗留的概率不再发生变化。求解系统处于在各状态逗留的概率不再发生变化。求解系统处于 各种状态的稳态概率是研究离散事件系统特性的重各种状态的稳态概率是研究离散事件系统特性的重 要手段。要手段。 稳态概率及其求法稳态概率

16、及其求法 系统在各状态的稳定概率通常有以下两种解法：系统在各状态的稳定概率通常有以下两种解法： 已知瞬态概率，求极限已知瞬态概率，求极限 lim S (t) ii t AP 式中式中 S Si i（t t）-系统系统i i状态的瞬态概率；状态的瞬态概率； A Ai i-i-i状态的稳态概率。状态的稳态概率。 16沐风书苑 同构法同构法 当系统达到稳定状态以后，各种状态将持续转当系统达到稳定状态以后，各种状态将持续转 移，但是每种状态出现的概率基本不变，从而形成移，但是每种状态出现的概率基本不变，从而形成 一个稳定的状态空间。求解状态空间方程组，就可一个稳定的状态空间。求解状态空间方程组，就可

17、得到系统在各种状态的稳态概率。得到系统在各种状态的稳态概率。 通常，稳态概率空间的表达式不易求出，该解通常，稳态概率空间的表达式不易求出，该解 法适合于解决一些比较简单系统的稳态状态概率问法适合于解决一些比较简单系统的稳态状态概率问 题。题。 17沐风书苑 例例1 1 以图以图1 1所示模型为例，求解稳态概率。所示模型为例，求解稳态概率。 图1 马尔可夫过程的状态转移图 修复（q） 故障（p） 1-p1-q S（1）F（2） 18沐风书苑 设系统处于正常状态的稳态概率为设系统处于正常状态的稳态概率为1 1和处于故障状和处于故障状 态的稳态概率为态的稳态概率为2 2，则有，则有 112 221

18、12 (1) (1) 1 pq qp 显然，前两个方程是线性相关的，可以删掉一个。解显然，前两个方程是线性相关的，可以删掉一个。解 方程组得：方程组得： 1 2 q pq p pq 19沐风书苑 例例2 2 设任意相继的两天中，雨天转晴天的概率为设任意相继的两天中，雨天转晴天的概率为1/31/3， 晴天转雨天的概率为晴天转雨天的概率为1/21/2，任一天晴或雨是互为逆事件。，任一天晴或雨是互为逆事件。 以以0 0表示晴天状态，以表示晴天状态，以1 1表示雨天状态，表示雨天状态，XnXn表示第表示第n n天状天状 态（态（0 0或或1 1）。又已知）。又已知5 5月月1 1日为晴天，问日为晴天，问5 5月月3 3日为晴天，日为晴天， 5 5月月5 5日为雨天的概率各等于多少？日为雨天的概率各等于多少？ 解：分析解：分析 分析状态转移过程，求出系统状态转移率矩阵；分析状态转移过程，求出系统状态转移率矩阵； 确定某状态下的转移概率矩阵；确定某状态下的转移概率矩阵； 求解。求解。 20沐风书苑