随机过程课程设计
《随机过程》
课程设计(论文)
题 目: 连续马尔科夫过程的转移
概率及应用
学 院: 理学院 专 业: 数学与应用数学 班 级: 数学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矩阵 ......................................................... - 3 - 3.3柯尔莫哥洛夫向后方程 ............................................ - 4 - 3.4柯尔莫哥洛夫向前方程 ............................................ - 4 - 第4章 马尔可夫过程研究的问题的分析 --------------------------------------------------------------- - 5 -
4.1连续参数随机游动问题 ............................................ - 5 - 第5章 计算结果及程序 ------------------------------------------------------------------------------------- - 6 - 第6章 结论和展望 ----------------------------------------------------------------------------------------- - 11 - 参考文献 ------------------------------------------------------------------------------------------------------- - 11 - 评 阅 书 ------------------------------------------------------------------------------------------------- - 12 -
随机过程 课程设计任务书
摘 要
马尔可夫过程(MarKov Process)是一个典型的随机过程。设X(t)是一随机过程,当过程在时刻t0所处的状态为已知时,时刻t(t t0)所处的状态与过程在t0时刻之前的状态无关,这个特性成为无后效性。
本文主要阐述连续马尔科夫过程的转移概率定义、性质及其应用,以及科尔莫哥洛夫向前、向后方程,Q矩阵。主要研究机器维修,排队,以及随机游动等实际问题,根据实际问题来求解微分方程。并用MATLAB,对其结果进行了合理性的分析,使得我们能更好的理解和应用连续马尔可夫过程,并能用柯尔莫哥洛夫向前向后方程,Q矩阵,MATLAB求解实际问题。
关键字 马尔科夫过程 转移概率 柯尔莫哥洛夫 微分方程数值求解 随机游动
连续马尔科夫过程的转移概率及其应用
第1章 绪论
1951年前后,伊藤清建立的随机微分方程的理论,为马尔可夫过程的研究开辟了新的道路。1954年前后, W.费勒将半群方法引入马尔可夫过程的研究。流形上的马尔可夫过程、马尔可夫向量场等都是正待深入研究的领域。
类重要的随机过程,它的原始模型马尔可夫链,由俄国数学家Α.Α.马尔可夫于1907年提出。人们在实际中常遇到具有下述特性的随机过程:在已知它目前的状态(现在)的条件下,它未来的演变(将来)不依赖于它以往的演变(过去)。这种已知“现在”的条件下,“将来”与“过去”独立的特性称为马尔可夫性,具有这种性质的随机过程叫做马尔可夫过程。荷花池中一只青蛙的跳跃是马尔可夫过程的一个形象化的例子。青蛙依照它瞬间或起的念头从一片荷叶上跳到另一片荷叶上,因为青蛙是没有记忆的,当现在所处的位置已知时,它下一步跳往何处和它以往走过的路径无关。如果将荷叶编号并用x0,x1,x2......分别表示青蛙最初处的荷叶号码及第一次、第二次、„„跳跃后所处的荷叶号码,那么{xn,n≥0} 就是马尔可夫过程。液体中微粒所作的布朗运动,传染病受感染的人数,原子核中一自由电子在电子层中的跳跃,人口增长过程等等都可视为马尔可夫过程。还有些过程(例如某些遗传过程)在一定条件下可以用马尔可夫过程来近似。
关于马尔可夫过程的理论研究,1931年Α.Η.柯尔莫哥洛夫发表了《概率论的解析方法》,首先将微分方程等分析方法用于这类过程,奠定了它的理论基础。1951年前后,伊藤清在P.莱维和C.H.伯恩斯坦等人工作的基础上,建立了随机微分方程的理论,为研究马尔可夫过程开辟了新的道路。1954年前后,W.弗勒将泛函分析中的半群方法引入马尔可夫过程的研究中,Ε.Б.登金(又译邓肯)等并赋予它概率意义(如特征算子等)。50年代初,角谷静夫和J.L.杜布等发现了布朗运动与偏微分方程论中狄利克雷问题的关系,后来G.A.亨特研究了相当一般的马尔可夫过程(亨特过程)与 位势的关系。目前,流形上的马尔可夫过程、马尔可夫场等都是正待深入研究的领域。
第2章 连续时间马尔可夫链基本理论
2.1定义
设随机过程{X(t),t≥0},状态空间I={0,1,2
},若对tn+1任意及非负整数
数
0≤t1
及非负整
p{X(tn+1)=in+1|X(t1)=i1,X(t2)=i2,
,X(tn)=in}=p{X(tn+1)=in+1|X(tn)=in}
i1,2
i有,,i
,则称{X(t),t≥0}为连续时间马尔可夫链。
2.2转移概率
在s时刻处于状态i,经过时间t后转移到状态j的概率
pij(s,t)=p{X(s+t)=j|X(s)=i}
定义.2
齐次转移概率pij(s,t)=pij(t) (与起始时刻s无关,只与时间间隔t有关)转移概率矩阵P(t)=pij(t),i,j∈I,t≥0
命题:若τi为过程在状态转移之前停留在状态i的时间,则对s, t≥0有
(1) p{τi>s+t|τi>s}=p{τi>t} (2) τi 服从指数分布
定理1 齐次马尔可夫过程的转移概率具有:
(1) pij(t)≥0;
∑p(t)=1;(j∈I)
(3) p(t+s)=∑p(t )p( s ) (k∈I)
(2)
ijij
ik
kj
正则性条件
lim(t)=1,i=j lim(t)=0,i≠j,(t→0)
定义3
(1)初始概率: pj=pj (0) = P{ X (0) = j}, j∈I (2)绝对概率: pj (t ) = P{ X (t ) = j}, j∈I , t≥0 (3)初始分布: p={pj,j∈I}
(4)绝对分布: p(t)={pj(t)j∈I}t≥0
定理2
齐次马尔可夫过程的绝对概率及有 限维概率分布具有下列性质: (1) pj (t)≥0 (2)
∑p(t)=1 (3) p (t )=∑pp(t)
jj
iij
(4) pj(t +τ)=∑pi(t)pij(τ) (5)
P{X(t1)=i1
X(tn)=in}
pin-iin(tn-tn-1)i∈I
=∑pipii1(t1)pi1i2(t2-t1)
第3章 柯尔莫哥洛夫微分方程
3.1跳跃强度
状态转移概率
⎧X(t2)=j⎪⎫⎪p⎨⎬ ⎪⎩Xt1=i⎪⎭
它满足
⎧⎧⎪X(t2)=j⎫⎪⎪X(t2)=j⎫⎪
p⎨≥0p ,⎬⎨⎬=1 ∑j∈I⎪⎪⎩Xt1=i⎪⎭⎩Xt1=i⎪⎭
齐次马尔可夫过程的状态转移概率
pij(τ) 满足:
pij(τ)≥0,∑pij(τ)=1
跳跃强度
j∈I
pij(∆t)=pij(0)+qij⋅∆t+0∆t=σij+qij⋅∆t+0(∆t)
qij=lim
其中
pij(∆t)-pij(0)
∆t
∆t→0
pij(0)=σij=
{
1(i=j)
0(i≠j)
称为参数连续状态离散齐次马尔可夫过程的跳跃强度 当i≠j时,qij=lim
pij(∆t)∆t
∆t→0
当i=j时, qij=lim
pij(∆t)-1∆t
∆t→0
3.2 Q矩阵
⎡q00⎢q10
把矩阵Q=⎢
⎢⎢⎣qn0
q01q11qn1
q0n⎤q1n⎥⎥叫 ⎥⎥qnn⎦
马氏过程的速率矩阵,简称Q矩阵。
但考虑到密度矩阵Q=(qij),是由P(t)=(pij)的导数组成 即
Q=P'(0)
qij=(pij(t))'
跳跃强度的性质
t=0
∑q
j∈I
ij
=0
3.3柯尔莫哥洛夫向后方程
假设∑qik=qii,则对一切i, j及t ≥0,有p'ij(t)=∑qikpkj(t)-qiipij(t)=QiPj
k≠i
k≠i
3.4柯尔莫哥洛夫向前方程
在适当的正则条件下有p'ij(t)=∑pik(t)qkj-pij(t)qjj
★ 向后方程的矩阵形式:P(t)=QP(t) ①
'
k≠j
★ 向前方程的矩阵形式:P'(t)=P(t)Q ② 其中Q矩阵为
⎡-q00⎢qQ=⎢10
⎢q20⎢⎣
q01q02
-q11q12q21-q22
⎤⎥⎥ ⎥⎥⎦
矩阵p'(t)的元素为矩阵p(t)的元素的导数,而
⎡p00(t)⎢
p(t)P(t)=⎢10
⎢p20(t)⎢⎣
p01(t)p11(t)p21(t)
p02(t)p12(t)p22(t)
⎤⎥⎥ ⎥⎥⎦
这样,连续时间马尔科夫链的转移概率的求解问题就是矩阵微分方程的求解问题,其转移概率有其转移速率矩阵Q决定。
若Q是一个有限维矩阵,则式①和式②的解为
P(t)=eQt=∑
j=0
∞
(Qt)
j!
j
定理3齐次马尔可夫过程在t时刻处于状 态j∈I的绝对概率pj(t) 满足方
程:
p'j(t)=-pj(t)qj+j∑p(tk)q
k≠j
kj
第4章 马尔可夫过程研究的问题的分析
4.1连续参数随机游动问题
有限图上的随机游动(即有限马尔可夫链)近一二十年来在近似算法设计的重要应用,使它受到越来越广泛的关注。这时算法的有效性大部分依赖于所设计随机游动的性能好坏,而随机游动的性能主要由它的几个重要的参数来决定,如平均首达时间,平均覆盖时间,收敛速度等。
例 设在[1,5]的线段上有一个质点作随机游动,此质点只能停留在1,2,3,4,5,诸点上。质点任何时刻都可能发生移动,其移动的规则是:
(t+∆t)(1)若在时刻t 质点位于2,3,4,中的一点,,则在中以概率∆t+o(∆t)
向右移动一格,以概率2∆t+o(∆t)向左移动一格;
(t+∆t)(2)若在时刻t 质点位于1,则在中以概率∆t+o(∆t)向右移动一格;
(3)若在时刻t 质点位于5,则以概率2∆t+o(∆t)向左移动一格;
(t+∆t)(4)在发生其他移动的概率是o(∆t)。
求Pi j(t)满足的微分方程。
转移速率矩阵
Q=⎡⎣qij⎤⎦
状态转移概率矩阵 p(τ)=⎡⎣pij(τ)⎤⎦
从给定状态转移到任意状态的转移概率矩阵
记作pi(τ),为 p(τ)=⎡⎣pij(τ)⎤⎦的第i行的行矢量 从任意状态转移到特定状态的转移概率矩阵
记作sj(τ),为 p(τ)=⎡⎣pij(τ)⎤⎦的第j行的列矢量 t时刻系统状态的概率分布律矩阵 W(t)=⎡⎣wi(t)⎤⎦=⎡⎣w0(t),w1(t),
wk(t),
⎤⎦
第5章 计算结果及程序
解:写出马尔科夫过程的Q 矩阵,则相应的Q 矩阵是,
⎡-11000⎤⎢2-3100⎥⎢⎥Q=⎢02-310⎥ ⎢⎥002-31⎢⎥⎢⎣0002-2⎥⎦
根据柯尔莫哥洛夫-费勒前进方程,可以列出Pi j(t)满足的微分方程:
dpij(t)dt
=∑pik(t)qkj,i,j∈I
k≠j
1i=j
初始条件:pij(0)=σij=0((i≠j))
{
根据柯尔莫哥洛夫-费勒后退方程,可以列出Pi j(t) 满足的微分方程:
dpij(t)dt
=∑qik(t)pkj,i,j∈I
k≠j
1i=j初始条件:pij(0)=σij=0((i≠j))
{
程序
>> [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/124
-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/124
-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
评 阅 书