马尔可夫过程ppt课件

马尔可夫过程,神和尧,1,2,一类随机过程（数学基础是随机过程理论）。原始模型马尔可夫链，由俄国数学家A.A.马尔可夫于1907年提出。该过程具有如下特性：在已知目前状态（现在）的条件下，它未来的演变（将来）不依赖于它以往的演变(过去)。例如森林中动物头数的变化构成马尔可夫过程。在现实世界中，有很多过程都是马尔可夫过程，如液体中微粒所作的布朗运动、传染病受感染的人数、车站的候车人数等，都可视为马尔可夫过程。,马尔可夫过程简介,3,马尔可夫过程定义,马尔可夫特性如果一个随机过程的概率分布函数具有以下特性PX(t)xn|X(tn)=xn,X(tn-1)=xn-1,X(t0)=x0=PX(t)x|X(tn)=xn,ttntn-1.t0则称该随机过程具有马尔可夫特性。,一个具有马尔可夫特性的随机过程被称为马尔可夫过程。,离散状态空间的马尔可夫过程也称为马尔可夫链。,4,值得指出的是，马尔可夫链既可以是连续时间的，也可以是离散时间的，它取决于系统参数的设定。,以离散时间的马尔可夫链为例，其定义为：设一个离散的随机序列Xn（n=1,2，.,N），若它满足PXn+1=xn+1|Xn=xn，Xn-1=xn-1，.,X0=x0=PXn+1=xn+1|Xn=xn则称之为离散时间马尔可夫链。,5,马尔可夫特性的直观解释为：,在给定t时刻随机过程的状态为Xn或xn，则该过程的后续状态及其出现的概率与t之前的状态无关。也就是说，过程当前的状态包括了过程所有的历史信息，该过程的进一步发展完全由当前状态所决定，与当前状态之前的历史无关，这种性质也称为无后效性或无记忆性。,此特性也可以理解为：随机过程Xn在“现在”状态已知的条件下，过程“将来”的情况与“过去”无关。或者说，过去只影响现在，而不影响将来。P将来|现在、过去=P将来|现在,6,马尔可夫过程分类,按其状态空间E和时间参数集T是连续还是离散可分成四类：,（1）时间离散、状态离散的马尔可夫过程马尔可夫链。参数集T=0,1,2,状态空间E=整数（2）时间连续、状态离散的马尔可夫过程可列马尔可夫过程、连续参数马尔可夫链。参数集T=0,状态空间E=整数（3）时间离散、状态连续的马尔可夫过程马尔可夫序列。参数集T=0,1,2,状态空间E=(-,+)（4）时间连续、状态连续的马尔可夫过程。参数集T=0,状态空间E=(-,+),7,表1马尔可夫过程的分类,8,马尔可夫特性要求系统处于任何状态的时间分布具有无记忆性。,对于连续型随机变量X，满足无记忆特性的概率分布函数为：PXt+|Xt=PX它的密度函数为指数分布f(x)=e-x,无记忆性要求在连续时间马尔科夫链状态的驻留时间为服从指数分布的随机变量。同样的，对于离散时间马尔科夫链，驻留时间必定是满足几何分布的随机变量。以s表示随机过程在一个状态i的驻留时间，则有Ps=i=pi-1（1-p）（i=1,2,3，.）,9,驻留时间是检验随机过程是否属于马尔可夫过程的重要标志。,检验一个随机过程是否满足马尔可夫特性；状态驻留时间是否是无记忆的；过程从一个状态到另一个状态的概率是否仅依赖于要离开的状态和目的状态。,10,马尔可夫过程的形式化定义为：,设X(t),t0是取值为E=0，1，2，.离散状态空间的一个随机过程，若对任意自然数n以及n个时刻点，均有X(tn)=in|X(t1)=i1,X(t2)=i2,.X(tn-1)=in-1=X(tn)=in|X(tn-1)=in-1i1，i,2，.inE其中，X(ti)=ti表示处于ti（i=1,2，.n)时刻的状态，则称X(t),t0为离散状态空间E上的连续时间马尔可夫过程。,11,转移概率函数,若对任意t，u0，均有PX(t+u)=j|X(u)=i=Pij(t)i,jE与u无关，则称马尔可夫过程X(t),t0是齐次的。即Pij(t)只与时间差t有关，而与时间起点u的位置无关。一般如不作特别说明，马尔可夫过程均假设是齐次的。对固定i,jE，函数Pij(t)称为转移概率函数。P(T)=(Pij(t)称为转移概率矩阵。此处，假定马尔可夫过程是正则的，即有,12,13,状态转移图和状态转移率矩阵,马尔可夫模型常使用状态转移图来描述系统的运行情况。,图1马尔可夫过程的状态转移图,修复（q）,故障（p）,1-p,1-q,S,F,14,图1所示为一个可修复系统的状态转移图，系统存在“正常（S)”和“故障（F)”两种状态。当出现故障时，系统将从“S”状态转移到“F”状态；一旦修复成功，系统将会由“F”状态转移到“S”状态。由于这两种状态出现的概率及其持续时间具有随机性，它们的转移规律只能按照某种概率转移。图1中p、q为状态的转移概率。显然，0p1,0q1。根据上述分析，还可以得到系统状态的转移率矩阵：,15,系统经过多次转移后，通常会达到一个与时间无关的稳定状态。此时，系统在状态转移过程中，在各状态逗留的概率不再发生变化。求解系统处于各种状态的稳态概率是研究离散事件系统特性的重要手段。,稳态概率及其求法,系统在各状态的稳定概率通常有以下两种解法：已知瞬态概率，求极限,式中Si（t）-系统i状态的瞬态概率；Ai-i状态的稳态概率。,16,同构法当系统达到稳定状态以后，各种状态将持续转移，但是每种状态出现的概率基本不变，从而形成一个稳定的状态空间。求解状态空间方程组，就可得到系统在各种状态的稳态概率。,通常，稳态概率空间的表达式不易求出，该解法适合于解决一些比较简单系统的稳态状态概率问题。,17,例1以图1所示模型为例，求解稳态概率。,图1马尔可夫过程的状态转移图,修复（q）,故障（p）,1-p,1-q,S（1）,F（2）,18,设系统处于正常状态的稳态概率为1和处于故障状态的稳态概率为2，则有,显然，前两个方程是线性相关的，可以删掉一个。解方程组得：,19,例2设任意相继的两天中，雨天转晴天的概率为1/3，晴天转雨天的概率为1/2，任一天晴或雨是互为逆事件。以0表示晴天状态，以1表示雨天状态，Xn表示第n天状态（0或1）。又已知5月1日为晴天，问5月3日为晴天，5月5日为雨天的概率各等于多少？,解：分析分析状态转移过程，求出系统状态转移率矩阵；确定某状态下的转移概率矩阵；求解。,20,晴转雨（1/2）,1-1/2,1-1/3,晴天,雨天,雨转晴（1/3）,状态转移图：,21,得到系统状态转移率矩阵为：,则5月2日状态转移概率矩阵为：,22,则5月3日状态转移概率矩阵为：,因此5月3日为晴天的概率为5/1