北大随机过程课件：第-3-章-第-2-讲-马尔可夫过程

马尔可夫过程¾1马尔可夫过程概论61.1马尔可夫过程处于某个状态的概率61.2马尔可夫过程的状态转移概率61.3参数连续状态离散马尔可夫过程的状态转移的切普曼-柯尔莫哥洛夫方程切普曼-柯尔莫哥洛夫方程齐次切普曼-柯尔莫哥洛夫方程转移概率分布函数、转移概率密度函数61.4马尔可夫过程状态瞬时转移的跳跃率函数和跳跃条件分布函数瞬时转移概率分布函数61.5确定马尔可夫过程Q矩阵跳跃强度、转移概率Q矩阵¾2参数连续状态离散马尔可夫过程的前进方程和后退方程柯尔莫哥洛夫-费勒前进方程（利用Q矩阵可以导出、转移概率的微分方程）福克-普朗克方程（状态概率的微分方程）柯尔莫哥洛夫-费勒后退方程（利用Q矩阵可以导出、转移概率的微分方程）¾3典型例题排队问题、机器维修问题、随机游动问题的分析方法¾4马尔可夫过程的渐进特性稳态分布存在的条件和性质稳态分布求解¾5马尔可夫过程的研究1概论1.1定义及性质1.2状态转移概率1.3齐次马尔可夫过程的状态转移概率1.5跳跃强度、转移概率Q矩阵2前进方程和后退方程2.1切普曼-柯尔莫哥洛夫方程2.2柯尔莫哥洛夫-费勒前进方程2.2福克-普朗克方程2.3柯尔莫哥洛夫-费勒后退方程3典型的马尔可夫过程举例例1例2例3例4，随机游动4马尔可夫过程的渐进特性4.1引理14.2定理24.3定理5马尔可夫过程的研究6关于负指数分布的补充说明：1概论1.1定义：马尔可夫过程()tξ：参数域为T，连续参数域。以下分析中假定[0,)T=∞；状态空间为I，离散状态。以下分析中取{0,1,2,}I=；对于Tttttmm∈+121，若在12mtttT∈这些时刻观察到随机过程的值是12,,miii，则1mmttT+∈时刻的条件概率满足:{}{}1111()/(),,()()/(),mmmmmmPtjtitiPtjtijIξξξξξ++======∈则称这类随机过程为具有马尔可夫性质的随机过程或马尔可夫过程。1.2定义：齐次马尔可夫过程对于马尔可夫过程()tξ，如果转移概率{}21()/()Ptjtiξξ==只是时间差12tt−=τ的函数,这类马尔可夫过程称为齐次马尔可夫过程。1.３性质马尔可夫过程具有过程的无后效性；参数连续状态离散的马尔可夫过程的条件转移概率为：{}{}212112()/()0()/(),,PtjtttPtjtittijIξξξξ′′=≤≤===≤∈马尔可夫过程的有限维联合分布律可以用转移概率来表示{}{}{}{}32132211123(),(),()()/()()/()(),,,PtktjtiPtktjPtjtiPtitttijkIξξξξξξξξ=========≤≤∈马尔可夫过程的有限维条件分布律可以用转移概率来表示1.4跳跃强度状态转移概率{}21()/()Ptjtiξξ==状态转移概率满足：{}0)(/)(12≥==itjtPξξ{}1)(/)(12===∑∈IjitjtPξξ齐次马尔可夫过程的状态转移概率：)(τjiP满足：0)(≥τjiP，1)(=∑∈IjjiPτ跳跃强度()(0)0()0()ijijijijijPtPqttqttδΔ=+⋅Δ+Δ=+⋅Δ+Δ()(0)limijijijtoPtPqtΔ→Δ−=Δ其中1(0)0ijijijPijδ=⎧==⎨≠⎩称ijq为参数连续状态离散齐次马尔可夫过程的跳跃强度当ji≠时，ttPqijotjiΔΔ=→Δ)(lim当ji=时，ttPqijotijΔ−Δ=→Δ1)(lim跳跃强度的性质：0ijjq=∑转移率矩阵（跳跃强度矩阵）：称Q={qij}为过程的转移率矩阵；1.5马尔可夫过程研究的问题马尔可夫过程的描述：转移率矩阵：ijQq⎡⎤=⎣⎦状态转移概率矩阵：()()ijPττ⎡⎤=⎣⎦P从特定状态转移到任意状态的转移概率矩阵：记作()iτp，为()()ijPττ⎡⎤=⎣⎦P的第i行的行矢量从任意状态转移到特定状态的转移概率矩阵：记作()jτs，为()()ijPττ⎡⎤=⎣⎦P的第j行的列矢量t时刻系统状态的概率分布律矩阵：[][]01()()(),(),(),iktwtwtwtwt==w从实际物理问题，确定马尔可夫过程描述，相应的Q矩阵根据Q矩阵，确定某一时刻在各个状态上的概率分布；根据Q矩阵，确定经过一段时间的状态转移概率；渐进分析：确定当∞→t时，在各个状态上的概率分布；典型问题：机器维修问题设某机器的正常工作时间是一负指数分布的随机变量，平均正常工作时间为1/λ，它损坏后的修复时间也是一个负指数分布的随机变量，它的平均修复时间为1/μ。如机器在t=0时是正常工作的，问在t=10时机器正常工作的概率如何？2前进方程和后退方程2.1福克-普朗克方程设t时刻系统状态概率记为：()tw，初始概率为(0)w若已知初始概率和转移率矩阵Q：如何求()tw？根据全概率公式，有w()w()()w()()w()()w()[1()]w()[()]w()w()[()]w()w()jkkjkjjjkkjkjjjjkkjkjjkkjkjkkjktttPttPttPttqtottqtotttqtotdttqdt≠≠+Δ=⋅Δ=⋅Δ+⋅Δ=+⋅Δ+Δ+⋅⋅Δ+Δ=+⋅⋅Δ+Δ=⋅∑∑∑∑∑写成矩阵形式有()()dttdt=wwQ初始条件：(0)w由此，可以根据初始概率和转移率矩阵得到()tw。若已知初始概率和转移概率矩阵P：如何求()tw？根据全概率公式：()(0)()tPt=ww求解机器维修问题2.2切普曼-柯尔莫哥洛夫方程{}{}{}),,()(/)()(/)()(/)(321231213IjitttktjtPitktPitjtPIk∈==⋅=====∑∈ξξξξξξ齐次马尔可夫过程的切普曼-柯尔莫哥洛夫方程：IjitPtPtPIkjkkiji∈⋅=+∑∈,,0,0,)()()(τττ2.2柯尔莫哥洛夫-费勒前进方程根据转移率矩阵Q求经过时间t以后的转移概率。从切普曼-柯尔莫哥洛夫方程，可以得到()()()()()()()()[1()]()[()]()()[()]ijikkjkijjjikkjkjijjjikkjkjijikkjkPttPtPtPtPtPtPtPtqtotPtqtotPtPtqtot≠≠+Δ=⋅Δ=⋅Δ+⋅Δ=+⋅Δ+Δ+⋅⋅Δ+Δ=+⋅⋅Δ+Δ∑∑∑∑由此得到关于状态转移概率的一个方程：柯尔莫哥洛夫-费勒前进方程：∑=kjkikjiqtPdttdP)()(初始条件：1()(0)0()ijijPij=⎧=⎨≠⎩考虑矩阵柯尔莫哥洛夫-费勒前进方程中的第i行，将矩阵)(tP的第i行记作)(tipQpp)()(ttdtdii=初始条件是(0)ip是第i个元素为1、其他元素为零的列矢量。由此可以根据Ｑ矩阵，确定经过时间ｔ从状态ｉ到其它状态转移的概率。柯尔莫哥洛夫-费勒前进方程的矩阵形式：QPP)()(ttdtd=初始条件：IP=)0(上述方程表示了根据Ｑ矩阵，确定经过时间ｔ状态转移概率矩阵。2.3柯尔莫哥洛夫-费勒后退方程根据转移率矩阵Q求经过时间t以后的转移概率。)()]([)()()]([)()](1[)()()()()()()(tPtotqtPtPtotqtPtotqtPtPtPtPtPtPttPjkkkijijkjkkijiiiikjkikjiiikjkikji⋅Δ+Δ⋅+=⋅Δ+Δ⋅+⋅Δ+Δ⋅+=⋅Δ+⋅Δ=⋅Δ=+Δ∑∑∑∑≠≠由此得到关于状态转移概率的一个方程：柯尔莫哥洛夫-费勒后退方程：∑=kjkikjitPqdttdP)()(初始条件是1()(0)0()ijijPij=⎧=⎨≠⎩考虑矩阵柯尔莫哥洛夫-费勒后退方程中的第j列，将矩阵)(tP的第j列记作)(tjs)()(ttdtdjjsQs=初始条件是(0)js：是第j个元素为1、其他元素为零的列矢量。由此可以根据Ｑ矩阵，确定从各状态出发，经过时间ｔ到j状态的转移概率。柯尔莫哥洛夫-费勒后退方程的矩阵形式：)()(ttdtdPQP=初始条件是IP=)0(上述方程表示了根据Ｑ矩阵，确定经过时间ｔ状态转移概率矩阵。前进方程，先选择初始态去分析，后退方程，先选择结束态去分析。前进方程和后退方程都是解决根据Q矩阵，确定转移概率矩阵的问题。例４3举例例1设有一个时间连续、状态离散的马尔可夫过程{}0),(≥ttξ，它的状态空间是I:{1,2,,m}。当mjiji,,2,1,,=≠时1=jiq；当mji,,2,1==时mqji−=1。求)(tPji。解：写出马尔科夫过程的Q矩阵或者绘出系统的状态转换图。给出m=4的一个例子：写出这个马尔科夫过程的Q矩阵，或者绘出系统的状态转换图。()iidtQdt=pp()∑≠+−=jkikijijtPtPtPdtd)()(41)(对应统一的形式为∑≠+−=jkikijijtPtPmtPdtd)()()1()(给出)(tPji的联立微分方程组()(1)()()ijijikkjdPtmPtPtdt≠=−−+∑考虑到规一化条件，()11()()ikkijikkjPtPtPt≠=−=∑∑进一步得到微分方程是，()(1)()1()()1ijijijijdPtmPtPtdtmPt⎡⎤=−−+−⎣⎦=−+解微分方程（待定系数法）得到mAetPmtji/1)(+=−考虑系统的初始条件，jiifPjiifPjiji==≠=,1)0(,0)0(相应微分方程的解是，mmetPmmemtPmtjimtii/1/1)(/1/)1()(+−=+−=−−求出Q矩阵建立状态转移概率的微分方程、状态转移概率的归一化条件；例2机器维修问题设某机器的正常工作时间是一负指数分布的随机变量，平均正常工作时间为1/λ，它损坏后的修复时间也是一个负指数分布的随机变量，它的平均修复时间为1/μ。如机器在t=0时是正常工作的，问在t=10时机器正常工作的概率如何？解1：(1)设)(tξ代表在t时刻机器的状态，有两个状态：工作中、维修中则状态空间记为I：{0,1}。机器从正常工作到故障的时间间隔是负指数分布的；机器从维修到恢复工作的时间间隔是副指数分布的；负指数分布是无记忆的、无后效性的。)(tξ是一个参数连续状态离散的马尔可夫过程。（2）求解Q矩阵：根据持续工作时间和故障修复时间的负指数分布特性，更新计数过程服从泊松分布，tΔ时间内系统状态转移概率如下：0,0()1PttλΔ=−⋅Δ0,1()PttλΔ=⋅Δ1,0()PttμΔ=Δ1,1()1PttμΔ=−⋅Δ因此，系统的Q矩阵为：λλμμ−⎡⎤=⎢⎥−⎣⎦QQλλμμ−⎛⎞=⎜⎟−⎝⎠(3)利用福克－普朗克方程求解Qλλμμ−⎛⎞=⎜⎟−⎝⎠[][][]010101()()()()()()dwtwtwtwtQwtwtdtλλμμ−⎛⎞==⎜⎟−⎝⎠001101()()()()()()dwtwtwtdtdwtwtwtdtλμλμ=−+=−初始条件：01(0)1,(0)0ww==解得：()0()1()()ttwtewteλμλμμλλμλμλλλμλμ−+−+=+++=−++解2:利用系统的后退方程求解（终结状态是正常工作的0状态），⎟⎟⎠⎞⎜⎜⎝⎛⎟⎟⎠⎞⎜⎜⎝⎛−−=⎟⎟⎠⎞⎜⎜⎝⎛=⎟⎟⎠⎞⎜⎜⎝⎛)()()()()()(100010001000tPtPtPtPQtPtPdtdμμλλ)()()()()()(100010100000tPtPtPdtdtPtPtPdtdμμλλ−=+−=初始条件：0010(0)1,(0)0PP==由微分方程组可以得到，[][]0)()()()()()(100010001000=−++−=+tPtPtPtPtPdtdtPdtdμμλλλμλμ即CtPtP=+)()(1000λμ，考虑到初始条件有，CPP==⋅+⋅=+μλμλμ01)0()0(1000即[])(1)(,)()(00101000tPtPtPtP−==+μλμλμ代入微分方程组，解)(00tP的微分方程[]μμλμλ++−=−+−=)()()(1)()(00000000tPtPtPtPdtdμμλ=++)()()(0000tPtPdtd得到微分方程