OR_08马尔科夫链.

第8章马尔科夫链（MarkovChains）121随机过程的基本概念在不少随机现象中，不仅需考虑在某一时刻下的系统状态，而且要研究该系统状态随时间推移而发生的发展变化过程。例如：卡车装运系统电话交换系统城市交通交叉路口3随机现象发展变化过程如何进行描述？某固定时刻t下随机现象状态的描述：随机变量当t在某时间区间内连续发生变化时，单个或多个随机变量不足以表示随机现象的发展变化过程。则：当t在某区间(a，b)内连续变化时，必须用一族无限多个随机变量来描述。这一族无限多个随机变量的总称就是随机过程。4函数概念与随机过程概念的对比：确定性现象中：随时间t变化的一族数值构成函数Y(t)，每个固定值t确定一个数值Y。t的变化范围称定义域，Y(t)的取值范围称值域。随机性现象中：随时间t变化的一族随机变量构成随机过程Y(t)，每个固定值t确定一个随机变量Y。t的取值范围T称参数集，Y(t)的取值范围E称状态空间。因此，随机过程可以看作依赖于时间t的由随机变量构成的函数。5随机过程的描述符号：｛Y(t)，t∈T}随机过程的定义：设T为参数集，若对于每一个t∈T，均有一个随机变量Y(t)与其对应，则将这一族依赖于t的随机变量的全体称为随机过程，记作｛Y（t)，t∈T｝，或简记作YT。6如：泊松过程属T连续，E离散的平稳过程。马尔可夫链是T和E均离散的马尔可夫过程。随机过程的分类：•按照参数集（T）和状态空间（E）的类型，可分为：离散参数链,非离散参数链,随机序列,随机函数•根据概率结构，随机过程可以划分为：独立增量过程，平稳过程，非平稳过程，马尔可夫过程等72随机过程的模拟•随机过程模拟的实质：•随机变量模拟的实质：通过计算机获取随机变量的样本，在一次实验中表现为一个数值。通过计算机实验获取随机过程的一个样本函数。8泊松过程及模拟•泊松流的概念...)2,1,0,0(!)(kekkxPk泊松流(即泊松过程)常用来描述一个随机质点流的状态变化过程。随机质点流指源源不断地随机地到达某目标的一串质点，如：到商场的顾客流、到达工厂的定单流，网络上到达某节点的数据流等。单位时间内到达目标的泊松流质点数目服从泊松分布：9{Tn,n＝1,2,……}则描述了随着到达次序的变化，相继到达目标的两质点到达时间间隔的变化过程。N(t)：[0,t]时间内，到达某目标的质点数；Sn：第n个质点到达目标的时刻(n＝1，2，…)；Tn：第n个质点与其前一质点的相继到达间隔时间。描述泊松流概率特征的符号：{N(t),t≥0｝描述了随着t的变化，在[0,t]时间区间内到达目标质点数的变化过程；{Sn,n＝1,2,……}描述了随着到达目标的先后次序，质点到达时刻的变化过程；10•泊松流的特征及其性质泊松流概率特征：1)独立性：在互不相交的时间区间内到达目标的质点数是相互独立的；2)平稳性：对于充分小的△t＞0，在时间区间[t,t＋△t]内有一个质点到达目标的概率与时间起点t无关，而仅与△t长度成正比；3)普遍性：对于充分小的△t＞0，在时间区间[t,t＋△t]内有一个以上质点到达目标的概率几乎为0。泊松流的基本性质：强度为的泊松流，其相邻质点到达间隔时间服从参数为的负指数分布。11•泊松流的模拟泊松流的模拟，其实质就是要通过计算机获取泊松流的样本函数。由泊松流的特性可知，泊松流的样本函数均是跃度为1的递增阶梯函数。12泊松流模拟方法一：基于泊松流的特征平稳性：在时间区间[t,t+t]内，到达质点的平均数为t；普遍性：则在时间区间[t,t+t]内，质点的到达成为简单事件，有一个质点到达的概率为t，没有质点到达的概率为1-t；独立性：则整个时间段内顾客的到达成为若干相互独立的简单事件的总和。因此，逐个考察各t子区间内质点到达与否即可获取泊松流在[0，T]内的一列到达时刻，进而得到泊松流的一个样本函数。13基于模拟方法一的模拟抽样流程：14泊松流模拟方法二：根据泊松流的基本性质，各质点的相继到达时间间隔t1，t2，……是相互独立且服从同一参数λ的负指数分布，而负指数分布随机数由计算机抽样获得，进而可以计算各质点的到达时刻，得到泊松流的一个样本函数。1基于模拟方法二的模拟抽样流程：15-1t，t=0164.马尔科夫链1、马氏链的基本概念2、齐次马氏链的模拟3、应用举例4.1马氏链的基本概念研究随机过程的主要目的之一是用来预测未来。现以逐日考察的气象预报为例，当设x(t)表示t时刻广州天气的状态，并以0、1、2、3分别代表四种气候状态：雨天、晴天、阴天、多云，即有x(t)=0表示t时刻广州为雨天；x(t)=1表示t时刻广州为晴天；x(t)=2表示t时刻广州为阴天；x(t)=3表示t时刻广州为多云。则当t取0、1、2、…、365时，x(t)=i就表示了自今天开始以后的一年中广州每天天气的状态i（i=0、1、2、3）。于是随机过程{x(t),t=0,1,2,…}就描述了自今天开始以后的一年中广州天气的变化过程。显然此随机过程有离散状态空间E={0，1，2，3}与离散参数集（时间集）T={0，1，2，…}，故它是时间离散、状态离散的链。17为了进行天气预报，人们通常关心的是在过去和当前的气候状态已知条件下来预测将来的天气状态。若以表t今天，s表明天（st），A表过去所处的气候状态，则由积累的气象资料来获得条件概率分布列P{x(s)=j|x(t)=i,A}是十分需要的。因为它表示了在过去状态为A、当前（今天）状态为i已知的条件下，将来（明天）状态为的可能性（其中i与j均可取0，1，2，3中的任一种）。18例如若已知有P{x(s)=0|x(t)=i,A}=0.8P{x(s)=1|x(t)=i,A}=0.1P{x(s)=2|x(t)=i,A}=0.05P{x(s)=3|x(t)=i,A}=0.05则人们当然可以预言明天的气候状态为0（雨天）。19一般情况下，当当前状态已知的条件下，将来的状态可能与过去所处的状态A有关，也可能无关。若随机过程{x(t),t=0,1,2,…}的条件概率满足关系式P{x(s)=j|x(t)=i,A}=P{x(s)=j|x(t)=i}对任何st及i∈E，j∈E成立，即与过去状态A无关，则称该随机过程为马氏链，并将上述特性成为马氏链性或无后效性。20马氏性指出了这样一个事实：“如果我们知道了系统在任一时刻的状态，就以此预测从这以后的任何未来时刻的状态变化过程，至于在这以前，系统是怎样到达此状态的经历是无关紧要的。”或简单地说“给定现在，将来与过去独立”，这就是马氏链的本质特性。自然科学与社会科学的很多现象都具有上述特性，如仓库前卡车排队长度的变化过程，产品销售的变化过程等。21在马氏链{x(t),t=0,1,2,…}中当s=t+1时，条件概率P{x(t+1)=j|x(t)=i}，一般来说不仅依赖于状态i与j，而且依赖于当前时刻t，但若该马氏链的条件概率与当前时刻t无关，则称此特殊的马氏链为齐次马氏链，或者说该马氏链是齐次的。马氏链的齐次性反映了这样一个事实：无论从什么时刻开始，系统未来的状态变化过程的统计规律总是一致的。在其次马氏链{x(t),t=0,1,2,…}中，由于条件概率P{x(t+1)=j|x(t)=i,A}与过去历史A无关，与当前时刻t无关，从而只与当前时刻t所处的状态i以及将来（明天或其他）状态j有关，故可以简记为Pij=P{x(t+1)=j|x(t)=i,A}其中i和j可取状态空间E中任一状态，22如天气预报中i与j可取0、1、2、3中的任一状态。若将中Pij中i与j所取的状态一一列举出来，并按照一定的次序排列起来，可得：称为齐次马氏链的转移矩阵（更确切地说是一步转移矩阵，其“一步”的含义是由于有s=t+1，即将来与现在时刻仅差一个单位）。23P=00010203101112132021222330313233PPPPPPPPPPPPPPPP24在此转移矩阵P中，第一行元素00010203PPPP表征了在当前状态为0的状态下，未来状态分别取0，1，2，3的概率。考虑到未来状态亦只能取这四个状态中的一个，故应有00010203P+P+P+P=1同样，转移矩阵P中的第二行元素10111213PPPP表征了在当前状态为1的条件下，未来状态分别取0，1，2，3的概率，其余类推。与前同理，应有关系式显然，若我们将天气状态的变化过程{x(t),t=0,1,2,…}理想地看作齐次马氏链的话，只要给出了转移矩阵，则无论当前的状态i取0，1，2，3中的哪一个，均可以从转移矩阵P中找出相应的一行来进行比较，从而得到预测值。2510111213P+P+P+P20212223P+P+P+P30313233P+P+P+P=1=1=14.2齐次马氏链的模拟齐次马氏链{x(t),t=0,1,2,…}中的一列随机变量x(0),x(1),x(2),…如果是相互独立的话，我们就可以按照上一节的方法将每个随机变量独立地逐个进行模拟，并获取其样本值。但事实上问题并非如此简单，原因在于马氏链的各个随机变量x(l)与x(h)之间并非是相互独立的（l≠h），而是满足一定的相依关系---马氏链。但好在这种马氏性所满足的相依关系是比较微弱的，它只要求每一时刻s的状态仅依赖于上一时刻t=s-1的状态，即x(n+1)依赖于x(n)，x(n)依赖于x(n-1)，…，x(2)依赖于x(1)，x(1)依赖于x(0)，因此为获取齐次马氏链的一个样本，只需要由t=0时的初始状态x(0)=i0及转移矩阵P来决定x(1)之样本i1,再由i1及P来决定x(2)之样本i2，由in及P来决定x(n+1)的样本in+1……26根据上述设想，对一个具有状态空间E={0，1，2，…}的转移矩阵的齐次马氏链{x(t),t=0,1,2,…}实施模拟的具体步骤如下：（1）设x(0)由初始状态i0，即x(0)=i0。（2）求x(1)的样本R1。考虑到状态x(0)=i0已发生，故在x(0)=i0已发生的条件下x(1)的条件分布列P{x(1)=j|x(0)=i0}=Pi0j(j=0,1,2,…)27P=0001020m1011121mm0m1m2mmPPPPPPPPPPPP是已知的，这只须从矩阵28P=00nnn00010mi0i11mi0i1imm0m1mmPPPPPPPPPPPP的第i0行取出各元素000i0i1imPPP即可。有了x(1)的条件分布列，就可以直接按照上一节对离散型随机变量的一般模拟法来求取x(1)的样本值i1。其具体做法为首先取伪随机数u1，然后选取数i1，使满足不等式于是有x(1)的样本R1=i1。2911100010iijjPijPiju⑶求x(2)的样本R2。与上同理，由于x(1)=i1已发生，故在x(1)=i1已发生条件下x(2)的条件分布列是已知的，这只须从转移矩阵P中取出第i1行的全部元素11i0i1PP即可，然后按照对离散型随机变量的一般模拟法来求取x(2)的样本值。即首先选取随机数u2，然后选取数i2，使满足不等式于是有x(2)的样本R2=i2。3021200121iijjPijPiju⑷求x(3)的样本R3。反复运用上述步骤，即可获得齐次马氏链{x(t),t=0,1,2,…}在具有初始状态i0条件下的一组样本值i0，i1，i2…。若以初始时刻t=0表示今天，x(0)=i0表示已知的今天天气状态，x(t),t=0,1,2,…表示明天、后天、大后天…的天气状态，则利用上述方法对齐次马氏链{x(t),t=0,1,2,…}实施模拟求得之一组样本值i0，i1，i2…即为广州天气在今天以后一段时期状态的预报。3132最后需要说明的是使上述的一组样本值是在初始状态x(0)=i0已确定的情况下获得的，如果初始状态x(0)亦为随机变量，则只要给出