马尔可夫过程ppt课件
2) P(ij t) 1 jE
3) P(ik u)• P(kj v)=P(ij u+v) kE
若令P(j t)=P{X(t)=j},jE。它表示t时刻系统处于j状态的概率,则有
P(j t)= P(k 0)• P(kj t) kE
13
Hale Waihona Puke 状态转移图和状态转移率矩阵 马尔可夫模型常使用状态转移图来描述系统的运行情况。
其中,X(ti)=ti表示处于ti(i=1,2,...n)时刻的状态, 则称{X(t),t≥0}为离散状态空间E上的连续时间马尔可 夫过程。
11
转移概率函数
若对任意t,u≥0,均有
P{X(t+u)=j|X(u)=i}=Pij(t) i,j∊E 与u无关,则称马尔可夫过程{X(t),t≥0}是齐次的。即Pij(t) 只与时间差t有关,而与时间起点u的位置无关。一般如不作
参数集T=[0, ∞],状态空间E={整数}
(3)时间离散、状态连续的马尔可夫过程——马尔可夫序列。 参数集T= {0,1,2,…},状态空间E= (-∞, +∞)
(4)时间连续、状态连续的马尔可夫过程。 参数集T= [0, ∞],状态空间E= (-∞, +∞)
7
表1 马尔可夫过程的分类
分类
名称
E
特别说明,马尔可夫过程均假设是齐次的。
对固定i,j∊E,函数Pij(t)称为转移概率函数。 P(T)=(Pij(t))称为转移概率矩阵。 此处,假定马尔可夫过程是正则的,即有
lim t0
Pi, j (t) ij
1 0
(i j) (i j)
12
转移概率函数具有以下性质: 1)P(ij t) 0
有随机性,它们的转移规律只能按照某种概率转移。
图1中p、q为状态的转移概率。显然,0< p< 1,0< q< 1。 根据上述分析,还可以得到系统状态的转移率矩阵:
A
1
q
p
p
1
q
15
稳态概率及其求法
系统经过多次转移后,通常会达到一个与时间 无关的稳定状态。此时,系统在状态转移过程中, 在各状态逗留的概率不再发生变化。求解系统处于 各种状态的稳态概率是研究离散事件系统特性的重 要手段。
故障(p)
S
1-p
F
1-q
修复(q)
图1 马尔可夫过程的状态转移图 14
图1所示为一个可修复系统的状态转移图,系统
存在“正常(S)”和“故障(F)”两种状态。当出
现故障时,系统将从“S”状态转移到“F”状态;
一旦修复成功,系统将会由“F”状态转移到“S”
状态。由于这两种状态出现的概率及其持续时间具
3
马尔可夫过程定义
马尔可夫特性 如果一个随机过程的概率分布函数具有以下特性
P{X(t) ≤xn| X(tn) = xn, X(tn-1) = xn-1, …, X(t0) = x0} = P{X(t) ≤ x| X(tn) = xn},t﹥tn﹥tn-1﹥...t0
则称该随机过程具有马尔可夫特性。 一个具有马尔可夫特性的随机过程被称为马尔可 夫过程。
T
离散
( n=0,1,2,...,n)
离散
马尔可夫链
连续
马尔可夫序列
连续
(
可列马尔可夫过程 马尔可夫过程
n=0,1,2,...,n)
8
马尔可夫特性要求系统处于任何状态的时间分布具 有无记忆性。
对于连续型随机变量X,满足无记忆特性的概率分布函数为: P{X≥t+τ|X≥t}=P{X≥τ}
它的密度函数为指数分布 f(x)=αe-αx
马尔可夫过程
神和尧
1
2
马尔可夫过程简介
一类随机过程(数学基础是随机过程理论)。 原始模型马尔可夫链,由俄国数学家A.A.马尔可夫 于1907年提出。 该过程具有如下特性:在已知目前状态 (现在) 的条件下,它未来的演变 (将来)不依赖于它以往 的演变 ( 过去 ) 。 ④例如森林中动物头数的变化构成——马尔可夫过 程 。在现实世界中,有很多过程都是马尔可夫过程, 如液体中微粒所作的布朗运动、传染病受感染的人 数、车站的候车人数等,都可视为马尔可夫过程。
无记忆性要求在连续时间马尔科夫链状态的驻留时间为 服从指数分布的随机变量。同样的,对于离散时间马尔科 夫链,驻留时间必定是满足几何分布的随机变量。 以s表示随机过程在一个状态i的驻留时间,则有
P{s=i}=pi-1(1-p)(i=1,2,3,...)
9
驻留时间是检验随机过程是否属于马尔可夫过程的 重要标志。
检验一个随机过程是否满足马尔可夫特性; 状态驻留时间是否是无记忆的; 过程从一个状态到另一个状态的概率是否仅依赖 于要离开的状态和目的状态。
10
马尔可夫过程的形式化定义为:
设{X(t),t≥0}是取值为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-1} i1,i,2,...in∊E
5
马尔可夫特性的直观解释为:
在给定t时刻随机过程的状态为Xn或xn,则该过 程的后续状态及其出现的概率与t之前的状态无关。 也就是说,过程当前的状态包括了过程所有的历史 信息,该过程的进一步发展完全由当前状态所决定, 与当前状态之前的历史无关,这种性质也称为无后 效性或无记忆性。
此特性也可以理解为:随机过程Xn在“现在” 状态已知的条件下,过程“将来”的情况与“过去” 无关。或者说,过去只影响现在,而不影响将来。
P{将来|现在、过去}=P{将来|现在}
6
马尔可夫过程分类
按其状态空间E和时间参数集T是连续还是离散可分成四类:
(1)时间离散、状态离散的马尔可夫过程——马尔可夫链。 参数集T={0,1,2,…},状态空间E={整数}
(2)时间连续、状态离散的马尔可夫过程——可列马尔可夫过 程、连续参数马尔可夫链。
离散状态空间的马尔可夫过程也称为马尔可夫链。
4
值得指出的是,马尔可夫链既可以是连续时间的, 也可以是离散时间的,它取决于系统参数的设定。
以离散时间的马尔可夫链为例,其定义为:设一个离散 的随机序列Xn(n=1,2,....,N),若它满足 P{Xn+1=xn+1|Xn=xn,Xn-1=xn-1,...,X0=x0}=P{Xn+1=xn+1|Xn=xn} 则称之为离散时间马尔可夫链。