1、BUPT第10章 马尔可夫链 1906 1906年，俄国伟大数学家年，俄国伟大数学家A.MarkovA.Markov马尔可夫马尔可夫(1856(18561922)1922)在他的在他的大数定律关于相依变量的扩展大数定律关于相依变量的扩展一文中，一文中，第一次提到一种如同锁链般环环相扣的随机变量序列，其第一次提到一种如同锁链般环环相扣的随机变量序列，其中某个变量各以多大的概率取什么值，完全由它前面的一中某个变量各以多大的概率取什么值，完全由它前面的一个变量来决定，而与它更前面的那些变量无关个变量来决定，而与它更前面的那些变量无关.或者说是或者说是仅仅是站在仅仅是站在“今天今天”的角度上憧憬的角度
2、上憧憬“将来将来”、而不管、而不管“昨昨天天”的历史是多么的辉或者沮丧的历史是多么的辉或者沮丧.这就是所谓的这就是所谓的马尔可夫马尔可夫过程过程.1BUPT21.1 马尔可夫链的概念BUPT31.1 马尔可夫链的概念BUPT41.1 马尔可夫链的概念BUPT51.1 马尔可夫链的概念BUPT61.1 马尔可夫链的概念BUPT71.1 马尔可夫链的概念BUPT81.1 马尔可夫链的概念BUPT91.1 马尔可夫链的概念BUPT101.1 马尔可夫链的概念0,61,6jiijiji，BUPT111.1 马尔可夫链的概念BUPT121.1 马尔可夫链的概念BUPT131.1 马尔可夫链的概念 下面我
3、们给出几个马尔可夫实际应用的例子，下面我们给出几个马尔可夫实际应用的例子，并提出在应用中常常需要解决的问题并提出在应用中常常需要解决的问题,在后面的我们在后面的我们会逐一解决会逐一解决.BUPT141.1 马尔可夫链的概念BUPT151.1 马尔可夫链的概念BUPT161.1 马尔可夫链的概念0.930.010.020.0400000.94000.020.040000.9500.0100.040000.9700.010.02100000010000001000000BUPT171.2 马尔可夫链的多步转移概率BUPT181.2 马尔可夫链的多步转移概率BUPT191.2 马尔可夫链的多步转移概
4、率BUPT201.3 马尔可夫链的有限维分布BUPT211.3 马尔可夫链的有限维分布BUPTBUPT22221.3 1.3 马尔可夫链的有限维分布马尔可夫链的有限维分布例例:设设Xn,n0Xn,n0是具有三个状态是具有三个状态0 0，1 1，2 2的齐次马的齐次马氏链，一步转移概率矩阵为氏链，一步转移概率矩阵为 4/14/304/12/14/104/14/3210210P初始分布初始分布q qi i(0)=PX(0)=PX0 0=i i=1/3,=1/3,i i=0,1,2.=0,1,2.试求试求(1)PX(1)PX0 0=0,X=0,X2 2=1=1；(2)PX(2)PX2 2=1.=1.
5、20125/85/161/160(2)5/161/23/1613/169/161/42PP解解:先求出二步转移概率矩阵先求出二步转移概率矩阵 BUPT231.3 马尔可夫链的有限维分布于是于是 020200011 0,1010 02|153 16P XXP XP XXqp 2001111221(2)10202021519113 1621624P XqpqpqpBUPT244 平稳分布 定义定义 设马尔可夫链的状态空间为设马尔可夫链的状态空间为E E，如果对于所有的，如果对于所有的i i,j j E E,转移概率转移概率p pijij(n),(n),当当nn时，存在不依赖时，存在不依赖于于i i
6、的极限的极限 jnijnp=lim)(则称此则称此链具有遍历性链具有遍历性，又若，又若 ,称称 =(=(0 0,1 1,),)为链的为链的极限分布极限分布。1 jj 010101()jjnnjP nP 或BUPT254 平稳分布BUPT264 平稳分布 定理定理 设齐次马氏链设齐次马氏链X Xn n,n,n 0 0的状态空间为的状态空间为E E，如果如果存在存在正整数正整数m m，都有，都有 P Pijij(m)0,(m)0,i i,j ,j=1,N=1,N，则此链具有遍历性则此链具有遍历性，且有极限分布，且有极限分布=(=(1 1,2 2,N N).).BUPTBUPT27274 4 平稳分
7、布平稳分布例例:设齐次马氏链具有设齐次马氏链具有三个状态，一步转移概率矩阵为三个状态，一步转移概率矩阵为 pqpqpqP000其中其中0p1,q=1-p,0p1,q=1-p,试证该链是遍历的，并求其极限分布。试证该链是遍历的，并求其极限分布。解解:显然，显然，m=1m=1时，定理条件不满足。时，定理条件不满足。m=2m=2时时(2)2PPqpqpqqppqqppqpqq2222222pqpqpqpqpqpq000000再根据定理，极限分布再根据定理，极限分布 满足的方程组满足的方程组 ),(321BUPTBUPT28284 4 平稳分布平稳分布1321323312211ppqpqq解得解得 p
8、=q=1/2p=q=1/2时，时，1 1=2 2=3 3=1/3.=1/3.p pq q时时3,2,1,)()(1113jqpqpqpjj 例例 设一马氏链的一步转移概率矩阵为设一马氏链的一步转移概率矩阵为 02/102/12/102/1002/102/12/102/10P试讨论它的遍历性。试讨论它的遍历性。BUPTBUPT29294 4 平稳分布平稳分布解解:已知已知(2)21/201/2001/201/21/201/2001/201/2PP(3)3PPP 02/102/12/102/1002/102/12/102/10P)(limnpijn 这表明对任一固定的这表明对任一固定的 j j(=
9、1,2,3,4)(=1,2,3,4)，极限，极限 都不存在。按定义，此链不具遍历性。都不存在。按定义，此链不具遍历性。可得：可得：BUPTBUPT30304 4 平稳分布平稳分布例例:设齐次马氏链具有三个状态，初始分布为设齐次马氏链具有三个状态，初始分布为0.250.25，0.250.25，0.5 0.5 一步转移概率矩阵为一步转移概率矩阵为 1 1）试证该链是遍历的，并求其极限分布；）试证该链是遍历的，并求其极限分布；2 2）求概率）求概率P=13044111P=42413044.013P(1,1,2).XXX.解解:显然，显然，m=1m=1时，定理条件不满足。时，定理条件不满足。m=2m=
10、2时时BUPT314 平稳分布(2)2493161616385.1616161510161616PP再根据定理，极限分布再根据定理，极限分布 满足的方程组满足的方程组 0121PBUPT324 平稳分布0011012212012114431142413441解得解得012133,.777(2)013011121155P(1,1,2)Pr(1).42161282XXXXp p）BUPT334 平稳分布BUPT344 平稳分布BUPT354 平稳分布BUPT364 平稳分布BUPT374 平稳分布BUPT384 平稳分布BUPT394 平稳分布BUPT404 平稳分布BUPT本章作业P1901，2，3，5，6，7，10，11 第五章思维导图42BUPT
