《随机过程》
课程设计(论文)
题目: 连续马尔科夫过程的转移
概率及应用
学院:理学院
专业:数学与应用数学
班级:数学09-2班
学生姓名:姜德月
学生学号:2009026249
指导教师:蔡吉花
2011 年12 月20 日
目录
课程设计任务书--------------------------------------------------------------- I 摘要----------------------------------------------------------------------- II 第1章绪论-------------------------------------------------------------- - 1 - 第2章连续时间马尔可夫链基本理论----------------------------------------- - 2 -
2.1定义.................................................................................................................................... - 2 -
2.2转移概率 ........................................................................................................................... - 2 -第3章柯尔莫哥洛夫微分方程----------------------------------------------- - 3 -
3.1跳跃强度 ........................................................................................................................... - 3 -
3.2 Q矩阵 ............................................................................................................................ - 4 -
3.3柯尔莫哥洛夫向后方程 .................................................................................................. - 4 -
3.4柯尔莫哥洛夫向前方程 .................................................................................................. - 5 -第4章马尔可夫过程研究的问题的分析--------------------------------------- - 5 -
4.1连续参数随机游动问题 .................................................................................................. - 5 -第5章计算结果及程序---------------------------------------------------- - 6 - 第6章结论和展望------------------------------------------------------- - 16 - 参考文献----------------------------------------------------------------- - 16 - 评阅书------------------------------------------------------------- - 17 -
随机过程课程设计任务书
摘 要
马尔可夫过程(MarKov Process)是一个典型的随机过程。设()X t 是一随机过程,当过程在时刻0t 所处的状态为已知时,时刻0()t t t 所处的状态与过程在0t 时刻之前的状态无关,这个特性成为无后效性。
本文主要阐述连续马尔科夫过程的转移概率定义、性质及其应用,以及科尔莫哥洛夫向前、向后方程,Q 矩阵。主要研究机器维修,排队,以及随机游动等实际问题,根据实际问题来求解微分方程。并用MATLAB ,对其结果进行了合理性的分析,使得我们能更好的理解和应用连续马尔可夫过程,并能用柯尔莫哥洛夫向前向后方程,Q 矩阵,MATLAB 求解实际问题。
关键字 马尔科夫过程 转移概率 柯尔莫哥洛夫 微分方程数值求解 随机游动
连续马尔科夫过程的转移概率及其应用
第1章 绪论
1951年前后,伊藤清建立的随机微分方程的理论,为马尔可夫过程的研究开辟了新的道路。1954年前后, W.费勒将半群方法引入马尔可夫过程的研究。流形上的马尔可夫过程、马尔可夫向量场等都是正待深入研究的领域。
类重要的随机过程,它的原始模型马尔可夫链,由俄国数学家Α.Α.马尔可夫于1907年提出。人们在实际中常遇到具有下述特性的随机过程:在已知它目前的状态(现在)的条件下,它未来的演变(将来)不依赖于它以往的演变(过去)。这种已知“现在”的条件下,“将来”与“过去”独立的特性称为马尔可夫性,具有这种性质的随机过程叫做马尔可夫过程。荷花池中一只青蛙的跳跃是马尔可夫过程的一个形象化的例子。青蛙依照它瞬间或起的念头从一片荷叶上跳到另一片荷叶上,因为青蛙是没有记忆的,当现在所处的位置已知时,它下一步跳往何处和它以往走过的路径无关。如果将荷叶编号并用012,,......x x x 分别表示青蛙最初处的荷叶号码及第一次、第二次、……跳跃后所处的荷叶号码,那么{},0n x n ≥ 就是马尔可夫过程。液体中微粒所作的布朗运动,传染病受感染的人数,原子核中一自由电子在电子层中的跳跃,人口增长过程等等都可视为马尔可夫过程。还有些过程(例如某些遗传过程)在一定条件下可以用马尔可夫过程来近似。
关于马尔可夫过程的理论研究,1931年Α.Η.柯尔莫哥洛夫发表了《概
率论的解析方法》,首先将微分方程等分析方法用于这类过程,奠定了它的理论基础。1951年前后,伊藤清在P.莱维和C.H.伯恩斯坦等人工作的基础上,建立了随机微分方程的理论,为研究马尔可夫过程开辟了新的道路。1954年前后,W.弗勒将泛函分析中的半群方法引入马尔可夫过程的研究中,Ε.Б.登金(又译邓肯)等并赋予它概率意义(如特征算子等)。50年代初,角谷静夫和J.L.杜布等发现了布朗运动与偏微分方程论中狄利克雷问题的关系,后来G.A.亨特研究了相当一般的马尔可夫过程(亨特过程)与 位势的关系。目前,流形上的马尔可夫过程、马尔可夫场等都是正待深入研究的领域。
第2章 连续时间马尔可夫链基本理论
2.1定义
设随机过程(){},0X t t ≥,状态空间{}I=0,1,2L ,若对1t n +任意及非负整数
121
0t t t n -≤<<及非负整数
12n+1
i ,i ,,i L 有
()()()(){}111122|,,,n n n n p X t i X t i X t i X t i ++=====L ()(){}11|n n n n p X t i X t i ++==,则称(){},0X t t ≥为连续时间马尔可夫链。
2.2转移概率
在s 时刻处于状态i ,经过时间t 后转移到状态j 的概率
()()(){},|ij p s t p X s t j X s i =+==
定义.2
齐次转移概率()(),ij ij p s t p t = (与起始时刻s 无关,只与时间间隔t 有关)转移概率矩阵()(),,,0ij P t p t i j I t =∈≥
命题:若τi 为过程在状态转移之前停留在状态i 的时间,则对s, t ≥0有
(1) {}{}|?i i i p s t s p t τττ>+>=> (2) τi 服从指数分布
定理1 齐次马尔可夫过程的转移概率具有:
(1) ()ij p 0t ≥;
(2)
()()ij
p 1;t j I =∈∑
(3) ()()()ij p t s (k I)ik kj
t s p p +=∈∑
正则性条件
()lim 1,t i j == ()()lim 0,,0t i j t =≠→
定义3
(1)初始概率: ()(){} 0 P X 0 j , j I j j p p ===∈ (2)绝对概率: ()(){} t P X t j , j I , t 0?j p ==∈≥ (3)初始分布: {},j p p j I =∈
(4)绝对分布: ()(){}0j p t p t j I t =∈≥
定理2
齐次马尔可夫过程的绝对概率及有 限维概率分布具有下列性质:
(1) () t 0j p ≥
(2)
()1j p t =∑ (3) ()() t j
i ij
p p p t =∑ (4) ()(t )()j
i
ij
p p t p ττ+=∑
(5)
()(){}
()()()112111211P t p t p n i n n n i ii i i i i n n X t i X t i p p t t t i I
--===--∈∑L L
第3章 柯尔莫哥洛夫微分方程
3.1跳跃强度
状态转移概率
()()21X t j p X t i ??=????=????
它满足
()()210X t j p X t i ??=??≥??=???? ,()()211j I X t j p X t i ∈??=??
=??=????
∑
齐次马尔可夫过程的状态转移概率
()ij p τ 满足:
()()0,1ij ij j I
p p ττ∈≥=∑
跳跃强度
()()()000ij ij ij ij ij p t p q t t q t t σ?=+??+?=+??+?
()()
0lim
ij ij ij t p t p q t
?→?-=?
其中
()(
)
(){100i j ij ij i j p σ=≠==
称为参数连续状态离散齐次马尔可夫过程的跳跃强度 当i j ≠时,()0
lim
ij ij t p t q t
?→?=?
当i=j 时, ()0
1lim
ij ij t p t q t
?→?-=?
3.2 Q 矩阵
把矩阵0001010
1110
1q =n n n n nn q q q
q q Q q q q ????????????
L L L L L L L
叫 马氏过程的速率矩阵,简称Q 矩阵。
但考虑到密度矩阵()ij Q q =,是由()()ij P t p =的导数组成 即
(0)Q P '=
'
(())ij ij t q p t ==
跳跃强度的性质
0ij
j I
q
∈=∑
3.3柯尔莫哥洛夫向后方程
假设ik ii k i
q q ≠=∑,则对一切i, j 及t ≥0,有()()()'ij ik kj ii ij i j k i
p t q p t q p t Q P ≠=-=∑
3.4柯尔莫哥洛夫向前方程
在适当的正则条件下有()()()'ij ik kj ij jj k j
p t p t q p t q ≠=-∑
★ 向后方程的矩阵形式:()()'
P t QP t = ①
★ 向前方程的矩阵形式:()()'P t P t Q = ② 其中Q 矩阵为
00010210
1112202122q q q q q q Q q q q -????-??=??-????
L L L L
L
L
L 矩阵()'p t 的元素为矩阵()p t 的元素的导数,而
()()()()()()()()()()00010210
1112202122=p t p t p t p t p t p t P t p t p t p t ??
?
?
??
????
??
L L L L
L
L L 这样,连续时间马尔科夫链的转移概率的求解问题就是矩阵微分方程的求解问题,其转移概率有其转移速率矩阵Q 决定。
若Q 是一个有限维矩阵,则式①和式②的解为
()()0
!
j
Qt
j Qt P t e
j ∞===∑
定理3齐次马尔可夫过程在t 时刻处于状 态j I ∈的绝对概率()j p t 满足方
程:
()()()'j j jj k kj k j
p t p t q p t q ≠=-+∑
第4章 马尔可夫过程研究的问题的分析
4.1连续参数随机游动问题
有限图上的随机游动(即有限马尔可夫链)近一二十年来在近似算法设计的重要应用,使它受到越来越广泛的关注。这时算法的有效性大部分依赖于所设计随机游动的性能好坏,而随机游动的性能主要由它的几个重要的参数来决定,如平均首达时间,平均覆盖时间,收敛速度等。
例 设在[]1,5的线段上有一个质点作随机游动,此质点只能停留在1,2,3,4,5,诸
点上。质点任何时刻都可能发生移动,其移动的规则是:
(1)若在时刻t 质点位于2,3,4,中的一点,,则在t t +?()
中以概率()t o t ?+? 向右移动一格,以概率()2t o t ?+?向左移动一格;
(2)若在时刻t 质点位于1,则在t t +?()中以概率()t o t ?+?向右移动一格; (3)若在时刻t 质点位于5,则以概率()2t o t ?+?向左移动一格; (4)在t t +?()发生其他移动的概率是()o t ?。 求() j i P t 满足的微分方程。
转移速率矩阵
ij Q q ??=??
状态转移概率矩阵 ()()ij p p ττ??=??
从给定状态转移到任意状态的转移概率矩阵
记作()i p τ,为 ()()ij p p ττ??=??的第i 行的行矢量 从任意状态转移到特定状态的转移概率矩阵
记作()j s τ,为 ()()ij p p ττ??=??的第j 行的列矢量 t 时刻系统状态的概率分布律矩阵
()()()()()01,,,i k W t w t w t w t w t ==????????L L
第5章 计算结果及程序
解:写出马尔科夫过程的Q 矩阵,则相应的Q 矩阵是,
1100023100=02310002310002-2Q -??
??-????-??-??????
根据柯尔莫哥洛夫-费勒前进方程,可以列出() j i P t 满足的微分方程:
()(),,ij ik kj k j
dp t p t q i j I dt
≠=∈∑
初始条件:()()(){
100i j
ij ij i j p σ=≠==
根据柯尔莫哥洛夫-费勒后退方程,可以列出() j i P t 满足的微分方程:
()(),,ij ik kj k j
dp t q t p i j I dt
≠=∈∑
初始条件:()()(){
100i j ij ij i j p σ=≠==
程序
>> [x,y,z,m,n]=dsolve('Dx=-1*x+2*y,Dy=1*x-(1+2)*y+2*z,Dz=1*y-(1+2)
*z+2*m,Dm=1*z-(1+2)*m+2*n,Dn=1*m-2*n','x(0)=1,y(0)=0,z(0)=0,m(0)=0,n(0) =0','t') x =
-1/4*(15/124-3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*exp((-3-1/2*10^
(1/2)-1/2*2^(1/2))*t)+2/31-1/4*(3/155*10^(1/2)+15/124-3/620*5^(1/2)
+1/62*2^(1/2))*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)-1/4*(1/62*2^(1/2)
+15/124-3/155*10^(1/2)+3/620*5^(1/2))*exp((-3-1/2*10^(1/2)+1/2*2^(1/2 ))
*t)-1/4*(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)*exp((-
3+1/2*10^(1/2)-1/2*2^(1/2))*t)+1/8*(1/62*2^(1/2)+15/124-3/155*10^(1/2)
+3/620*5^(1/2))*20^(1/2)*exp((-3-1/2*10^(1/2)+1/2*2^(1/2))*t)+1/8*
(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)*20^(1/2)*exp((-
3+1/2*10^(1/2)-1/2*2^(1/2))*t)-1/8*(3/155*10^(1/2)+15/124-3/620*5^(1/2 )
+1/62*2^(1/2))*20^(1/2)*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)-1/8*(15/12 4
-3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*20^(1/2)*exp((-3-1/2*10^
(1/2)-1/2*2^(1/2))*t)-1/4*(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)
+15/124)*exp((-3+1/2*10^(1/2)-1/2*2^(1/2))*t)*2^(1/2)+1/4*(1/62*2^(1/2)
+15/124-3/155*10^(1/2)+3/620*5^(1/2))*exp((-3-1/2*10^(1/2)+1/2*2^(1/2 ))
*t)*2^(1/2)-1/4*(15/124-3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*exp
((-3-1/2*10^(1/2)-1/2*2^(1/2))*t)*2^(1/2)+1/4*(3/155*10^(1/2)+15/124-
3/620*5^(1/2)+1/62*2^(1/2))*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)*2^(1/2)
y =
1/31+1/4*(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)*exp((-
3+1/2*10^(1/2)-1/2*2^(1/2))*t)*2^(1/2)-1/4*(1/62*2^(1/2)+15/124-
3/155*10^(1/2)+3/620*5^(1/2))*exp((-3-1/2*10^(1/2)+1/2*2^(1/2))*t)*2^
(1/2)+1/4*(15/124-3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*exp((-3-
1/2*10^(1/2)-1/2*2^(1/2))*t)*2^(1/2)-1/4*(3/155*10^(1/2)+15/124-3/620*5 ^
(1/2)+1/62*2^(1/2))*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)*2^(1/2)
z =
16/31+(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)*exp((-3+1/2* 10^
(1/2)-1/2*2^(1/2))*t)+(1/62*2^(1/2)+15/124-3/155*10^(1/2)+3/620*5^(1/2) )
*exp((-3-1/2*10^(1/2)+1/2*2^(1/2))*t)+(3/155*10^(1/2)+15/124-3/620*5^
(1/2)+1/62*2^(1/2))*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)+(15/124-
3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*exp((-3-1/2*10^(1/2)-1/2*2^
(1/2))*t)
m =
-(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)*exp((-3+1/2*10^(1 /2)
-1/2*2^(1/2))*t)+1/4*(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)
*exp((-3+1/2*10^(1/2)-1/2*2^(1/2))*t)*10^(1/2)-1/4*(3/620*5^(1/2)-
1/62*2^(1/2)+3/155*10^(1/2)+15/124)*exp((-3+1/2*10^(1/2)-1/2*2^(1/2))* t)
*2^(1/2)-(1/62*2^(1/2)+15/124-3/155*10^(1/2)+3/620*5^(1/2))*exp((-3-
1/2*10^(1/2)+1/2*2^(1/2))*t)-1/4*(1/62*2^(1/2)+15/124-3/155*10^(1/2)
+3/620*5^(1/2))*exp((-3-1/2*10^(1/2)+1/2*2^(1/2))*t)*10^(1/2)+1/4*
(1/62*2^(1/2)+15/124-3/155*10^(1/2)+3/620*5^(1/2))*exp((-3-1/2*10^(1/2 )
+1/2*2^(1/2))*t)*2^(1/2)-(3/155*10^(1/2)+15/124-3/620*5^(1/2)+1/62*2^
(1/2))*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)+1/4*(3/155*10^(1/2)+15/124-
3/620*5^(1/2)+1/62*2^(1/2))*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)*10^ (1/2)+1/4*(3/155*10^(1/2)+15/124-3/620*5^(1/2)+1/62*2^(1/2))*exp((-
3+1/2*10^(1/2)+1/2*2^(1/2))*t)*2^(1/2)-(15/124-3/620*5^(1/2)-1/62*2^ (1/2)-3/155*10^(1/2))*exp((-3-1/2*10^(1/2)-1/2*2^(1/2))*t)-1/4*(15/124- 3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*exp((-3-1/2*10^(1/2)-1/2*2^ (1/2))*t)*10^(1/2)-1/4*(15/124-3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^
(1/2))*exp((-3-1/2*10^(1/2)-1/2*2^(1/2))*t)*2^(1/2)+8/31
n =
1/4*(15/124-3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*exp((-3-1/2*10^ (1/2)-1/2*2^(1/2))*t)+4/31+1/4*(3/155*10^(1/2)+15/124-3/620*5^(1/2)
+1/62*2^(1/2))*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)+1/4*(1/62*2^(1/2)
+15/124-3/155*10^(1/2)+3/620*5^(1/2))*exp((-3-1/2*10^(1/2)+1/2*2^(1/2 ))
*t)+1/4*(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)*exp((-
3+1/2*10^(1/2)-1/2*2^(1/2))*t)-1/8*(1/62*2^(1/2)+15/124-3/155*10^(1/2)
+3/620*5^(1/2))*20^(1/2)*exp((-3-1/2*10^(1/2)+1/2*2^(1/2))*t)-1/8*
(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)*20^(1/2)*exp((-
3+1/2*10^(1/2)-1/2*2^(1/2))*t)+1/8*(3/155*10^(1/2)+15/124-3/620*5^(1/2 )
+1/62*2^(1/2))*20^(1/2)*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)+1/8*(15/12 4
-3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*20^(1/2)*exp((-3-1/2*10^
(1/2)-1/2*2^(1/2))*t)+1/4*(1/62*2^(1/2)+15/124-3/155*10^(1/2)+3/620*5^
(1/2))*exp((-3-1/2*10^(1/2)+1/2*2^(1/2))*t)*10^(1/2)-1/4*(3/620*5^(1/2)-
1/62*2^(1/2)+3/155*10^(1/2)+15/124)*exp((-3+1/2*10^(1/2)-1/2*2^(1/2))* t)
*10^(1/2)+1/4*(3/620*5^(1/2)-1/62*2^(1/2)+3/155*10^(1/2)+15/124)*exp(( -
3+1/2*10^(1/2)-1/2*2^(1/2))*t)*2^(1/2)-1/4*(1/62*2^(1/2)+15/124-
3/155*10^(1/2)+3/620*5^(1/2))*exp((-3-1/2*10^(1/2)+1/2*2^(1/2))*t)*2^ (1/2)+1/4*(15/124-3/620*5^(1/2)-1/62*2^(1/2)-3/155*10^(1/2))*exp((-3-
1/2*10^(1/2)-1/2*2^(1/2))*t)*10^(1/2)+1/4*(15/124-3/620*5^(1/2)-1/62*2^ (1/2)-3/155*10^(1/2))*exp((-3-1/2*10^(1/2)-1/2*2^(1/2))*t)*2^(1/2)-1/4*
(3/155*10^(1/2)+15/124-3/620*5^(1/2)+1/62*2^(1/2))*exp((-3+1/2*10^(1/ 2)
+1/2*2^(1/2))*t)*10^(1/2)-1/4*(3/155*10^(1/2)+15/124-3/620*5^(1/2)
+1/62*2^(1/2))*exp((-3+1/2*10^(1/2)+1/2*2^(1/2))*t)*2^(1/2)
第6章结论和展望
从上面的例子中可以看出利用连续马尔可夫过程求解以及matlab使用的重要性,通过这个例子,我们可以更好的理解马尔可夫过程,理解柯尔莫哥洛夫方程,同时知道怎样求解一些实际问题,例如:排队问题,机器维修问题、零件寿命、随机游动等问题。
马尔可夫链近一二十年来在近似算法设计的重要应用,使它受到越来越广泛的关注。以后将会更加的普及到现实社会当中,来帮助我们解决更多的实际问题。
参考文献
《应用随机过程》,钱敏平,龚光鲁,北京大学出版社,1998.
《随机过程论》,钱敏平高等教育出版社2000
《应用随机过程》,林元烈清华大学出版社2002
《随机过程》,刘次华华中科技大学出版社2008
《Matlab在时间序列分析中的应用》张善文雷英杰冯有前
西安电子科技大学出版社2007