马尔科夫链.pdf

1 第第1313章马尔科夫链章马尔科夫链 （（Markov Chains）） 2 1 1 随机过程的基本概念随机过程的基本概念 在不少随机现象中，不仅需考虑在某一时在不少随机现象中，不仅需考虑在某一时 刻下的系统状态，而且要研究该刻下的系统状态，而且要研究该系统状态随时系统状态随时 间推移而发生的发展变化过程间推移而发生的发展变化过程。。 例如卡车装运系统例如卡车装运系统 电话交换系统电话交换系统 城市交通交叉路口城市交通交叉路口 3 随机现象发展变化过程如何进行描述 某固定时刻某固定时刻t下随机现象状态的描述下随机现象状态的描述 随机变量随机变量 当当t在某时间区间内连续发生变化时，单个或多个在某时间区间内连续发生变化时，单个或多个 随机变量不足以表示随机现象的发展变化过程。随机变量不足以表示随机现象的发展变化过程。 则当则当t在某区间在某区间a，，b内连续变化时，必须内连续变化时，必须 用一族无限多个随机变量来描述。这用一族无限多个随机变量来描述。这一族无限多一族无限多 个随机变量的总称就是个随机变量的总称就是随机过程随机过程。。 4 函数概念与随机过程概念的对比函数概念与随机过程概念的对比 确定性现象中确定性现象中 随时间随时间t变化的一族数值变化的一族数值 构成函数构成函数Yt，每个固定，每个固定 值值t确定一个数值确定一个数值Y。。 t的变化范围称定义域，的变化范围称定义域， Yt的取值范围称值域。的取值范围称值域。 随机性现象中随机性现象中 随时间随时间t变化的一族随机变量变化的一族随机变量 构成构成随机过程随机过程Yt，每个固，每个固 定值定值t确定一个确定一个随机变量随机变量Y。。 t的取值范围的取值范围T称称参数集参数集，， Yt的取值范围的取值范围E称称状态空状态空 间间。。 因此，随机过程可以看作依赖于时间因此，随机过程可以看作依赖于时间t t的的 由随机变量构成的函数。由随机变量构成的函数。 5 随机过程的描述符号随机过程的描述符号｛｛Yt，，t∈∈T } 随机过程的定义随机过程的定义 设设T为参数集，若对于每一个为参数集，若对于每一个t∈∈T，均有一，均有一 个随机变量个随机变量Yt与其对应，则将这一族依赖与其对应，则将这一族依赖 于于t的随机变量的全体称为的随机变量的全体称为随机过程随机过程，，记作记作 ｛｛Y（（t，，t∈∈T｝｝，，或简记作或简记作YT。。 6 如如泊松过程泊松过程属属T连续，连续，E离散的平稳过程。离散的平稳过程。 马尔可夫链马尔可夫链是是T和和E均离散的马尔可夫过程。均离散的马尔可夫过程。 随机过程的分类 按照参数集（按照参数集（T）和状态空间（）和状态空间（E）的类型，可分为）的类型，可分为 离散参数链离散参数链,非离散参数链非离散参数链,随机序列随机序列,随机函数随机函数 根据概率结构，随机过程可以划分为根据概率结构，随机过程可以划分为 独立增量过程，平稳过程，非平稳过程，马尔可夫过独立增量过程，平稳过程，非平稳过程，马尔可夫过 程等程等 7 2 2 随机过程的模拟随机过程的模拟 随机过程模拟的实质随机过程模拟的实质 随机变量模拟的实质随机变量模拟的实质 通过计算机获取随机变量的样本，在一次通过计算机获取随机变量的样本，在一次 实验中表现为一个数值。实验中表现为一个数值。 通过计算机实验获取随机过程的通过计算机实验获取随机过程的一个样本函一个样本函 数数。。 8 3 泊松过程（泊松流）及其模拟泊松过程（泊松流）及其模拟 3.1 泊松流的概念泊松流的概念 ...2 , 1 , 0, 0 − ke k kxP k λ λ λ 泊松流泊松流即泊松即泊松过程过程常常用来描述一个随机用来描述一个随机质点流质点流 的状态变化过程。的状态变化过程。 随机随机质点流指源源质点流指源源不不断地断地随机随机地到达地到达某某目标目标的的一一 串质点串质点，如，如到商场到商场的的顾客流、到达工厂顾客流、到达工厂的定单的定单 流流，，网络上到达网络上到达某某节点节点的数的数据流等据流等。。 单单位位时间内时间内到达目标到达目标的的泊松流质点泊松流质点数数目服从泊松目服从泊松 分布分布 9 {Tn,n＝＝1,2,}则描述了随着到达次序的变化，相继到则描述了随着到达次序的变化，相继到 达目标的两质点到达时间间隔的变化过程。达目标的两质点到达时间间隔的变化过程。 Nt[0,t]时间内，到达某目标的质点数；时间内，到达某目标的质点数； Sn第第n个质点到达目标的时刻个质点到达目标的时刻n＝＝1，，2，，；； Tn第第n个质点与其前一质点的相继到达个质点与其前一质点的相继到达间隔时间间隔时间。。 描述泊松流概率特征的符号 {Nt,t≥≥0｝｝描述了随着描述了随着t的变化，在的变化，在[0,t]时间区间内到达时间区间内到达 目标质点数的变化过程；目标质点数的变化过程； {Sn,n＝＝1,2,}描述了随着到达目标的先后次序，质点到描述了随着到达目标的先后次序，质点到 达时刻的变化过程；达时刻的变化过程； 10 3.2 泊松流的泊松流的特征及其特征及其性质性质 n 泊松流概率特征泊松流概率特征 1独立性独立性在互不相交的时间区间内到达目标的质在互不相交的时间区间内到达目标的质 点数是相互独立的；点数是相互独立的； 2平稳性平稳性对于充分小的△对于充分小的△t＞＞0，在时间区间，在时间区间[t,t＋＋ △△t]内有一个质点到达目标的概率与时间起点内有一个质点到达目标的概率与时间起点t无无 关，而仅与△关，而仅与△t长度成正比；长度成正比； 3普遍普遍性性对于充分小的△对于充分小的△t＞＞0，在时间区间，在时间区间[t,t＋＋ △△t]内有一个以上质点到达目标的概率几乎为内有一个以上质点到达目标的概率几乎为0。。 n 泊松流的基本性质泊松流的基本性质 强度强度为为λ的泊松流，的泊松流，其相邻其相邻 质质点点到达间到达间隔时隔时间间服从服从参数为参数为λ的的负指负指数分数分布布。。 11 3.3 泊松流的模拟泊松流的模拟 泊松流的模拟，其实质就是要通过计算机获取泊泊松流的模拟，其实质就是要通过计算机获取泊 松流的样本函数。由泊松流的特性可知，泊松流的松流的样本函数。由泊松流的特性可知，泊松流的 样本函数均是样本函数均是跃度为跃度为1的的递增阶梯函数递增阶梯函数。。 12 泊松流模拟方法一 基于泊松流的特征基于泊松流的特征 平稳性平稳性在时间区间在时间区间[t,t∆t]内，到达质点的平均数为内，到达质点的平均数为λ∆t；； 普遍普遍性性则在时间区间则在时间区间[t,t∆t]内，质点的到达成为简单事内，质点的到达成为简单事 件，有一个质点到达的概率为件，有一个质点到达的概率为λ∆t，没有质点到达的概率为，没有质点到达的概率为 1- λ∆t；； 独立性独立性则整个时间段内顾客的到达成为若干相互独立的则整个时间段内顾客的到达成为若干相互独立的 简单事件的总和。简单事件的总和。 因此，逐个考察各因此，逐个考察各∆t子区间内质点到达与否子区间内质点到达与否 即可获取泊松流在即可获取泊松流在[0，，T]内的一列到达时刻，进内的一列到达时刻，进 而得到泊松流的一个样本函数。而得到泊松流的一个样本函数。 13 基于模拟方法一的模拟抽样流程 14 泊松流模拟方法二 根据泊松流的基本性质，各质点的相继到达根据泊松流的基本性质，各质点的相继到达 时间间隔时间间隔t1，，t2，，是相互独立且服从同一参是相互独立且服从同一参 数数λλ的的负指数分布负指数分布，而负指数分布随机数由计算，而负指数分布随机数由计算 机抽样获得，进而可以计算各质点的到达时刻，机抽样获得，进而可以计算各质点的到达时刻， 得到泊松流的一个样本函数。得到泊松流的一个样本函数。 λ 1 15 基于模拟方法二的模拟抽样流程基于模拟方法二的模拟抽样流程 λ- 1 t ，，t0 16 4. 马尔科夫链马尔科夫链 1、马氏链的基本概念、马氏链的基本概念 2、齐次马氏链的模拟、齐次马氏链的模拟 3、应用举例、应用举例 17 4.1马马氏氏链的链的基基本概念本概念 研究随机过程的主要目的之一是用来预测未来。研究随机过程的主要目的之一是用来预测未来。 现以逐日考察的气象预报为例，当设现以逐日考察的气象预报为例，当设xt表示表示t时刻时刻 广州天气的状态，并以广州天气的状态，并以0、、1、、2、、3分别代表四种气分别代表四种气 候状态雨天、晴天、阴天、多云，即有候状态雨天、晴天、阴天、多云，即有xt0表表 示示t时刻广州为雨天；时刻广州为雨天；xt1表示表示t时刻广州为晴天；时刻广州为晴天； xt2表示表示t时刻广州为阴天；时刻广州为阴天；xt3表示表示t时刻广州时刻广州 为多云。则当为多云。则当t取取0、、1、、2、、、、365时，时，xti就表就表 示了自今天开始以后的一年中广州每天天气的状态示了自今天开始以后的一年中广州每天天气的状态i （（i0、、1、、2、、3）。于是随机过程）。于是随机过程{xt,t0,1,2,} 就描述了自今天开始以后的一年中广州天气的变化就描述了自今天开始以后的一年中广州天气的变化 过程。显然此随机过程有离散状态空间过程。显然此随机过程有离散状态空间E{0，，1，， 2，，3}与离散参数集（时间集）与离散参数集（时间集）T{0，，1，，2，，}，， 故它是时间离散、状态离散的链。故它是时间离散、状态离散的链。 18 为了进行天气预报，人们通常关心的是在为了进行天气预报，人们通常关心的是在 过去和当前的气候状态已知条件下来预测将过去和当前的气候状态已知条件下来预测将 来的天气状态。若以表来的天气状态。若以表t今天，今天，s表明天表明天 （（st），），A表过去所处的气候状态，则由积表过去所处的气候状态，则由积 累的气象资料来获得条件概率分布列累的气象资料来获得条件概率分布列 P{xsj|xti,A} 是十分需要的。因为它表示了在过去状态为是十分需要的。因为它表示了在过去状态为 A、当前（今天）状态为、当前（今天）状态为i已知的条件下，将已知的条件下，将 来（明天）状态为的可能性（其中来（明天）状态为的可能性（其中i与与j均可取均可取 0，，1，，2，，3中的任一种）。中的任一种）。 19 例如若已知有例如若已知有 P{xs0|xti,A}0.8 P{xs1|xti,A}0.1 P{xs2|xti,A}0.05 P{xs3|xti,A}0.05 则人们当然可以预言明天的气候状态为则人们当然可以预言明天的气候状态为0（雨（雨 天）。天）。 20 一般情况下，当当前状态已知的条件下，一般情况下，当当前状态已知的条件下， 将来的状态可能与过去所处的状态将来的状态可能与过去所处的状态A有关，有关， 也可能无关。若随机过程也可能无关。若随机过程{xt,t0,1,2,}的条的条 件概率满足关系式件概率满足关系式 P{xsj|xti,A} P{xsj|xti} 对任何对任何st及及i∈∈E，，j∈∈E成立，即与过去状成立，即与过去状 态态A无关，则称该随机过程为无关，则称该随机过程为马氏链马氏链，并将，并将 上述特性成为上述特性成为马氏链性马氏链性或或无后效性无后效性。。 21 马氏性指出了这样一个事实马氏性指出了这样一个事实“如果我们知如果我们知 道了系统在任一时刻的状态，就以此预测从道了系统在任一时刻的状态，就以此预测从 这以后的任何未来时刻的状态变化过程，至这以后的任何未来时刻的状态变化过程，至 于在这以前，系统是怎样到达此状态的经历于在这以前，系统是怎样到达此状态的经历 是无关紧要的。是无关紧要的。”或简单地说或简单地说“给定现在，将给定现在，将 来与过去独立来与过去独立”，这就是马氏链的本质特性。，这就是马氏链的本质特性。 自然科学与社会科学的很多现象都具有上述自然科学与社会科学的很多现象都具有上述 特性，如仓库前卡车排队长度的变化过程，特性，如仓库前卡车排队长度的变化过程， 产品销售的变化过程等。产品销售的变化过程等。 22 在马氏链在马氏链{xt,t0,1,2,}中当中当st1时，条件概率时，条件概率 P{xt1j|xti}，一般来说不仅依赖于状态，一般来说不仅依赖于状态i与与j，， 而且依赖于而且依赖于当当前前时刻时刻t，但，但若若该该马氏链马氏链的的条件条件概率与概率与 当当前前时刻时刻t无无关关，则称此特殊的马氏链为，则称此特殊的马氏链为齐次马氏齐次马氏 链链，或者说该马氏链是齐次的。马氏链的齐次性反，或者说该马氏链是齐次的。马氏链的齐次性反 映了这样一个事实映了这样一个事实无论从什么时刻开始，系统未无论从什么时刻开始，系统未 来的状态变化过程的统计规律总是一致的。来的状态变化过程的统计规律总是一致的。 在其次马氏链在其次马氏链{xt,t0,1,2,}中，由于条件概率中，由于条件概率 P{xt1j|xti,A} 与过去历史与过去历史A无关，与当前时刻无关，与当前时刻t无关，从而只与当无关，从而只与当 前时刻前时刻t所处的状态所处的状态i以及将来（明天或其他）状态以及将来（明天或其他）状态j 有关，故可以简记为有关，故可以简记为 PijP{xt1j|xti,A} 其中其中i和和j可取状态空间可取状态空间E中任一状态，中任一状态， 23 如天气预报中如天气预报中i与与j可取可取0、、1、、2、、3中的任一状态。中的任一状态。 若将中若将中Pij中中i与与j所取的状态一一列举出来，并按照一所取的状态一一列举出来，并按照一 定的次序排列起来，可得定的次序排列起来，可得 称为齐次马氏链的称为齐次马氏链的转移矩阵转移矩阵（更确切地说是一步转（更确切地说是一步转 移矩阵，其移矩阵，其“一步一步”的含义是由于有的含义是由于有st1，即将来与，即将来与 现在时刻仅差一个单位）。现在时刻仅差一个单位）。 P 000102 03 10111213 20212223 30313233 P P P P P P P P P P P P P P P P       24 在此转移矩阵在此转移矩阵P中，第一行元素中，第一行元素000102 03P P P P 表征了在当前状态为表征了在当前状态为0的状态下，未来状态分别取的状态下，未来状态分别取0，， 1，，2，，3的概率。考虑到未来状态亦只能取这四个状态的概率。考虑到未来状态亦只能取这四个状态 中的一个，故应有中的一个，故应有 000102 03P P P P 1 同样，转移矩阵同样，转移矩阵P中的第二行元素中的第二行元素10111213P P P P 表征了在当前状态为表征了在当前状态为1的条件下，未来状态分别取的条件下，未来状态分别取0，，1，， 2，，3的概率，其余类推。的概率，其余类推。 25 与前与前同理同理，，应应有有关系式关系式 显然，若我们将天气状态的变化过程显然，若我们将天气状态的变化过程 {xt,t0,1,2,}理想地看作齐次马氏链的话，只要理想地看作齐次马氏链的话，只要 给出了转移矩阵，则无论当前的状态给出了转移矩阵，则无论当前的状态i取取0，，1，，2，，3 中的哪一个，均可以从转移矩阵中的哪一个，均可以从转移矩阵P中找出相应的一中找出相应的一 行来进行比较，从而得到预测值。行来进行比较，从而得到预测值。 10111213P P P P 20212223P P P P 30313233P P P P 1 1 1 26 4.2 齐齐次马次马氏氏链的模拟链的模拟 齐次马氏链齐次马氏链{xt,t0,1,2,}中的一列随机变量中的一列随机变量x0, x1, x2,如果是相互独立的话，我们就可以按照上一节的如果是相互独立的话，我们就可以按照上一节的 方法将每个随机变量独立地逐个进行模拟，并获取其样方法将每个随机变量独立地逐个进行模拟，并获取其样 本值。但事实上问题并非如此简单，原因在于马氏链的本值。但事实上问题并非如此简单，原因在于马氏链的 各个随机变量各个随机变量xl与与xh之间并非是相互独立的之间并非是相互独立的 （（l≠≠h），而是满足一定的相依关系），而是满足一定的相依关系- - - 马氏链马氏链。但好在。但好在 这种马氏性所满足的这种马氏性所满足的相依关系是比较微弱的相依关系是比较微弱的，它只要求，它只要求 每一时刻每一时刻s的状态仅依赖于上一时刻的状态仅依赖于上一时刻ts- 1的状态，即的状态，即 xn1依赖于依赖于xn，，xn依赖于依赖于xn- 1，，，，x2依赖于依赖于 x1，，x1依赖于依赖于x0，因此为获取齐次马氏链的一个样，因此为获取齐次马氏链的一个样 本，只需要由本，只需要由t0时的初始状态时的初始状态x0i0及转移矩阵及转移矩阵P来决来决 定定x1之样本之样本i1,再由再由i1及及P来决定来决定x2之样本之样本i2，由，由in及及P来来 决定决定xn1的样本的样本in1 27 根据根据上上述述设想设想，，对对一个一个具具有有状态空间状态空间E{0，，1，， 2，，}的的转移矩阵转移矩阵 的齐次马氏链的齐次马氏链{xt,t0,1,2,}实施模拟的具体步骤实施模拟的具体步骤 如下如下 （（1）设）设x0由初始状态由初始状态i0，即，即x0i0。。 （（2）求）求x1的样本的样本R1。考虑到状态。考虑到状态x0i0已发生，已发生， 故在故在 x0i0已发生的条件下已发生的条件下x1的条件分布列的条件分布列 P{x1j|x0 i0}Pi0jj0,1,2, P 0001020m 1011121m m0m1m2mm P P P P P P P P P P P P       28 是已知的，这只须从矩阵 P 00 nnn 0 00 10 m i0i11 m i0i1im m 0m 1m m P P P P P P P P P P P P            的第的第i0行取出各元素行取出各元素000i 0i 1i mP P P即可。即可。 29 有有了了x1的的条条件件分分布布列，列，就就可以可以直接直接按照按照上上一一节节对对 离散型随机变量的一离散型随机变量的一般般模拟模拟法法来来求求取取x1的样本值的样本值i1。。 其其具体做法具体做法为为首首先先取取伪伪随机数随机数u1，，然然后后选选取数取数i1，，使满使满 足不足不等等式式 于是有于是有x1的样本的样本R1 i1。。 1 11 00 010 ii jj PijPiju − ≤∑∑ ⑶求⑶求x2的样本的样本R2。与上同理，由于。与上同理，由于x1 i1已发生，已发生， 故在故在x1 i1已发生条件下已发生条件下x2 的条件分布列是已知的，的条件分布列是已知的， 这只须从转移矩阵这只须从转移矩阵P中取出第中取出第i1行的全部元素行的全部元素 11i 0i 1P P 即可，然后按照对离散型随机变量的一般模拟法来求取即可，然后按照对离散型随机变量的一般模拟法来求取 x2的样本值。的样本值。 30 即首即首先先选选取随机数取随机数u2，，然然后后选选取数取数i2，，使满足使满足 不不等等式式 于是有于是有x2的样本的样本R2 i2。。 2 12 00 121 ii jj Pi jPi ju − ≤∑∑ 31 ⑷求⑷求x3的样本的样本R3。反复运用上述步骤，即可获。反复运用上述步骤，即可获 得齐次马氏链得齐次马氏链{xt,t0,1,2,}在具有初始状态在具有初始状态i0 条件下的一组样本值条件下的一组样本值i0，，i1，，i2。。 若以初始时刻若以初始时刻t0表示今天，表示今天，x0 i0表示已知表示已知 的今天天气状态，的今天天气状态，xt,t0,1,2,表示明天、后表示明天、后 天、大后天天、大后天的天气状态，则利用上述方法对的天气状态，则利用上述方法对 齐次马氏链齐次马氏链{xt,t0,1,2,}实施模拟求得之一组实施模拟求得之一组 样本值样本值i0，，i1，，i2即为广州天气在今天以后一即为广州天气在今天以后一 段时期状态的预报。段时期状态的预报。 32 最后需要说明的是使上述的一组样本值是在初最后需要说明的是使上述的一组样本值是在初 始状态始状态x0 i0已确定的情况下获得的，如果初始已确定的情况下获得的，如果初始 状态状态x0亦为随机变量，则只要给出亦为随机变量，则只要给出x0的初始分的初始分 布列布列P{ x0i}Pi，，i0，，1，，2，，，，m。于是只。于是只 要利用对离散型随机变量的一般模拟法很易获得要利用对离散型随机变量的一般模拟法很易获得 x0的样本值的样本值i0，然后再按上述步骤⑵、⑶、⑷，然后再按上述步骤⑵、⑶、⑷ 做下去即可。做下去即可。 33 3. 应用应用举举例例 某地区天气有雨、晴、阴、多云四种状某地区天气有雨、晴、阴、多云四种状 态，设明天的天气以一定的概率取决于今天态，设明天的天气以一定的概率取决于今天 的天气，其转移矩阵如图所示。试从初始状的天气，其转移矩阵如图所示。试从初始状 态为晴天开始来对该地区的今后态为晴天开始来对该地区的今后365天的气候天的气候 状态实施模拟（预报这状态实施模拟（预报这365天的气候状态），天的气候状态）， 并统计出各类天气的天数及其所占百分比。并统计出各类天气的天数及其所占百分比。 34 某地区天气转移概率表某地区天气转移概率表 0.40.10.30.2 多云多云 3 0.10.40.20.3 阴阴2 0.20.20.40.2 晴晴1 0.20.20.10.5 雨雨0 多云多云阴阴晴晴雨雨 明天明天 今天今天 35 解若气候状态雨天、晴天、阴天、多云分解若气候状态雨天、晴天、阴天、多云分 别用数字别用数字0、、1、、2、、3来代替，并设来代替，并设xti表示自表示自 今正开始以后的第今正开始以后的第t天的天气状态为天的天气状态为i，则由题意，则由题意 设知设知{xt,t0,1,2,,1000}为齐次马氏链，并有为齐次马氏链，并有 离散状态空间离散状态空间E{0,1,2,3}、离散时间集、离散时间集 T{0,1,2,,1000}及转移矩阵及转移矩阵 P 0.5 0.1 0.2 0.2 0.2 0.4 0.2 0.2 0.3 0.2 0.4 0.1 0.2 0.3 0.1 0.4       36 模拟求解 设有初始状态设有初始状态x01（晴天），运用对齐次马氏链实施模拟的（晴天），运用对齐次马氏链实施模拟的 基本步骤可设计出程序框图。图中各标识符的含义如下基本步骤可设计出程序框图。图中各标识符的含义如下 PI,J 转移矩阵转移矩阵 SII0,1,2,3 一次实验中雨天、晴天、阴天、多云四种天气累计量一次实验中雨天、晴天、阴天、多云四种天气累计量 N0一次实验中预定模拟天数（题意为一次实验中预定模拟天数（题意为365天）天） M 预定重复实验的次数（每次实验均模拟预定重复实验的次数（每次实验均模拟N0天）天） YI,M I0,1,2,3 第第M次试验雨天、晴天、阴天、多云四种天气次试验雨天、晴天、阴天、多云四种天气 的平均百分比的平均百分比 G 转移矩阵中，第转移矩阵中，第i行元素的逐次累加和行元素的逐次累加和 EI I0,1,2,3 M次试验雨天、晴天、阴天、多云四种天气的次试验雨天、晴天、阴天、多云四种天气的 平均百分比平均百分比 SMI I0,1,2,3 M次试验雨天、晴天、阴天、多云四种天气天次试验雨天、晴天、阴天、多云四种天气天 数累计量或平均量数累计量或平均量 37 理论分析理论分析 1. 马尔可夫过程的概率分马尔可夫过程的概率分布布 例例一维随机游动一维随机游动 . 21,}5 , 4 , 3 , 2 , 1{ 等时刻发生游动等时刻发生游动 秒秒秒、秒、并且仅仅在并且仅仅在上作随机游动上作随机游动 在如图所示直线的点集在如图所示直线的点集 一随机游动的质点一随机游动的质点 I 12345 游动游动的概率的概率规规则则 各各以以1/3的概率的概率向左或向右向左或向右移移动动一一格格, 或或以以1/3的概率的概率留留 在在原原处处; 如如果果在在Q（醉汉）（醉汉）现在现在位位于点于点 i 1 i 5,则则下下一一时刻时刻 38 12345 以概率以概率1移移动动到到2或或4这这一一点上点上. 如如果果Q现在现在位位于于1或或5这这点上点上, 则则下下一一时刻就时刻就 1和和5这这两点两点称称为为反反射壁射壁. 上上面面这种这种游动称游动称为为带带有两有两个个反反射壁射壁的随机的随机游动游动. 12345 模拟模拟方法方法产产生生均均匀匀分分布布的随机数序列的随机数序列132322 11122,其其中中1表表示示左左移移;2表表示不示不动动;3表表示示右右移移. 39 理论分析理论分析.的位置的位置时时表示时刻表示时刻以以QnX n .}, 2 , 1 , 0,{是一随机过程是一随机过程则则LnX n 状态空间就是状态空间就是I. ,,为已知时为已知时且当且当IiiX n ∈ , 1 有关有关所处的状态分布只与所处的状态分布只与iXX nn 而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关. 所以它是一个马氏链所以它是一个马氏链, 且是齐次的且是齐次的. 40 一步转移概率一步转移概率}|{ 1 iXjXPp nnij        ≥− − . 21, 0 4, 52, 1, 1 51, 1,, 1, 3 1 j jiji iiiij 或或 41                 01000 3/13/13/100 03/13/13/10 003/13/13/1 00010 5 4 3 2 1 P 5 4 3 2 1 一步转移概率矩阵一步转移概率矩阵 42 由以上讨论知由以上讨论知,转移概率决定了马氏链的运转移概率决定了马氏链的运 动的统计规律动的统计规律. 因此因此, 确定马氏链的任意确定马氏链的任意n步转步转 移概率成为马氏链理论中的重要问题之一移概率成为马氏链理论中的重要问题之一. 43 一一、、C- K 方方程程 }, { 1 TnnX∈设设是一齐次马氏链是一齐次马氏链, 则对任意的则对任意的 有有,, 1 Tvu∈ ., 2, 1,, 1 ∑ ∞ k kjikij jivpuPvuPL 切普曼切普曼- -柯尔柯尔莫哥洛莫哥洛夫方程夫方程 简称简称C - K方程方程 Chapman- Kolmogorov 说明说明 C- K 方方程程基于下基于下列列事事实实 ., , ””转移转移到状态到状态 经经时段时段出出发发所所处处的状态的状态““从时刻从时刻 jj i avusXa vuas 2.多多步步转移转移概率的确定概率的确定 44 这一事件可分解成这一事件可分解成 转移到中间状态转移到中间状态先经时段先经时段出发出发““从从uasX i , ”等事”等事转移到状态转移到状态经时段经时段在从在从 jkk avaka,2, 1L 件的和事件件的和事件. tosus vus i a k aj a 如下图所示如下图所示 45 证明证明, 1 TsIak∈∈ 和和先固定先固定 由条件概率定义和乘法定理得由条件概率定义和乘法定理得 }|,{ ikj asXausXavusXP },|{ }|{ ikj ik asXausXavusXP asXausXP ⋅ .vPuP kjik 马氏性和齐次性马氏性和齐次性 ,, 2 , 1,构成一划分构成一划分””因事件组因事件组““LkausX k 46 所以所以 }|{ ijij asXavusXPvuP ∑ ∞ 1 ,{ k j usXavusXP}.| ik asXa 考虑到马氏性和齐次性考虑到马氏性和齐次性, 即得即得 C- K 方程方程. C- K 方程也可写成矩阵形式方程也可写成矩阵形式 .vPuPvuP 47 二、多步转移概率的确定 利用利用 C- K 方程我们容易确定方程我们容易确定 n 步转移概率步转移概率. 得递推关系得递推关系 , 1, 1 ,−nvuvPuPvuP令令中中在在 ,111−−nPPnPPnP . n P nP 从而可得从而可得 马氏链马氏链的的n步转移步转移概率是概率是一一步转移步转移概率概率的的 n 次次 方方,链链的的有有限限维维分布可分布可由由初初始始分布分布和和一一步转移步转移概率概率 完完全全确定确定. 结结论论 48 . 1,0 , 1 1 1 0 1 0       − − ba bb aa P n步步转移转移概率概率矩阵矩阵为为       1 0 1 0 1110 0100 nPnp nPnp PnP n 矩阵一般可表示为矩阵一般可表示为 ., 2 , 1Ln , 11       − − −−       bb aa ba ba ab ab ba n 对于只有两对于只有两个状态的马个状态的马氏氏链链, 一一步步转移转移概率概率 49 一、遍历性的概念 对于一般的两个状态的马氏链对于一般的两个状态的马氏链, 由上面内容可知由上面内容可知, 有极限有极限时时当当,1,0nPba ij π ∑ N j jj 定定理理 1 ,1,2,..., N jiij i pjNππ ∑ 52 说明说明 步转移概率步转移概率使使数数求证遍历性即找一正整求证遍历性即找一正整mm,. 1 .无零无零元元矩阵矩阵 m P 2. 极限分布转化为了求解方程组极限分布转化为了求解方程组. 3. 在定理的条件下马氏链的极限分布是平稳分布在定理的条件下马氏链的极限分布是平稳分布. 53 , 00 0 0 00                 试说明带有两个反射壁的随机游动是遍历的试说明带有两个反射壁的随机游动是遍历的, 并求其极限分布并求其极限分布平稳分布平稳分布. 解解 的元的元代表转移概率矩阵的正代表转移概率矩阵的正以以 例例 2 2PP                 01000 3/ 13/ 13/ 100 03/ 13/ 13/ 10 003/ 13/ 13/ 1 00010 5 4 3 2 1 P 5 4 3 2 1 54                                 00 0 0 00 00 0 0 00 4 4 PP .                 无零无零元元,链是链是遍遍历历的的 55 ,,, 521 满足方程组满足方程组极限分布极限分布ππππL          πππππ ππ ππππ ππππ ππππ ππ . 1 ,3/1 3/13/1 3/13/13/1 ,/33/1 ,3/1 54321 45 5434 4323 3212 21 .33 54321 πππππ由前四个方程解得由前四个方程解得 代入最后一个方程代入最后一个方程 归一条件归一条件, 得唯一解得唯一解                 01000 3/ 13/ 13/ 100 03/ 13/ 13/ 10 003/ 13/ 13/ 1 00010 5 4 3 2 1 P 5 4 3 2 1 Pππ 56 .11/3,11/1 43251 πππππ 所以极限分布为所以极限分布为 . 11/1,11/3,11/3,11/3,11/1π 这这个个分分布表明布表明 经过长时间游动之后经过长时间游动之后, 醉汉醉汉 Q 位于点位于点 2 或或 3 或或 4 的概率约为的概率约为 3/11, 位于点位于点 1 或或 5 的概率约为的概率约为 1/11. 57 对于某地区天气有雨、晴、阴、多云四种状态的马氏链，容易对于某地区天气有雨、晴、阴、多云四种状态的马氏链，容易 验证，其具有遍历性。验证，其具有遍历性。 1234 11234 21234 31234 41234 1234 {,,,} 0.50.20.30.2 0.10.40.20.3 0.20.20.40.1 0.20.20.10.4 1 ππ π π π πππππ πππππ πππππ πππππ ππππ          极限分布满足方程组 58 1234 0134 0.318 0.238 0.222 0.222 116.07 86.87 81.03 81.0 , 3 ,, SSSS ππππ ∴ 解之得 一年中雨晴阴多云的理论天数分别为 59 习题习题 由于公路运输的发展，大量的短途客流由铁路由于公路运输的发展，大量的短途客流由铁路 转向公路。历年市场调查结果显示，某铁路局吸转向公路。历年市场调查结果显示，某铁路局吸 引区今年与上年相比有如下规律原铁路客流有引区今年与上年相比有如下规律原铁路客流有 85仍由