马尔可夫链课件

1、CHAPTER 5 马尔可夫链第一节 基本概念1、分类离散连续离散连续马尔可夫链马尔可夫序列可数状态马尔可夫过程连续状态马尔可夫过程按马尔可夫过程参数空间和状态空间的不同可分为一、马尔可夫链的定义及例子 随机过程 称为马尔可夫链，若它只取有限或可列个值（称为过程的状态，记为0，1，2，），并且，对任意 及状态 ，有2. 马尔可夫链的定义 定义 称 为n时刻的一步转移概率。 若 ，即pij与n无关，称转移概率具有平稳性.此时称Xn,n0为齐次（或时齐的）马尔可夫链。记P=(pij)，称P为Xn,n0的一步转移概率矩阵.3、转移概率4、马尔可夫链的例子显然Yn , n1也是一马尔可夫链。例1 独立

2、随机变量和的序列 设 Yn,n1为独立同分布随机变量序列，且Yn取值为非负整数，其概率分布为PYn=i=ai，i=0,1,2, 令X0=0,Xn=Y1+ Yn ，则易证Xn,n0是一马尔可夫链，且例2 M/G/1排队系统 假设顾客依参数为 的泊松过程来到一服务中心，只有一个服务员，来客发现服务员空着即刻得到服务；其他人排队等待服务。相继来到的顾客的服务时间Ti假定为相互独立的随机变量，具有共同的分布G；且假定他们与来到过程独立。 M/G/1排队系统中字母M代表顾客来到时间间隔服从指数分布， G代表服务时间的分布， 数字1代表只有一个服务员。 若以X(t)记在t时刻系统中的顾客数，X(t),t0

3、则不具马尔可夫性。因为，若我们知道在t时刻系统中的顾客数，那么为了预测将来的状态，我们不用关心从最近的一位顾客来到后已过去了多长时间（因为来到过程是无记忆的），但和服务中的顾客服务了多长时间有关（因为服务时间分布不具无记忆性）。Xn-第n个顾客走后剩下的顾客数，Yn -第n+1个顾客接受服务期间来到的顾客数，则容易证明Yn，n1独立同分布，且因此， Xn，n1是马尔可夫链。其转移概率为 为了克服上述困难，我们可以只在顾客离去的时刻考察系统，记例3 G / M /1排队系统 来到时间间隔分布为G，服务时间分布为指数分布，参数为 ，且与顾客到达过程独立。 Xn-第n个顾客来到时见到系统中的顾客数（

4、包括该顾客），则Xn，n1是马尔可夫链。记 Yn -第n个顾客来到时刻到第n+1个顾客来到时刻之间系统服务完的顾客数，则 pi0公式略有不同，它是服务台由有i个顾客转为空闲的概率，即第n个顾客来到时刻到第n+1个顾客来到时刻之间系统服务完的顾客数i+1。例4 直线上的随机游动 （1）无限制的随机游动 设有一质点在数轴上随机游动，每隔一单位时间移动一次，每次只能向左或向右移动一单位，或原地不动。设质点在0时刻的位置为a,向右移动的概率为p，向左移动的概率为q，原地不动的概率为r(p+q+r=1),且各次移动相互独立，以Xn表示质点经n次移动后所处的位置，则Xn,n0是一马尔可夫链,转移概率为Pi

5、,i+1=p, Pi,i-1=q, Pi,i=r, 其余Pi,j=0 （2）带吸收壁的随机游动 设（1）中的随机游动限制在S=0,1,2, b，当质点移动到状态0或b后就永远停留在该位置，即p00=1, pbb=1，其余pij(1i,j b-1)同（1），这时Xn,n0称为带两个吸收壁0和b的随机游动 ，它是一有限状态马尔可夫链。例5 Polya（波利亚）模型 罐中有b只黑球及r只红球，每次随机地取出一只后把原球放回，并加入与抽出球同色的球c只，再第二次随机地取球重复上面步骤进行下去，Xn=i表示第n回摸球放回操作完成后，罐中有i只黑球这一事件，所以这是一个非齐次的马尔可夫链，在传染病研究中有

