随机过程-第五章-马尔可夫链

-1-第五章马尔可夫链有一类随机过程，它具备所谓的“无后效性”（Markov性），即要确定过程将来的状态，知道它此时刻的情况就足够了，并不需要对它以往状况的认识，这类过程称为Markov过程。Markov过程的两类基本类型包括离散时间Markov链和连续时间Markov链。注：以下几节我们首先讨论的离散时间Markov链，简称Markov链。5.1基本概念定义5.1Markov链：随机过程{,0,1,2,}nXn称为Markov链，若它只取有限或可列个值012,,,EEE，这个可能取值的集合将以非负整数集{0,1,2,}来表示。{0,1,2,}或其子集记为S，称为过程的状态空间。若nXi，就说过程在时刻n时刻处于状态i，假设每当过程处于状态i，则在下一时刻将处于状态j的概率是固定的ijP。对任意的0n及一切状态011,,,,,niiiij有11111001{,,,,}{}nnnnnnPXjXiXiXiXiPXjXi这样的随机过程称为Markov链。概率方程可解释为，对Markov链，给定过去的状态011,,,nXXX及现在的状态nX，将来的状态1nX的条件分布与过去的状态独立，只依赖于现在的状态，这称为Markov性。定义5.2转移概率：定义5.1中的条件概率1{}nnPXjXi代表处于状态i的过程下一步转移到状态j的概率，称为Markov链{,0,1,2,}nXn的一步转移概率，简称为转移概率。注：一般情况下，转移概率1{}nnPXjXi与状态,ij及时刻n有关。注：由定义5.1中的概率方程可进一步推导得到如下方程111100111122110000{,,,,}{}{}{}{}nnnnnnnnnnPXiXiXiXiPXiXiPXiXiPXiXiPXi显然，Markov链的统计特征由其初始分布00{}PXi和转移概率11{}kkkPXiXi（1,2,,kn）决定。定义5.3时齐Markov链：当Markov链的转移概率1{}nnPXjXi只与状态,ij有关，而与时刻n无关时，称Markov链为时齐的，并记1{}ijnnPPXjXi；否则，说-2-就称之为非时齐的。注：本课程的讨论仅限于时齐Markov链，并简称为Markov链。转移概率ijP的性质：（1）0,,ijPijS；（2）1,ijjSPiS。以P记转移概率ijP的矩阵，则有000102101112202122PPPPPPPPPP定义5.4随机矩阵：若一矩阵中的元素满足两条性质：（1）0,,ijPijS；（2）1,ijjSPiS。则称该矩阵为随机矩阵。显然，随机矩阵的各行元素之和都等于1。例5.1赌徒输光问题：考虑一赌徒，在每局赌博中他以概率p赢得1元，以概率1qp输掉1元，假设各局赌博是相互独立的，赌徒开始有i（0in）元，且他在赌金为0（输光）或为n元时停止。这一过程的状态为{0,1,2,,}Sn，其转移概率00,1,11,,,1,2,1nniiiiPPPpPqin(1)(1)10000000000000000000000001nnqpqPpqp定义5.5n步转移概率：定义n步转移概率nijP为处于状态i的过程经过n次转移后处于状态j的概率，即{},,,0,1nijmnmPPXjXiijSmn-3-相应地，n步转移概率矩阵记为()nP。其中，(1)ijijPP；且规定00,1,ijijPij。在计算n步转移概率方面切普曼-柯尔莫哥洛夫方程（Chapman-Kolmogorov方程，简称C-K方程）提供了相应的方法。定理5.1C-K方程：对一切,0,,nmijS，有（1）mnmnijikkjkSPPP（2）()()()mnmnPPP（1）证明：00000000000{,}{}{}{,,}{}{,,}{,}{}{,}{,}{}mnmnijmnmnmkSmnmmkSmmnmmkSMarkovmnikkjkSPXjXiPPXjXiPXiPXjXkXiPXiPXjXkXiPXkXiPXiPXkXiPXjXkXiPXkXiPP全概率公式链的定义（2）证明：（2）是（1）的矩阵形式。由（2）的结论可推得()(1)nnnPPPP例5.2赌徒输光问题（例5.1）：设例5.1中赌徒从2元赌金开始赌博，3n（即当赌金为0或3元时停止赌博），12pq。求他经过4次赌博之后输光的概率。解：根据题设要求求解42040{02}PPXX。首先写出一步转移矩阵4410001100221100220001P利用C-K方程（2）的方法得到-4-(4)410005150816161501651800160PP故420405{02}16PPXX。例5.3广告效益的推算P82某种鲜奶A改变了广告方式，经调查发现买A种鲜奶及另外三种鲜奶B,C,D的顾客每两个月的平均转换率（假设市场只有此四种鲜奶）如下：,95%;,2%;,2%;,1%,30%;,60%;,6%;,4%,20%;,10%;,70%;,0%,20%;,20%;,10%;,50%AABCDBABCDCABCDDABCD假设当前四种鲜奶的市场份额为(,,,)(25%,30%,35%,10%)ABCDvvvv，试求半年后鲜奶的市场份额。解：根据题设首先可写出一步转移概率矩阵0.950.020.020.010.30.60.060.040.20.10.700.20.20.10.5P利用C-K方程计算得到半年后的转移概率矩阵(3)30.88940.04580.04660.01820.601750.25590.09880.043550.48340.13880.365840.011960.50090.21340.142640.14306PP结合市场份额可进一步计算得到半年后的鲜奶市场份额(3)'(0.624,0.15814,0.183318,0.034542)P对比半年前后的市场份额可发现，A种鲜奶的广告效益明显。5.2状态分类及性质定义5.6互通：若存在0n使得0nijP，则称状态i可达状态j（,ijS），记为ij；若同时有状态ji，则称两种状态是互通的，记为ij。命题5.1互通是一种等价关系，即-5-（1）自返性，ii；（2）对称性，ij，则ji；（3）传递性，,ijjk，则ik。证明：（1）（2）可从互通的定义直接得到。为证明（3），假设,ijjk，则存在,0mn使得0,0mnijjkPP，利用C-K方程（1）可知0mnmnmnikirrkijjkrSPPPPP类似地可以证明存在0K使得0KkiP。称互通的两个状态属于同一个类，且由命题5.1可知，任何一个状态不能同时属于两个不同的类，即任意两个不同的类不相交。思考：对例5.1中的赌徒问题的状态分类？定义5.7可约：若Markov链只存在一个类，则称它为不可约的；否则称为可约的。在不可约的Markov链中，一切状态都是彼此互通的。定义5.8闭集：一个状态集合S称为闭集，若对,iSjS，0ijP。即一旦进入某个闭集，就永远停留在此闭集中。一个不可约的Markov链的状态空间就是链中唯一的闭集。以下我们给出状态的一些性质，并对同类的状态的同质性加以证明。定义5.9周期性：若集合{:1,0}niinnP非空，则称它的最大公约数()ddi为状态i的周期。若1d，则称i是周期的；若1d，则称i是非周期的。若集合{:1,0}niinnP为空集，则称i的周期为无穷大。注：不是对于所有的,1,2,kdk都有0kdiiP。例5.4考察Markov链的周期如图所示，由状态1出发再回到状态1的可能步长为（4，6，8，10，…），它的最大公约数为2。尽管从状态1出发经2步并不能回到状态1，但我们仍然称2是状态1的周期。命题5.2若状态,ij属于同一类，则()()didj。证明：由类的定义可知ij，即存在,0mn使得0,0mnijjiPP，则426831957-6-0mnmnmniiikkiijjikSPPPPP对所有使得0sjjP的s，有0msnmnsmnsmsnmsniiikkiijjiijjkkiijjjjikSkSPPPPPPPPPPP因此，()di可被mn和mns整除，则()di可被s整除（()()()nmsnmsdididi）；而s显然可以整除()dj（0sjjP）。类似地可以证明，对所有使得0tiiP的t同样可同时整除()di和()dj。接下来证明()()didj。假设()()didj，不妨假设()()didj（对立假设也可以，但对结论不影响）。因对所有使得0tiiP的t可同时整除()di和()dj，根据最大公约数为周期的周期性定义可知，()dj为状态i的周期，这与()di为状态i的周期相矛盾；若假设()()didj，则可证明与()dj为状态j的周期矛盾。因此，假设()()didj不成立，则有()()didj。（请同学位对比书中有关此命题的证明，我个人认为其证明不充分）定义5.10常返性（滑过）：对任何状态i和j，定义nijf是从i出发在时刻n首次转移到j的概率，则有000{,,1,2,,1},1ijnijnkffPXjXjknXin令1nijijnff则ijf表示过程从i出发迟早转移到j的概率。若1jjf，则称状态j是常返的；若1jjf，则称状态j为非常返的或为滑过的（瞬过状态，以概率1jjf从j滑过）。注：对ij，ijf为正的当且仅当从状态i可达状态j。对于常返态i，定义1niiinnf表示由i出发再返回i所需的平均时间（步长）。命题5.3状态i为常返的当且仅当0niinP若状态i为非常返的，则有-7-011niiniiPf因而此时有lim0niinP。为证明命题5.3，我们需要引入下面的引理。引理5.1对任意状态,ij及1n，有1nlnlijijjjlPfP证明：用归纳法证，此略。命题5.3的证明：利用引理5.1，则有00111110011()1()()1()nnlnliiiiiiiinnllnliiiilnllnliiiilnllmiiiilmmiiiimPPfPfPfPfPfP转换求和次序因此011niiniiPf从而001;1nniiiiiiiinnPfPf收敛利用数列极限的知识可知，当0niinP收敛时，有lim0niinP。命题5.3的解释：若过程以概率1从状态i出发并最终回到i，则状态i是常返的，由Markov性可知，回到状态i后在概率上过程就重新开始了。因此，总是可以以概率1再回到状态i。可见以概率1到达状态i的次数是无限的，因而其期望也是无限的。另一方面，如果状态i是滑过的，则每当过程回到状态i，将有一个正概率1iif使得过程永远不再回到状态i，因此到达i的次数是具有有限均值11iif的几何分布的变量。-8-注：命题5.3的结论同时也证明：一个滑过状态只能到达有限次，则有限状态的Markov链不可能全部状态都是滑过的。关于这一结论的解释如