第4章 马尔可夫链

第4章马尔可夫链•马尔可夫过程按其状态和时间参数是连续的或离散的，可分为三类：•（1）时间、状态都是离散的马尔可夫过程，称为马尔可夫链。•（2）时间连续、状态离散的马尔可夫过程，称为连续时间的马尔可夫链。•（3）时间、状态都连续的马尔可夫过程。§4.1马尔可夫链的概念及转移概率一、马尔可夫链的定义假设马尔可夫过程{,}nXnT的参数集T是离散的时间集合，即{0,1,2,}T，其相应nX可能取值的全体组成的状态空间是离散的状态集12{,,}Iii。定义1设有随机过程{,}nXnT，若对于任意的整数nT和任意的011,,,niiiI，条件概率满足11001111{,,,}{}nnnnnnnnPXiXiXiXiPXiXi则称{,}nXnT为马尔可夫链，简称马氏链。上式是马尔可夫链的马氏性（或无后效性）的数学表达式。由定义知001100111100111111001111111122110{,,,}{|,,,}{,,,}{|}{,,,}{|}{|}{|nnnnnnnnnnnnnnnnnnnnnnPXiXiXiPXiXiXiXiPXiXiXiPXiXiPXiXiXiPXiXiPXiXiPXiX0}i可见，马尔可夫链的统计特性完全由条件概率11{|}nnnnPXiXi所决定。二、转移概率条件概率1{|}nnPXjXi的直观含义为系统在时刻n处于状态i的条件下，在时刻n+1系统处于状态j的概率。它相当于随机游动的质点在时刻n处于状态i的条件下，下一步转移到状态j的概率，记此条件概率为()ijpn，其严格定义如下：定义2称条件概率1{|}ijnnpPXjXi为马尔可夫链{,}nXnT在时刻n的一步转移概率，其中,ijI，简称为转移概率。一般地，转移概率()ijpn不仅与状态i,j有关，而且与时刻n有关。当()ijpn不依赖于时刻n时，表示马尔可夫链具有平稳转移概率。定义3若对任意的,ijI，马尔可夫链{,}nXnT的转移概率()ijpn与n无关，则称马尔可夫链是齐次的，并记()ijpn为ijp。下面我们只讨论齐次马尔可夫链，通常将“齐次”两字省略。设P表示一步转移概率()ijpn所组成的矩阵，且状态空间{1,2,}I，则1112121222nnpppPppp称为系统状态的一步转移概率矩阵。它具有性质：(1)0,,ijpijI;(2)1,ijjIpiI。(2)式中对j求和是对状态空间I的所有可能状态进行的，此性质说明一步转移概率矩阵中任一行元素之和为1。通常称满足上述(1)，(2)性质的矩阵为随机矩阵。定义4称条件概率(){|}(,,0,1)nijmnmpPXjXiijImn为马尔可夫链{,}nXnT的n步转移概率，并称()()()nnijPp为马尔可夫链的n步转移矩阵，其中()()0,1nnijijjIpp，即()nP也是随机矩阵。当n=1时，(1)ijijpp，此时一步转移矩阵(1)PP。此外，我们规定(0)0,1,ijijpij定理1设{,}nXnT为马尔可夫链，则对任意整数0,0nln和,ijI，n步转移概率()nijp具有下列性质112111()()()()()(1)()(1);(2);(3);(4).nnnlnlijikkjkInijikkkkjkIkInnnnpppppppPPPPP证(1)利用全概率公式及马尔可夫性，有()()()()(){,}{}{}{,,}{,}{,}{}{|}{,}()()nmmnijmnmmmmlmnmmlkImmlmmnmlmlmkInllnllkjikkjikkIkIPXiXjpPXjXiPXiPXiXkXjPXiXkPXiXkPXiPXjXkPXkXipmlpmpp(2)在(1)中令11,lkk得111()(1)nnijikkjkIppp这是一个递推公式，故可递推得到112111()nnnijikkkkjkIkIpppp(3)在(1)中令l=1，利用矩阵乘法可证。(4)由(3)，利用归纳法可证。定理1中(1)式称为切普曼---柯尔莫哥洛夫方程，简称C--K方程。它在马尔可夫链的转移概率的计算中起着重要的作用。(2)式说明n步转移概率完全由一步转移概率决定。(4)式说明齐次马尔可夫链的n步转移概率矩阵是一步转移概率矩阵的n次乘方。定义5设{,}nXnT为马尔可夫链，称0{}(){},()jjnpPXjPnPXjjI和为{,}nXnT的初始概率和绝对概率，并分别称{,}jpjI和{(),}jpnjI为{,}nXnT的初始分布和绝对分布，简记为{}jp和{()}jpn。称概率向量12()((),(),),(0)TPnpnpnn为n时刻的绝对概率向量，而称12(0)(,,)TPpp为初始概率向量。定理2设{,}nXnT为马尔可夫链，则对任意jI和1n，绝对概率()jpn具有下列性质：()()(1)()(2)()(1)(3)()(0)(4)()(1)njiijiIjiijiITTnTTpnpppnpnpPnPPPnPnP由（1）知，绝对概率由初始分布和n步转移概率完全确定（1）)()(nijIiinppjp证}{jXPn},{0iXjXPnIi}|{}{00iXjXPiXPnIi)(nijIiipp},{0iXjXPin定理3设{,}nXnT为马尔可夫链，则对任意12,,,niiiI和1n，有11211122{,,,}nnnniiiiiiiiIPXiXiXipppp三、马尔可夫链的一些简单例子例1无限制随机游动设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动的概率为q=1-p，这种运动称为无限制随机游动。以nX表示时刻质点所处的位置，则{,}nXnT是一个齐次马尔可夫链，试写出它的一步和k步转移概率。解显然{,}nXnT的状态空间{0,1,2,}I，其一步转移概率矩阵为0000qpPqp设在第k步转移中向右移了x步，向左移了y步，且经过k步转移状态从i进入j，则xykxyji从而()(),22kjikjixy由于x,y都只能取整数，所以()kji必须是偶数。又在k步中哪x步向右，哪y步向左是任意的，选取的方法有xkc种。于是(),()0()xxykkijcpqkjipkji为偶数，为奇数分析例2赌徒输光问题赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为，求甲输光的概率。pq1这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢1元）的概率为p，向左移（即输1元）的概率为q。如果一旦到达0（即甲输光）或a+b（即乙输光）这个游动就停止。这时的状态空间为{0，1，2，…，c}，c=a+b，。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。考虑质点从j出发移动一步后的情况解设cj0设ju为质点从j出发到达0状态先于到达c状态的概率。在以概率p移到1j的假设下，到达0状态先于到达c状态的概率为1ju同理以概率q移到1j的前提下，到达0状态先于到达c状态的概率为1ju根据全概率公式有qupuujjj11这一方程实质上是一差分方程，它的边界条件是0,10cuu于是设（p+q）11jjjqupuu))((11jjjjuupquupqr1jjjuud则可得到两个相邻差分间的递推关系1jjrdd于是0221drdrrddjjjj欲求au先求ju需讨论r当而1rcuu01)(110jjcjuujcjd10010drjcj011drrccjjuuu)(11iicjiuu011drdicjiicji01)1(drrrjcj01drrrcj两式相比ccjjrrru1故ccaarrru1ccapqpqpq)(1)()(当1r001cduuc而0)(djcuj因此cjcuj故cbcacua用同样的方法可以求得乙先输光的概率由以上计算结果可知当1r即qp时，甲先输光的概率为ccapqpqpq)(1)()(当1r即qp时，甲先输光的概率为cb当qp时，乙输光的概率为capqpq)(1)(1当qp时，乙先输光的概率为ca例3天气预报问题设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨，今日有雨，明日有雨的概率为0.5；昨日有雨，今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为0.2。若星期一、星期二均下雨，求星期四下雨的概率。解：设昨日、今日连续有雨称为状态０(RR)，昨日无雨、今日有雨称为状态１(NR)，昨日有雨、今日无雨称为状态2(RN)，昨日、今日无雨称为状态３(NN)，于是天气预报模型可以看着一个四个状态的马尔可夫链，转移概率为7.0}{}{}{00今昨明今昨明今连续三天有雨RRRPPRRRRPp0}{01今昨明今RRRNPp3.0}{}{02今昨明今昨明今RRNPRRNRPp0}{03今昨明今RRNNPp其中R代表有雨，N代表无雨。类似可得所有状态的一步转移概率。其一步转移概率矩阵为8.002.006.004.0005.005.003.007.033323130232221201312111003020100ppppppppppppPPPpP64.010.016.010.048.020.012.020.030.015.020.035.018.021.012.049.08.002.006.004.0005.005.003.007.08.002.006.004.0005.005.003.007.02P其两步转移概率矩阵为由于星期四下雨意味着过程说处的状态为０或１，因此星期一、星期二连续下雨，星期四下雨的概率为61.012.049.0)2(01)2(00ppp例4设质点在线段[1,4]上作随机游动，假设它只能在时刻nT发生移动，且只能停留在1,2,3,4点上。当质点转移到2,3时，它以1/3的概率向左或向右移动一格，或停留在原处。当质点移动到点1时，它以概率1停留在原处。当质点移动到点4时，它以概率1移动到点3。若以nX表示质点在时刻n所处的位置，则{,}nXnT是一个齐次马尔可夫链，其转移概率矩阵为10001/31/31/3001/31/31/30010P各状态之间的转移关系及相应的转移概率如图4.2所示。例6生灭链。观察某种生物群体，以nX表示在时刻n群体的数目，设为i个数量单位，如在时刻n+1增生到i+1个数量单位的概率为ib，减灭到i-1个数量单位的概率为ia，保持不变的概率为1()iiirab，则{,0}nXn为齐次马尔可夫链，{0,1,2,}I，其转移概率为,1,,1iijiibjiprijaji0(0)a，称此马尔可夫链为生灭链。某计算机房的一台计算机经常出故障,研究者每隔15