6、用。 下面的定理提供了一个非常有用的获得马尔可夫链的方法，并可用于检验一随机过程是否为马尔可夫链。定理：设随机过程Xn,n0满足 （1） Xn=f(Xn-1,Yn),(n 1), 其中f:S S S,且Yn取值在S上， （2） Yn,n1为独立同分布随机变量，且X0与Yn,n1也相互独立，则Xn,n0是马尔可夫链，其一步转移概率为 pij=Pf(i,Y1)=j证明：设n1 ，则Yn+1与X0, X1, , Xn相互独立，事实上， 因为X1=f(X0,Y1)， Y2与X0,Y1独立，所以， Y2与X1， X0独立。同理， X2=f(X1,Y2)= f(f(X0,Y1),Y2)，所以， Y3与X2

7、， X1， X0独立。归纳可得Yn+1与X0, X1, , Xn相互独立。所以Xn,n0是马尔可夫链，且所以有二、切普曼-柯尔莫哥洛夫方程 显然马尔可夫链Xn,n0的一步转移概率矩阵P为随机矩阵。2，n步转移概率定义：设Xn,n0是一马尔可夫链，称1，随机矩阵 定义：称矩阵A=(aij)SS为随机矩阵，若aij 0，且为马尔可夫链Xn,n0的n步转移概率。记称为n时刻Xn的概率分布向量。称为马尔可夫链Xn,n0的初始分布向量。 结论：一个马尔可夫链的特性完全由它的一步转移概率矩阵及初始分布向量决定。 类似地可以证明马尔可夫链任意个时刻的联合分布也完全由一步转移概率矩阵及初始分布向量决定。事实上

8、3、定理：切普曼-柯尔莫哥洛夫方程（C-K方程）或其中为马尔可夫链Xn , n0的n步转移概率矩阵。证明： 例（马尔可夫预测）某种鲜奶A改变了广告方式，经调查发现购买A种鲜奶及另外三种鲜奶B、C、D的顾客每两个月的平均转换率为：（假设市场上只有这4种鲜奶） A A（95%） B（2%） C（2%） D（1%） B A（30%） B（60%）C（6%） D（4%） C A（20%） B（10%）C（7%） D（0%） D A（20%） B（20%）C（10%） D（50%）假设目前购买A、B、C、D 4种鲜奶的顾客的分布为（25%，30%，35%，10%），求半年后鲜奶A、B、C、D的市场份额。

9、解 一阶转移矩阵为初始分布为则半年后A种鲜奶的市场占有率为（1）写出状态空间；（2）求P(2)；（3）问在甲获得1分的情况下，再赛二局可以结束比赛的概率是多少？例 甲、乙两人进行比赛，设每局比赛中甲胜的概率p，乙胜的概率是q，和局的概率是 r,(p+q+r=1)。设每局比赛后，胜者记“+1”分，负者记“-1”分，和局不记分。当两人中有一人获得2分结束比赛。以Xn表示比赛至第n局时甲获得的分数。 解 （1）记甲获得“负2分”为状态1，获得“负1分”为状态2，获得“0分”为状态3，获得“正1分”为状态4，获得“正2分”为状态5，则状态空间为一步转移概率矩阵为（2）二步转移概率矩阵（3）在P2中P4

10、5(2)是在甲得1分的情况下经二步转移至2分从而结束比赛的概率； P41(2)是在甲得1分的情况下经二步转移至-2分（即乙得2分）从而结束比赛的概率。解例 某计算机房的一台计算机经常出故障,研究者每隔15分钟观察一次计算机运行状态,收集了24小时的数据 (共作97次观察) . 用1表示正常状态, 用0表示不正常状态, 所得的数据序列如下:1110010011111110011110111111001111111110001101101分析状态空间: I=0, 1. 例11101101101011110111011110111111001101111110011196 次状态转移的情况:因此,

