运筹学 ch13马尔可夫链

第十三章 马尔可夫链马尔可夫过程是一类特殊的随机过程, 马尔可夫链是离散状态的马尔可夫过程,最初是由俄国数学家马尔可夫1896年提出和研究的.应用十分广泛,其应用领域涉及计算机,通信,自动控制,随机服务,可靠性,生物学,经济,管理,教育,气象,物理,化学等等.第一节 马尔可夫链的定义一．定义定义 1 设随机过程}),({T t t X ∈的状态空间S 是有限集或可列集,对任意正整数n ,对于T 内任意1+n 个参数121+<<⋅⋅⋅<<n n t t t t 和S 内任意1+n 个状态121,,,,+⋅⋅⋅n n j j j j ,如果条件概率})(,,)(,)(|)({221111n n n n j t X j t X j t X j t X P =⋅⋅⋅===++})(|)({11n n n n j t X j t X P ===++,(13.1) 恒成立,则称此过程为马尔可夫链. 式(13.1)称为马尔可夫性,或称无后效性.马氏性的直观含义可以解释如下: 将n t 看作为现在时刻,那末,121,,,-⋅⋅⋅n t t t 就是过去时刻,而1+n t 则是将来时刻.于是,(13.1)式是说,当已知系统现时情况的条件下,系统将来的发展变化与系统的过去无关.我们称之为无后效性.许多实际问题都具有这种无后效性.例如 生物基因遗传从这一代到下一代的转移中仅依赖于这一代而与以往各代无关.再如,每当评估一个复杂的计算机系统的性能时,就要充分利用系统在各个时刻的状态演变所具有的通常概率特性:即系统下一个将到达的状态,仅依赖于目前所处的状态,而与以往处过的状态无关.此外,诸如某公司的经营状况等等也常常具有或近似具有无后效性.二． 马尔可夫链的分类状态空间S 是离散的(有限集或可列集),参数集T 可为离散或连续的两类.三．离散参数马尔可夫链（1）转移概率定义2 在离散参数马尔可夫链},,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 中,条件概率)(})(|)({1m ij m m t p i t X j t X P ===+称为)(t X 在时刻(参数)m t 由状态i 一步转移到状态j 的一步转移概率, 简称转移概率.条件概率)(})(|)({)(m n ij m n m t p i t X j t X P ===+称为)(t X 在时刻(参数)m t 由状态i 经n 步转移到状态j 的n 步转移概率.(2)转移概率的性质:对于状态空间S 内的任意两个状态i 和j ,恒有(1) 0)()(≥m n ij t p ;(2)1)()(=∑∈m Sj n ij t p ,⋅⋅⋅=,2,1n ()()(m Sj n ij t p ∑∈ })(|)({i t X j t X P m n m Sj ===+∈∑ })({})(,)({i t X P i t X j tX P m S j m n m ====∑∈+ })({}})(}){)({({i t X P i t X j t X P m S j m n m ====∑∈+1})({})({====i t X P i t X P m m )四.离散参数齐次马尔可夫链定义3 在离散参数马尔可夫链},,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 中,如果一步转移概率)(m ij t p 不依赖于参数m t ,即对任意两个不等的参数m t 和k t ,k m ≠,有)(})(|)({1m ij m m t p i t X j t X P ===+ij k ij k k p t p i t X j t X P =====+)(})(|)({1则称此马尔可夫链具有齐次性或时齐性,称)(t X 为离散参数齐次马尔可夫链.例1 Bernoulli 序列是离散参数齐次马尔可夫链.验证 在Bernoulli 序列},3,2,1,{⋅⋅⋅=n X n 中, 对任意正整数 n , 121+<<⋅⋅⋅<<n n t t t t ,121,,,,+⋅⋅⋅n n t t t t X X X X 相互独立, 故对 ,1,0=k j )1,,2,1(+⋅⋅⋅=n k ,有},,,|{211211n t t t n t j X j X j X j X P n n =⋅⋅⋅===++}{11+==+n t j X P n}|{11n t n t j X j X P n n ===++即满足马尔可夫性,且}|{11n t n t j X j X P n n ==++⎩⎨⎧=-====++++0,11,}{1111n n n t j p j p j X P n 当当 , 不依赖于参数n t ,满足齐次性.故Bernoulli 序列是离散参数齐次马尔可夫链.例2 爱伦菲斯特(Ehrenfest)模型 一容器中有a 2个粒子在作随机运动.设想有一实际不存在的界面把容器分为左右容积相等的两部分.当右边粒子多于左边时,粒子向左边运动的概率要大一些,大出部分与两边粒子的差数成正比;反之,当右边粒子少于左边时,粒子向右边运动的概率要大一些.以nX 表示n 次变化后,右边粒子数与均分数a 之差,则状态空间},1,,2,1,0,1,,1,{a a a a S -⋅⋅⋅-⋅⋅⋅+--=,转移概率 ⎪⎪⎪⎩⎪⎪⎪⎨⎧==±≠∈-=+=+---+-1,),1(21),1(211,1,1,1,a a a a j j j j p p a j S j a j p a j p则 },3,2,1,{⋅⋅⋅=n X n 是齐次马尔可夫链.第二节 参数离散的齐次马尔可夫链对于离散参数齐次马尔可夫链,本节讨论以下四个问题.一. 转移概率矩阵设 },,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 是齐次马尔可夫链, 由于状态空间S 是离散的(有限集或可列集)，不妨设其状态空间 },,,2,1,0{⋅⋅⋅⋅⋅⋅=n S .则对S 内的任意两个状态i 和j ,由转移概率 ij p 排序一个矩阵⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅=ij i i j j p p p p p p p p p P 101111000100 称为(一步)转移概率矩阵 .})(|)({1i t X j t X P p m m ij ===+转移概率矩阵的性质：(1) 0≥ij p ,即元素均非负;(2) 1=∑∈S j ij p ,即每行和为1.具有以上两个特点的方阵称为随机矩阵.转移概率矩阵就是一个随机矩阵.例1 Bernoulli 序列的状态空间}1,0{=S ,转移概率矩阵⎝⎛=⎪⎪⎭⎫ ⎝⎛=q q p p p p P 11100100 ⎪⎪⎭⎫p p , })(|)({1i t X j t X P p m m ij ===+⎩⎨⎧=====+1,0,})({1j p j q j t X P m .例1 一维随机游动一个质点在直线上的五个位置:0,1,2,3,4之上随机游动.当它处在位置1或2或3时,以31的概率向左移动一步而以32的概率向右移动一步;当它到达位置0时,以概率1返回位置1;当它到达位置4时以概率1停留在该位置上(称位置0为反射壁,称位置4为吸收壁).以j t X n =)(表示时刻n t 质点处于位置j ,4,3,2,1,0=j ,则},,,),({210⋅⋅⋅=t t t t t X 是齐次马尔可夫链.其状态空间}4,3,2,1,0{=S ,状态0是反射状态,状态4是吸收状态.其转移概率矩阵⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛==1000032031000320310003203100010)(ij p P})(|)({1i t X j t X P p m m ij ===+分别以4,3,2,1,0,0==j i ； 4,3,2,1,0,1==j i ；4,3,2,1,0,2==j i ；4,3,2,1,0,3==j i ；4,3,2,1,0,4==j i按题设条件求出转移概率 })(|)({1i t X j t X P p m m ij ===+ 画出状态转移示意图如图例3（成功流）设在一串贝努里试验中,每次试验成功的概率为p ,令⎩⎨⎧≤≤=n k k n k n X n 1,,,0次成功次试验接连第第次试验失败第则},3,2,1,{⋅⋅⋅=n X n 是齐次马尔可夫链.其状态空间},,,2,1,0{⋅⋅⋅⋅⋅⋅=k S ,其转移概率pq X P i X X P n n n -======++1}0{}|0{11,p n P i X i X P n n =+==+=+}1{}|1{1次试验时成功第,,0,,020100===p p p q p ，⎪⎪⎩⎪⎪⎨⎧=≤<+=+≥====+0,0,01,2,0}|{1j q i j i j p i j i X j X P p n n ij , （ ,3,2,1=i ）于是转移概率矩阵⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅=ij i i j j p p p p p p p p p P 101111000100⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=p q p q p q p q 0000000000二． 切普曼-柯尔莫哥洛夫方程定理一 设 },,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X是马尔可夫链,则有)()()()()()(n m l kj km n ik m l n ij t p t p t p ++∑=, (13.6)称为切普曼-柯尔莫哥洛夫方程.证 由条件概率定义计算公式,利用全概率公式和马氏条件,得})(|)({)()(i t X j t X P t p m l n m m l n ij ===+++})({})(,)({i t X P j t X i t X P m l n m m ====++ })({}})(,)(}){)({({i t X P j t X i t X k t X P m Sk l n m m n m =====∑∈+++})({})(,)(,)({i t X P j t X k t X i tX P m Sk l n m n m m=====∑∈+++ })({})(,)({})(,)({})(,)(,)({i t X P k t X i t X P k t X i t X P j t X k t X i t X P m n m m kn m m l n m n m m ===⋅======+++++∑})(|)({})(,)(|)({i t X k t X P k t X i t X j t X P m n m n m m kl n m ==⋅====++++∑})(|)({})(|)({i t X k t X P k t X j t X P m n m n m kl n m ==⋅===++++∑)()()()(n m l kj km n ik t p t p +∑= 证毕.如果马尔可夫链具有齐次性,那么切普曼-柯尔莫哥洛夫方程化为)()()(l kjkn ik l n ij p p p ∑=+ ,(13.7)当1,1==l n 时,得到kj kik ij p p p ∑=)2(,进一步改写为矩阵形式 2)2(P P=其中)()2()2(ijp P =是两步转移概率矩阵,P 是一步转移概率矩阵.用数学归纳法可得 nn P P =)(,⋅⋅⋅=,4,3,2n (13.8) 式(13.8)表明:n 步转移概率矩阵)()()(n ij n p P =等于一步转移概率矩阵P 的n 次幂.因此也常把n P 作为n 步转移概率矩阵的符号.例2 在本节例2中,求)2(00p 和)2(31p.解 由kj kik ij p p p ∑=)2(,得3131140)2(00=⨯==∑=k k k p p p,913131413)2(31=⨯==∑=k k k p p p.或用2)2()2()(P p Pij==.例3 传输数字0和1的通讯系统,每个数字的传输需经过若干步骤,设每步传输正确的概率为109,传输错误的概率为101,(1)问:数字1经三步传输出1的概率是多少? (2)若某步传输出数字1,那么又接连两步都传输出1的概率是多少?解 以n X 表示第n 步传输出的数字,则},2,1,0,{⋅⋅⋅=n X n 是一齐次马尔可夫链,0X 是初始状态,状态空间}1,0{=S ,一步转移概率矩阵⎝⎛=101109P ⎪⎪⎪⎪⎭⎫109101 (1) 2)2(P P =⎝⎛=101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109 ⎪⎪⎪⎪⎭⎫109101= ⎝⎛1001810082⎪⎪⎪⎪⎭⎫10082100183)3(P P =⎝⎛=101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101= ⎝⎛1001810082⎪⎪⎪⎪⎭⎫1008210018 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101=⎝⎛10002441000756 ⎪⎪⎪⎪⎭⎫10007561000244,756.01000756)3(11==p ; (2) }1|1,1{21===++n n n X X X P}1|1{1===+n n X X P }1,1|1{12===⋅++n n n X X X P}1|1{1===+n n X X P }1|1{12==⋅++n n X X P81.0)109(21111==⋅=p p .。

21021210分布马尔可夫过程及其概率1§马尔可夫过程的定义、1211111121.简称马氏链可夫链，马尔可夫过程称为马尔时间和状态都是离散的课稿南京邮电大学孔告化讲22110}|{),(i m j n m i j a X a X P n m m P ===++记马氏链的转移概率、221021210.),(的转移概率转移到状态在时刻条件下，处于状态为马氏链在时刻称j i i j a n m a m n m m P ++课稿南京邮电大学孔告化讲.))(()(步转移概率矩阵为称n n P n P i j =⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎝⎛==M ML M M L L L M L M M L L L L )()()()()()()()()())(()(212222111211n P n P n P n P n P n P n P n P n P n P n P N N N N N N i j LLN a a a 21MM N a a a 21矩阵齐次马氏链的转移概率、3Ia a n P j i i j ∈≥,0)()1(Ia n P i j i j ∈=∑∞=1)()2(1课稿南京邮电大学孔告化讲111⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎝⎛==M M L M M L L L M L M M L L L L N N N N N N p p p p p p p p p P P 212222111211)1(L L N a a a 21M M N a a a 211课稿南京邮电大学孔告化讲这一点上。

或移动到就以概率，则下一时刻或现在位于点的概率停在原处；如果一格，或以的概率向左或向右移动则下一时刻各以现在位于点是：如果发生游动。

游动的规则等时刻秒秒、仅在上作随机游动，并且仅在如图所示直线的点集设一醉汉一维随机游动例题)4(21)5(13/13/1),51(21}5,4,3,2,1{)(:Q i i Q I Q <<=L 12345过程，是一随机则的位置，时表示时刻若以},2,1,0,{L =n X Q n X n n 而且当时，等以后的行为只与有关，而与质点以前是如何到是完全无关的，所以，它是一个马氏链，且为齐次马氏链。

马尔可夫链的基本原理和使用方法马尔可夫链是一种描述随机过程的数学工具，它的基本原理是当前状态的转移概率只依赖于前一个状态，而与之前的状态无关。

这种特性使得马尔可夫链非常适合用于描述一些随机的动态系统，比如天气变化、股票价格波动等。

在这篇文章中，我们将探讨马尔可夫链的基本原理和使用方法。

一、马尔可夫链的基本原理马尔可夫链的基本原理可以用一个简单的例子来说明。

假设有一个只有两种天气状态的城市，晴天和雨天。

我们可以用一个状态转移矩阵来描述这个系统，其中每个元素表示从一个状态转移到另一个状态的概率。

假设当前是晴天，那么下一天是晴天的概率是，是雨天的概率是。

同样地，如果当前是雨天，那么下一天是晴天的概率是，是雨天的概率是。

这样，我们就可以用状态转移矩阵来描述整个系统的状态变化。

马尔可夫链的基本原理就是这样简单，当前状态的转移概率只与前一个状态有关，而与之前的状态无关。

这种特性使得马尔可夫链具有很多有趣的数学性质，比如收敛性、平稳分布等。

二、马尔可夫链的使用方法马尔可夫链在实际应用中有很多用途，比如随机游走、马尔可夫决策过程、马尔可夫链蒙特卡洛等。

下面我们将简要介绍一些常见的使用方法。

1. 随机游走随机游走是马尔可夫链最常见的应用之一，它描述了一个在状态空间中随机移动的过程。

比如在一维格子上，每一步都以一定的概率向左或向右移动。

这种随机游走的性质可以用马尔可夫链来描述，其中状态空间就是格子上的位置，转移概率就是向左或向右移动的概率。

2. 马尔可夫决策过程马尔可夫决策过程是一种动态规划问题，描述了一个在随机环境中做决策的过程。

比如在一个赌博游戏中，每一步都需要根据当前的状态选择一个动作，而每个动作都有一定的奖励和转移概率。

这种决策过程可以用马尔可夫链来描述，其中状态空间就是所有可能的状态，转移概率就是选择不同动作的概率。

3. 马尔可夫链蒙特卡洛马尔可夫链蒙特卡洛是一种基于随机采样的数值计算方法，用于估计复杂系统的期望值。

第十三章马尔可夫链(习题课)习题十三1. 已知齐次马尔可夫链的转移概率矩阵⎝⎛=03131P 323132⎪⎪⎪⎪⎪⎪⎪⎭⎫31310问此马尔可夫链有几个状态？求二步转移概率矩阵.解 因为转移概率矩阵是三阶的, 故此马尔可夫链的状态有三个;二步转移概率矩阵2)2()2()(P p P ij ==⎝⎛=0313*******⎪⎪⎪⎪⎪⎪⎪⎭⎫31310⎝⎛03131323132⎪⎪⎪⎪⎪⎪⎪⎭⎫31310⎝⎛=929293949594⎪⎪⎪⎪⎪⎪⎪⎭⎫939292 .2. 在一串贝努利试验中,事件A 在每次试验中发生的概率为p ,令⎩⎨⎧=发生次试验第不发生次试验第A n A n X n ,1,0 , ,3,2,1=n (1) },2,1,{ =n X n 是否齐次马尔可夫链？(2) 写出状态空间和转移概率矩阵; (3) 求n 步转移概率矩阵.解 (1) 根据题设条件知道 ,,,,21nX X X 是相互独立的, 所以 },2,1,{ =n X n 是马尔可夫链, 又转移概率⎩⎨⎧=======++1,0,}{}|{11j p j q j X P i X j X P n n n与n 无关,故},2,1,{ =n X n 是齐次马尔可夫链; (2) 状态空间}1,0{=S ,一步转移概率矩阵)(ij p P = ⎝⎛=q q ⎪⎪⎭⎫p p , ⎩⎨⎧========++1,0,}{}|{11j p j q j X P i X j X P p n n n ij . (3) n 步移概率矩阵nn ijn P pP==)()()( ⎝⎛=q q ⎪⎪⎭⎫p p . 3. 从次品率)10(<<p p 的一批产品中,每次随机抽查一个产品,以nX 表示前n 次抽查出的次品数,(1) },2,1,{ =n X n 是否齐次马尔可夫链？(2) 写出状态空间和转移概率矩阵; (3)如果这批产品共有100个,其中混杂了3个次品,作有放回抽样,求在抽查出2个次品的条件下,再抽查2次,共查出3个次品的概率. 解 (1)根据题意知,},2,1,{ =n X n 是齐次马尔可夫链; (2) 状态空间},,,2,1,0{ n S =, p 是次品率,p q -=1是正品率,根据题意知 ⎪⎪⎩⎪⎪⎨⎧+>+==<====+1,01,,,0}|{1i j i j p i j q i j i X j X P pn n ij, ,,,2,1,0,n j i = ;(3)次品率03.0=p , 所求概率为)2(232}2|3{p X X P n n ===+∑+∞==032k k k p p ++⋅+⋅++=000q p p q0582.097.003.022=⨯⨯==pq .4. 独立重复地掷一颗匀称的骰子,以nX 表示前n 次掷出的最小点数, (1) },2,1,{ =n X n 是否齐次马尔可夫链？(2) 写出状态空间和转移概率矩阵; (3)求}3|3,3{21===++n n n X X X P ; (4)求}1{2=X P .解 (1) 根据题意知,},2,1,{ =n X n 是齐次马尔可夫链;(2)状态空间 }6,5,4,3,2,1{,=S , }|{1i X j X P p nn ij ===+⎩⎨⎧≥=====+2,01,1}1|{11j j X j X P p n n j ,⎪⎪⎪⎩⎪⎪⎪⎨⎧≥======+3,02,651,61}2|{12j j j X j X P p n n j⎪⎪⎪⎩⎪⎪⎪⎨⎧≥======+4,03,642,1,61}3|{13j j j X j X P p n n j ,⎪⎪⎪⎩⎪⎪⎪⎨⎧=======+6,5,04,633,2,1,61}4|{14j j j X j X P p n n j ,⎪⎪⎪⎩⎪⎪⎪⎨⎧=======+6,05,624,3,2,1,61}5|{15j j j X j X P p n n j ,6,,2,1,61}6|{16 =====+j X j X P p n n j ;(3) }3|3,3{21===++n n n X X X P}3|3{1===+n n X X P }3,3|3{12===⋅++n n n X X X P}3|3{1===+n n X X P }3|3{12==⋅++n n X X P9464643333=⋅=⋅=p p ;(4) }|1{}{}1{126112i X X P i X P XP i ==⋅===∑=3611616116162=⋅+⋅=∑=i . 5.设齐次马尔可夫链},2,1,0,{ =n X n 的转移概率矩阵为⎝⎛=03131P 323132⎪⎪⎪⎪⎪⎪⎪⎭⎫31310 ,且初始概率分布为,31}{)0(0===j X P p j 3,2,1=j ,(1) 求}3,2,1{321===X X X P ; (2) 求}3{2=X P ; (3) 求平稳分布.解 (1)}3,2,1{321===X X X P}1,2|3{}1|2{}1{123121=======X X X P X X P X P}2|3{}1|2{}1{23121======X X P X X P X P23121}1{p p X P ⋅⋅==231203110}|1{}{p p j X X P j X P j ⋅⋅====∑= 23123110}{p p p j XP j j ⋅⋅==∑=814)03131(313132=++⨯⋅=; (2)}3{2=X P }|3{}{03120j X X P j X P j ====∑=)2(331}{j j p j XP ∑===277)939292(31=++= ;(3)平稳分布),,(321p p p 满足方程组031313211p p p p ++=,3231323212p p p p ++=,313103213p p p p ++=,1321=++p p p解之得41,42,41321===p p p .例6.具有三状态:0,1,2的一维随机游动,以j t X =)(表示时刻t 粒子处在状态),2,1,0(=j j 过程},,,),({210 t t t t t X =的一步转移概率矩阵⎝⎛=0q q P q p 0 ⎪⎪⎪⎭⎫p p 0 , (1) 求粒子从状态1经二步、经三步转移回到状态1 的转移概率;(2) 求过程的平稳分布.解 (1)}1)(|1)({2)2(11===+nn t X t X P ppq pq qp p pk k k20121=++==∑=,⎝⎛==222)2(q q q P P pq pq pq 2 ⎪⎪⎪⎪⎭⎫+222p pq p p ,⎝⎛+++==2333223)3(2pq q pq q p q q P P q p pq pq qp pq 2222++ ⎪⎪⎪⎪⎭⎫++3232222p q p p q p p 于是pq t X t X P p n n ====+}1)(|1)({3)3(11,(2) 平稳分布),,(210p p p 满足方程组 02100p q p q p p ++=, q p p p p p 21010++=, p p p p p p 21020++=,1210=++p p p ,解之得pq q p -=120 , pqpqp -=11,pq p p -=122 . 例7.设同型产品装在两个盒内,盒1内有8个一等品和2个二等品,盒2内有6个一等品和4个二等品.作有放回地随机抽查,每次抽查一个,第一次在盒1内取.取到一等品,继续在盒式内取;取到二等品,继续在2盒内取.以n X 表示第n 次取到产品的等级数,则},2,1,{ =n X n 是齐次马尔可夫链.(1) 写出状态空间和转移概率矩阵;(2) 恰第3、5、8次取到一等品的概率为多少？(3) 求过程的平稳分布解(1)根据题意, 状态空间}2,1{=S54108}1|1{111=====+n n X X P p, 51102}1|2{112=====+n n X X P p , 53106}2|1{121=====+n n X X P p ,52104}2|2{122=====+n n X X P p , 转移概率矩阵⎝⎛=5354P ⎪⎪⎪⎪⎭⎫5251 ; (2) 54}1{1==X P ,51}2{1==X P , }1,1,1{853===X X X P}1,1|1{}1|1{}1{358353=======X X X P X X P X P }1|1{}1|1{}1{58353======X X P X X P XP)3(11)2(113}1{p p X P ==9 )3(11)2(1121131}|1{}{p p i X X P i XP i ∑=====)3(11)2(1121)2(11}{p p p i XP i i ∑===,⎝⎛==251825192)2(P P ⎪⎪⎪⎪⎭⎫257256, ⎝⎛==12593125943)3(P P ⎪⎪⎪⎪⎭⎫1253212531,}1,1,1{853===X X X P)3(11)2(1121)2(11}{p p p i X P i i ∑===752.076.0)72.02.076.08.0(⨯⋅⨯+⨯=429783.0= ;(3) 平稳分布),(21p p 满足方程组 5354211p p p +=, 5251212p p p +=, 121=+p p ,解之得 431=p , 412=p .。

马尔可夫链的概念及转移概率第四章4.1 马尔可夫链的的概念及转移概率一、知识回顾二、马尔可夫链的的定义三、转移概率四、马尔可夫链的一些简单例子五、总结一、知识回顾1. 条件概率定义：设A，B为两个事件，且，称为事件A发生条件下B事件发生的条件概率。

将条件概率公式移项即得到所谓的乘法公式：2.全概率公式设试验E的样本空间为S，A为E的事件，若为S的一个完备事件组，既满足条件：1)两两互不相容，即2).，且有，则此式称为全概率公式。

3.矩阵乘法矩阵乘法的定义，如果那么矩阵C叫做矩阵A和B的乘积，记作4.马尔可夫过程的分类马尔可夫过程按其状态和时间参数是连续的或离散的，可分为三类：（1）时间、状态都是离散的马尔科夫过程，称为马尔可夫链；（2）时间连续、状态离散的马尔科夫过程称为连续时间的马尔可夫链的；（3）时间、状态都连续的马尔科夫过程。

二、马尔科夫链的定义定义4.1设有随机过程，若对于任意的整数和任意的，条件概率都满足(4.1.1) 则称为马尔科夫链，简称马氏链。

式(4.1.1)即为马氏链，他表明在状态已知的条件下，的条件概率与无关，而仅与所处的状态有关。

式(4.1.1)是马尔科夫链的马氏性（或无后效性）的数学表达式。

由定义知===可见，马尔科夫链的统计特性完全由条件概率所决定。

如何确定这个条件概率，是马尔科夫链理论和应用中的重要问题之一。

现举一例说明上述概念：例4.1.1 箱中装有c个白球和d个黑球，每次从箱子中任取一球，抽出的球要到从箱子中再抽出一球后才放回箱中，每抽出一球作为一次取样试验。

现引进随机变量序列为,每次取样试验的所有可能结果只有两个，即白球或黑球。

若以数代表白球，以数代表黑球则有由上所述的抽球规则可知，任意第n次抽到黑球或白球的概率只与第n-1次抽得球的结果有关，而与抽的球的结果无关，由此可知上述随机变量序列,为马氏链。

三、转移概率定义4.2称条件概率为马尔科夫链在时刻N的一步转移概率，其中，简称为转移概率。

马尔可夫链在运筹学中的应用分析马尔可夫链是概率论中一个重要的概念，它描述了一个随机过程，在给定当前状态的情况下，未来状态只依赖于当前状态，而与过去状态无关。

这种性质使得马尔可夫链在运筹学中有着广泛的应用。

本文将从马尔可夫链的基本概念入手，探讨其在运筹学中的具体应用，并分析其在实际问题中的作用和意义。

马尔可夫链的基本概念马尔可夫链是一个随机过程，通常用状态空间和状态转移概率矩阵来描述。

状态空间包括了所有可能的状态，而状态转移概率矩阵则描述了从一个状态转移到另一个状态的概率。

马尔可夫链具有马尔可夫性质，即未来状态的转移概率只与当前状态有关，与过去状态无关。

在运筹学中，马尔可夫链常常用于描述系统的演化过程，例如排队系统、库存管理、生产调度等。

通过建立适当的状态空间和状态转移概率矩阵，可以对系统的行为进行建模和分析，从而优化系统的性能和效率。

马尔可夫链在排队系统中的应用排队系统是运筹学中一个重要的研究对象，涉及到顾客到达、排队等待和服务过程。

马尔可夫链可以很好地描述排队系统中顾客的到达和服务过程，从而帮助我们分析系统的性能和效率。

以M/M/1排队系统为例，其中M表示顾客到达的时间间隔服从指数分布，服务时间也服从指数分布，1表示只有一个服务台。

我们可以建立一个二维的状态空间，分别表示系统中顾客的个数和服务台的状态。

通过计算状态转移概率矩阵，可以得到系统在不同状态下的稳定分布，进而分析系统的平均等待时间、利用率等性能指标。

马尔可夫链在库存管理中的应用库存管理是企业运营中一个重要的环节，涉及到存货成本、服务水平等方面。

马尔可夫链可以用来描述库存水平的变化过程，帮助企业合理制定库存策略，降低存货成本，提高服务水平。

以库存补货问题为例，我们可以建立一个状态空间，分别表示库存水平的不同状态。

通过计算不同状态之间的转移概率，可以得到系统在不同库存水平下的稳定分布。

进而可以分析最优的补货策略，使得库存水平能够在合适的范围内波动，既不会出现缺货现象，又不会造成过多的库存积压。