11、一步转移概率可用频率近似地表示为:第二节 状态的分类及性质 定义1 : 若存在某个n使得 ，则称从状态i可达状态j，记为ij，如果ij且 j i ，则称 i 与 j 相通，记为 。若一马尔可夫链的任意两个状态都是相通的，则称该马尔可夫链是不可约的。 若pii=1。则称状态 i 为吸收态。定理：相通是一种等价关系。即 定义2：若集合 则称该数集的最大公约数d(i)为状态 i 的周期。若d(i) 1，称i为周期的，若d(i) =1，称i为非周期的。 注意：若状态 i 的周期为d ,则对一切n0（mod(d)）都有 ,但并非对任意的n，都有 。例如定理：则 d ( i )=d ( j )。证明：若i

12、与j相通，则存在m,n，使得对任意的s，若有 ，则则，对应状态1而言，集合的最大公约数为2，所以， 。但是，当 时， 。但可以证明：对于充分大的n，有 。 因为d(i)是i的周期，所以d(i)应同时整除n+m和n+m+s，则d(i)一定整除s，而d(j)是j的周期，所以d(i)整除d(j)。反过来也可证明d(j)整除d(i)，于是d(i)= d(j)。定义3：首达时间定义为若右边为空集，则令 Tij表示从i出发首次到达j的时间，Tii表示从 i 出发首次回到 i 的时间.定义4：首达概率定义为表示从i经n步首次到达j的 概率。显然有定义5 fij表示过程从i出发在有限步内能够到达j的概率，（或

13、者说从i出发迟早转移到状态j的概率）。fii表示过程从i出发在有限步内（迟早）回到状态i的概率。定义6: 若fii=1, 则称 i 为常返状态， 若fii1, 则称 i 为非常返状态（或瞬时状态或称滑过的）。定义7: 若 i 为常返状态，即 fii=1, 记称 为从状态 i 出发再回到 i 的平均回转时间（或平均回转步数）。若 ，称为正常返状态，若 ，称为零常返状态。 定义8: 若状态 i 是正常返的并且是非周期的，则称状态 i 为遍历状态。注：当 i 为非常返状态（滑过的）时， 。定理： 与 有如下关系定理：状态 i 是常返状态，当且仅当状态 i 是非常返状态，当且仅当证明：约定 ，的含义则

14、表示过程到达 i 的次数。所以表示过程从 i 出发返回到 i 的平均次数。 若状态 i 是滑过的（非常返的）则 即滑过状态i只能有限次到达i 。从而有限状态的马尔可夫链不可能全部状态都是滑过的。即有限状态的马尔可夫链至少有一个状态是常返的。 定理：若 ，则 i, j 同为常返的和非常返的。即常 返性具有类性质。若为常返的，则它们同为正常返状态或零常返状态。 证明：由 ，知存在n, m， 使得 ，由C-K方程总有所以， 相互控制，同为无穷或有限，从而同为常返或非常返。 以Nj(t)记到时刻t为止转移到j的次数。若j是常返的，且X0=j，则因为一旦转移到j，过程在概率上重新从头开始，故Nj(t),

15、t0是一个来到时间间隔分布为 的更新过程。若X0=i ， ，且j是常返的，则Nj(t),t0是一个延迟更新过程，其初始来到时间间隔分布为 。 为什么要将状态进行分类呢？ 常返态表明，过程从常返状态出发能无穷次返回该状态，而滑过状态最多只能有限次地返回，因此，随着时间的发展，滑过状态将逐渐消失。所以，在对Markov链作稳态设计时，滑过状态是不予考虑的，这也说明了区分常返态与滑过状态是十分重要的。例 考虑直线上无限制的随机游动，状态空间为转移概率为则对于状态0，有由斯特林(Stirling)公式可知：当n充分大时有所以注意到所以，当 时， 此时，状态0是常返的。当 时，此时，状态0是滑过的。 由

16、于过程的各个状态都是相通的，由此可判断其它状态的常返性。例转移矩阵试对其状态分类。解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。考虑状态1是否常返，类似地可求得所以于是状态1是常返的。又因为所以状态1是正常返的。由定理可知，此链所有状态都是正常返的。例设马氏链的状态空间I=0,1,2,，其一步转移概率为其中试证此马氏链是一个不可约常返态链证先证I不可约设i，j是I中任意两个状态，则有类似地可证所以即I中任意两个状态都是相通的。因此，I是一个不可约的闭集再证I中状态0是一个常返态：由状态的转移规则，得所

17、以102345由定义知状态0为常返态。因此，由定理知I中所有状态都是常返态。故此马氏链为不可约常返链。 例 股票价格的马尔科夫性 考虑离散时间的股票价格过程，对时间t (t=0,1,2, ),设S(t)表示某一股票在t 时刻的价格，每间隔一个单位时间股票价格以概率q上升到前一期的u倍，或以概率1-q下降到前一期的 d 倍，且各次涨跌是相互独立的，即以概率q,以概率1-q, 设S(0)=S，则 定义独立同分布的随机变量序列第 i 次上涨,第 i 次下跌。则并且定义第 i 次上涨,第 i 次下跌。则 是一Markov链。(随机游动) 状态空间的分解 定义1 设马尔可夫链的状态空间为S， ，若对任意

18、的 ，都有 ，则称 C 为（随机）闭集。若C 的状态相通，则称闭集C 是不可约的。 注：状态 i 是吸收态等价于单点集 i 是闭集；马尔可夫链的整个状态空间为 S 构成一闭集。 闭集 C 的直观意义是自 C 的内部不能到达 C 的外部，这意味着系统状态一旦进入闭集 C 内，它就永远在C 中运动。 引理1 C是闭集的充要条件是对任意的都有 。 证明：充分性显然，下证必要性，用归纳法证明：当n=1时，由定义知结论成立，假设 n=k 时结论成立，即对任意的 有 则 引理2 若 i 是常返的，且 ，则 。 证明：若假如 ，则以正概率 ，使得从 j 出发不能在有限步内到达 i 。而 ，这意味着系统中存在

19、着一个正概率，使得它从 i 出发不能在有限步内回到 i , 从而 ，与 i 是常返状态矛盾，所以只能 。 引理3 若 i 是常返的，且 ，则 j 是常返的。 证明：由引理 2 知 ，于是存在 n 使得从而 ，即 。所以 。即 j 也是常返状态。 定理1 所有的常返状态构成一闭集。 证明：设 i 是常返状态，且 ，则引理1，2知 ，且 j 也是常返状态，说明从常返状态出发只能到达常返状态，不可能到达非常返状态。 定理2 马尔可夫链的状态空间 S 可分解为其中 为基本常返闭集，且T 为所有非常返状态组成的集合（不一定是闭集）。 【注】当系统从某非常返状态出发，系统可能一直在非常返集 T 中（当 T

20、 为闭集时），也可能在某时刻离开 T 进入到基本常返集中运动，一旦进入到基本常返集，就永远在该常返集中运动。 定理3 若 S 为有限集，则所有非常返状态组成的集合 T 一定是非闭集。即不管系统自什么状态出发，迟早要进入常返闭集。 推论 有限不可约马尔可夫链的状态都是常返态。即 定理4 设 是闭集，只考虑 上所得的 m步转移概率子矩阵 ，则 是一随机矩阵。 证明：显然 ， 任取所以，矩阵 为随机矩阵。 定理5 （系统进入基本常返闭集后的运动情形） 若基本常返闭集 中的状态的周期为d，则 可进一步 d 个不交子集之和，即这些子集有性质：自 中任一状态出发， 下一步（经1步转移）必转移到 中去。 如

21、果 i=d-1，则 i+1=d 解释为0，即 中的的状态下一步转移到 中去。证略。第三节 极限定理与平稳分布 一、极限定理 在实际应用中，人们常常关心两个问题： （1）当 时， 的极限是否存在？ （2）当什么条件下，一个马尔可夫链是一个平稳序列？ 注意到： ，故对（1）的研究可转化为对 的渐近性质的研究。即 是否存在？若存在，其极限是否与状态 i 有关？Markov链理论中，有关这一问题的定理统称为遍历定理。 问题(2) 的实际上是讨论马尔可夫链平稳分布是否存在的问题。这两个问题之间有密切联系。 例1 设马尔可夫链的转移概率矩阵为现在来计算令则所以 定理1 若 j 是非常返态（滑过的）则对任意

22、的 i 有证明：因为所以，令 ，得（因为 j 是非常返态）显然此时有 定理2 若 j 是常返态，则（1）若 ， 则有（2）若 时（不可达）则有证明（1）若 ，则 使得而故 （2）显然。的含义则表示过程到达 j 的次数。所以表示过程从 i 出发进入状态 j 的平均次数。 定理3 若 j 是非常返态或零常返态，则对任意的 i 有 证明：定理1已证 j 是非常返态情形，当 j 是零常返态时，取 有，先固定 m ，令 得这是因为上式中 ，且是有限项和。从而再令 ，注意到所以 推论1 有限状态的马尔可夫链没有零常返态。 推论2 有限状态的马尔可夫链的状态不可能全为非常返状态。 推论3 不可约的有限状态马

23、尔可夫链的状态全为正常返的。 推论4 若马尔可夫链有一个零常返态，则必有无限个零常返态。（由推论1可得）。 定理4 若 j 是正常返态，周期为 d , 则对任意的 i 及 有 当 j 是正常返状态时情况较复杂，此时 不一定存在，即使存在也可能与 i 有关。这时有一下结论: (证略)其中 表示从状态 i 出发，在时刻 n=r (mod(d) 首次到达状态 j 的概率。且 推论1 若 j 是遍历状态（正常返的并且是非周期的），则对任意的状态 i S 有 证明：在定理4 中取 d =1, r = 0。 推论2 对于不可约的遍历链（即所有状态是遍历状态且相通），若对任意状态 i ，jS，有 注意到：若

24、 ，且 j 为常返态，则 。由推论1即得。 定理4 若 j 是常返状态，则对任意的 i S， 有 推论 若不可约马尔可夫链的状态是常返状态，则对任意的 i ，j S， 有 注意： 表示过程从 i 出发前 n个单位时间进入状态 j 的总的平均次数， 表示每单位时间到达状态 j 的平均次数，与 表达的含义相同。状态性质判别法：i非常返i零常返i正常返i遍历的二、平稳分布与极限分布 1，定义：设pij是马尔可夫链Xn, n1的转移概率。若概率分布pj , j 0满足则称pj, j 0为Xn, n1的平稳分布。记 则平稳分布可表示为如下矩阵形式显然有即 注意：由 知， 所以1是矩阵 P 的左特征值，平

25、稳分布 是 P 的左特征向量。 证明：若马尔可夫链 Xn, n0 的初始分布 即Xn与X0有相同的 分布，这说明过程Xn, n0是平稳过程。这也是称分布pj=PX0=j 为平稳分布的原因。 定理：设 Xn, n0 是马尔可夫链， 则 Xn, n0是平稳过程的充要条件是其初始分布是平稳分布。 是平稳分布，则对任意的 n ，有 反之，若Xn, n0 是平稳过程，则而所以即 是平稳分布。 平稳分布 可通过求方程组的非负解得到。其中 。 2，定义：若不可约马尔可夫链是遍历的（即所有状称为马尔可夫链的极限分布。态相通且均为周期为1的正常返态），则极限 定理：不可约遍历的马尔可夫链有唯一的平稳分布此时唯一

26、的平稳分布就是极限分布。即 注：若状态都是滑过的（非常返）或都是零常返的，则平稳分布不存在。 证明：由定理4的推论2知不可约遍历的马尔可夫链的极限分布存在，且下证 是平稳分布。由于则有易知上式中极限与求和可交换，则有再由C-K方程得，两边取极限得，即 ，从而 是平稳分布。再证平稳分布的唯一性： 假设还有另外一个平稳分布 ，则有归纳可证令 有，因为 ，所以有 ，即平稳分布是唯一的。 定理：一个不可约非周期的马尔可夫链属于下列两种情况之一： 1，状态或全是滑过的（非常返的）或全是零常返的。此时对一切的 i, j 有因而不存在平稳分布。2，状态全是正常返态。即此时 是平稳分布，且不存在任何其它的平稳

27、分布。此时极限分布即是平稳分布。注：1，对于不可约的遍历链（不可约、正常返、周期为1）因为所以， 可被解释为马尔可夫链长时间之后处于状态j 的时间所占的比率。2，对于不可约的遍历链，因为极限分布存在且等于平稳分布，这意味着当n充分大时有， 即Xn,n0是一渐近平稳序列(平稳过程)，这在实际问题中是很有意义的。例设马氏链的状态空间I = 0,1,2,，转移概率为试讨论各状态的遍历性。解根据转移概率作出状态传递图1/21/21/21/21/21/20121/231/2从图可知，对任一状态 都有 ，故由定理可知，I 中的所以状态都是相通的，因此只需考虑状态0是否正常返即可。故从而0是常返态。又因为所

28、以状态0为正常返。又由于故状态0为非周期的从而状态0是遍历的。故所有状态i都是遍历的。例设有6个球（其中2个红球，4个白球）分放于甲、乙两个盒子中，每盒放3个，今每次从两个盒中各任取一球并进行交换，以 表示开始时甲盒中红球的个数， （ ）表示经n次交换后甲盒中的红球数。( 1 ) 求马氏链 ， 的转移概率矩阵；( 2 ) 证明 ， 是遍历的；（3）求（4）求解其一步转移矩阵为甲乙红球0白球3红球2白球1红球1白球2红球1白球2红球2白球1红球0白球3并作出状态传递图1/32/95/92/32/91/30122/3（2）由于它是一个有限马氏链，故必有一个常返态，又链中三个状态0、1、2都相通，所

29、以每个状态都是常返态。所以是一个不可约的有限马氏链，从而每个状态都是正常返的。所以此链为非周期的。故此链是不可约非周期的正常返链，即此链是遍历的。（2）可以利用定理证明遍历性解之得故得（4）讨论对时间连续状态离散的马尔可夫过程，取时间参数 ，状态空间I=0,1,2,第五节 时间连续马尔可夫链一、定义及性质时间连续的马尔可夫链转移概率齐次马氏链转移概率仅由t决定而与s无关2性质性质1切普曼柯尔莫哥洛夫方程性质2连续时间齐次马氏链的有限维概率分布由它的初始分布和转移矩阵所确定注性质3注对时间来说是可逆性性质4已知现在，那么过去与将来是独立注性质5 （遍历性定理）马尔可夫定理设 , 是状态空间I=0,1，2,s的时间连续的齐次马氏链，则的满足条件的唯一解。例1考虑一个电话总机接到的呼唤流，以 表示这个总机在0，t中接到的呼唤次数，由于呼唤流在不相交的时间区间中接到的呼唤次数是相互独立的，且 服从泊松分布，所以 是一个时间连续状态离散的马氏过程，而且是齐次的。写出它的转移概率。当呼唤次数 时转移概率当 时其状态空间I=0，1，2，转移概率为1随机连续则称 是随机连续的