《应用统计学与随机过程第7章--马尔可夫过程2016》由会员分享，可在线阅读，更多相关《应用统计学与随机过程第7章--马尔可夫过程2016（143页珍藏版）》请在金锄头文库上搜索。
1、主讲教师：何松华 教授联系电话：(0731）82687718 13973132618电子信箱：应用统计学与随机过程应用统计学与随机过程( (通信专业通信专业) )Applied Statistics and Random ProcessApplied Statistics and Random Process湖南大学教学课件：应用统计学与随机过程 马尔可夫过程7. 马尔可夫过程(8学时)7.1马尔可夫过程的一般概念7.2马尔可夫序列7.3连续马尔可夫过程7.4马尔可夫链7.5泊松过程引引 言言马尔可夫(1870年,俄罗斯)过程的工程背景(1)在对客观事物的分析中,经常需要根据事物的当前状态及过
2、去状态预测事物在未来时刻出现各种状态的可能性。(2)如果在仅仅已知当前状态的情况下,就能够完全确定客观事物在未来时刻出现各种状态的可能性,则预测问题可以变得简单化。(3)马尔可夫过程就是这样的特殊过程,即:在t0时刻状态已知的情况下,tt0时刻的状态只与t0时刻的状态有关；在信息处理、自动控制、公用事业等领域经常遇到这种过程。湖南大学教学课件：应用统计学与随机过程 马尔可夫过程马尔可夫过程的一般概念马尔可夫过程的一般概念7.11.马尔可夫过程的数学定义湖南大学教学课件：应用统计学与随机过程 马尔可夫过程设设随机过程随机过程X(t)以及任意的以及任意的m+1个时刻个时刻t1 t2 t3 tm t
3、m+1，对任意的取值对任意的取值xm以及任意的取值以及任意的取值范围范围 m+1, 1, 2, m-1;若满足条件若满足条件则称这类随机过程为具有则称这类随机过程为具有马尔可夫性质的随机过程或马尔可夫过程。马尔可夫性质的随机过程或马尔可夫过程。在m时刻的取值确定情况下,m+1时刻的取值或取值范围与m以前时刻的取值或取值范围无关(m时刻值必须确定时刻值必须确定)上述定义与如下定义等价湖南大学教学课件：应用统计学与随机过程 马尔可夫过程设设随机过程随机过程X(t)以及任意的以及任意的m+1个时刻个时刻t1 t2 t3 tm tm+1，若满足若满足简记为简记为: :则称这类随机过程为具有则称这类随机
4、过程为具有马尔可夫性质的随机过程或马尔可夫过程。马尔可夫性质的随机过程或马尔可夫过程。在m时刻的取值确定情况下,m+1时刻的条件概率密度与m以前时刻的取值无关湖南大学教学课件：应用统计学与随机过程 马尔可夫过程证(自学)：必要性，令如果条件概率分布函数满足：则上式两边对xm+1求偏导，得到：湖南大学教学课件：应用统计学与随机过程 马尔可夫过程充分性，若则：根据概率形式的条件贝叶斯公式湖南大学教学课件：应用统计学与随机过程 马尔可夫过程根据密度形式的条件贝叶斯公式马尔可夫性质2.马尔可夫过程的统计特性湖南大学教学课件：应用统计学与随机过程 马尔可夫过程性质1：对于马尔可夫过程，任意的多维概率密度
5、分布函数可以由其初始时刻的一维概率密度分布函数以及由此递推的一维条件概率密度分布函数确定。证：贝叶斯公式湖南大学教学课件：应用统计学与随机过程 马尔可夫过程同理可得到：根据马尔可夫过程定义(这里与tn时刻最靠近的过去时刻为tn-1)以此类推：递推到n-2=1时,为fx(x1;t1)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程推论(自学)：对于马尔可夫过程，任意多个时刻的多维概率密度分布函数可以由这些时刻的相邻时刻二维条件概率密度分布函数确定。湖南大学教学课件：应用统计学与随机过程 马尔可夫过程性质2：对于任意的tstrtn，在已知X(tr)=xr情况下，随机变量X(ts)与X(tn)
6、相互独立 ，即证：根据概率密度形式的条件贝叶斯公式根据马尔可夫过程定义则有：练习:利用概率论知识证明这里与tn时刻相对靠近的过去时刻为tr)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程性质3：如果(马尔可夫)随机过程是(严格)平稳的(联合概率密度函数不随时间的平移而变化)，则一定是齐次的(条件概率密度函数不随时间的平移而变化)，反之不一定。显然对任意的ts,tn，如果随机过程平稳，则同时平稳时X(ts+)与X(ts)具有相同的概率密度函数平稳时X(ts+)、 X(tn+)与X(ts)、 X(tn)具有相同的概率密度函数湖南大学教学课件：应用统计学与随机过程 马尔可夫过程得到即：条件概率
7、密度函数不随时间的平移而发生变化，此时，称马尔可夫过程为齐次的。反之，如果马尔可夫过程为齐次的，但不一定满足任意多维联合概率密度函数不随时间平移而变化的特性，则不一定是平稳的。性质4：切普曼柯尔莫哥洛夫方程(转移概率密度函数的递推关系)。对任意的tstr1)解：(1) 先求该离散时间因果线性系统的单位脉冲响应n0时， 该差分方程的通解为代入：得：非平稳时只能采用时域法湖南大学教学课件：应用统计学与随机过程 马尔可夫过程mW = 0根据因果及输入从0 时刻开始湖南大学教学课件：应用统计学与随机过程 马尔可夫过程同理参见前面的AR(1)模型对于非马氏的正态过程，联合分布还需要得到不同时刻之间的相关
8、函数；而马氏正态过程只需计算条件均值、条件方差湖南大学教学课件：应用统计学与随机过程 马尔可夫过程(2)合并整理(略)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程练习：利用正态分布函数积分性质求积分附:另外一种简单求法。在已知X(n-1)=xn-1时根据递推关系求条件均值、条件方差附录(自学): AR(1)正态过程为马氏过程湖南大学教学课件：应用统计学与随机过程 马尔可夫过程证明X(n)为离散马尔可夫随机过程，即已知初始状态X(-1)=0，输入从n=0时刻开始， W(n)为离散独立同分布(IID)序列证：显然，根据随机变量的函数的概率密度关系湖南大学教学课件：应用统计学与随机过程 马尔
9、可夫过程则有根据多维随机变量的多维函数的联合概率密度关系，有：显然定义如下矩阵：考虑到X(-1)=0, 湖南大学教学课件：应用统计学与随机过程 马尔可夫过程根据W(n)的独立同分布特性，有则有：同理可以得到：连续马尔可夫过程连续马尔可夫过程7.3连续马尔可夫过程的数学定义及举例湖南大学教学课件：应用统计学与随机过程 马尔可夫过程状态(随机变量取值)连续、时间也连续的马尔可夫过程称为连续马尔可夫过程。例题1：白色噪声通过一阶微分方程所表征的线性系统，输出过程为连续马尔可夫过程其中W(t)为白色平稳正态过程，则X(t)也为正态随机过程；X(0-)=0，输入从t=0加入；证明X(t)为马尔可夫过程；
10、并求其均值函数、方差函数、条件均值/方差函数X(t)的统计特性的推导见第3章ppt湖南大学教学课件：应用统计学与随机过程 马尔可夫过程证：系统的冲激响应在已知X(tn-1)的情况下，X(tn)的统计特性由tn-1以后的输入W(t)确定，与 tn-1之前的X(t) 无关，满足马尔可夫性质。对于任意的tn-1tn根据因果及输入从0 时刻开始根据因果线性系统特性湖南大学教学课件：应用统计学与随机过程 马尔可夫过程(自学：数学上的严格证明)对于任意的n以及任意的0t1t2tn-10)内的增量X(t+)-X(t)的均值为常数(0)，方差与时间起点无关，则增量的概率密度分布(正态分布)与起点无关,只与时间
11、宽度有关。马尔可夫链马尔可夫链7.41.马尔可夫链的数学定义湖南大学教学课件：应用统计学与随机过程 马尔可夫过程即在n-1时刻状态已知的情况下，n时刻的状态与n-1时刻以前的状态无关无后效性，X(1),X(2),X(n-2)对X(n)的影响是通过X(n-1)实现的，如果已知X(n-1)则无须知道n-1以前的值。思考：下标为什么写成in而不是n状态(随机变量取值)离散、时间也离散的马尔可夫过程称为马尔可夫链。设n为离散的采样时刻，a1,a2,aN为任意时刻随机变量的取值范围，称为状态集合I; 对于任意的 满足这里假设起始时刻为n=12.马尔可夫链举例湖南大学教学课件：应用统计学与随机过程 马尔可
12、夫过程 例：带反射壁的一维随机游动问题。设有一质点在例：带反射壁的一维随机游动问题。设有一质点在x轴上作随机游动。在轴上作随机游动。在n=1 时质点位于时质点位于x轴的原点，在轴的原点，在n=2,3,4,时质点可以在时质点可以在x轴上正向或反向移动一个单位轴上正向或反向移动一个单位距离；如果相对原点移动了距离；如果相对原点移动了l个单位的距离，则下次移动个单位的距离，则下次移动只能返回。不管质点处于什么位置，作正向移动一个单只能返回。不管质点处于什么位置，作正向移动一个单位距离概率为位距离概率为p，作反向移动一个单位距离概率为作反向移动一个单位距离概率为1-p。如图。如图。 x0p q=1-p
13、ll湖南大学教学课件：应用统计学与随机过程 马尔可夫过程若给定时间若给定时间n-1，质点偏离原点的距离为质点偏离原点的距离为k，可表示可表示为为xn-1=k，则质点在则质点在n时刻处于各种状态时刻处于各种状态 (偏离原点的偏离原点的距离距离)的概率的概率只与只与n-1时刻质点所在的状态有关。时刻质点所在的状态有关。 n时刻质点所处的状态及概率可以表示为：时刻质点所处的状态及概率可以表示为：当当 l xn-1 1以及任意的状态编号in-1及状态取值范围有：证(自学)：湖南大学教学课件：应用统计学与随机过程 马尔可夫过程湖南大学教学课件：应用统计学与随机过程 马尔可夫过程即:附录:马尔可夫链的无后
14、效性的推广2湖南大学教学课件：应用统计学与随机过程 马尔可夫过程证(自学)：对于任意的n1, m0 以及任意的有：湖南大学教学课件：应用统计学与随机过程 马尔可夫过程根据转移事件的分解或条件情况下的全概率公式根据“无后效性推广1”湖南大学教学课件：应用统计学与随机过程 马尔可夫过程根据“无后效性的推广1”以此类推，根据数学归纳法则可以得到：根据第1步的证明附录:马尔可夫链的无后效性的推广3湖南大学教学课件：应用统计学与随机过程 马尔可夫过程对于任意的M以及任意的时刻n1 n2 nM-1 nM，对于任意的有:证(自学)：(1)内插后变成下标连续序列；(2)内插时刻的事件为全概率事件，不影响条件概
15、率；(3)利用“无后效性的推广2”时刻不连续3.马尔可夫链的状态概率与状态转移概率湖南大学教学课件：应用统计学与随机过程 马尔可夫过程随机过程X(n)在第n时刻的状态为aj的概率，记为随机过程X(n)在第s时刻状态为ai的情况下，n时刻的状态为aj的概率称为从s时刻的第i种状态到n时刻的第j种状态的转移概率，记为根据全概率公式(参见后图)及贝叶斯公式，注意：是条件概率而非联合概率一维概率分布与二维联合概率分布的关系湖南大学教学课件：应用统计学与随机过程 马尔可夫过程pj(n)n时刻处于时刻处于j状态概率状态概率aja1a2aiaNp1j (s,n)p2j (s,n)pij (s,n)pNj (
16、s,n)p1(s)p2(s)pi(s)pN(s)事件的分解(或划分)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程一维情况下的全概率与二维情况下的全概率的等价性考虑到一维分布律与二维分布律之间的关系一维情况二维情况湖南大学教学课件：应用统计学与随机过程 马尔可夫过程条件概率同样需满足全概率性质，即：当s时刻状态为ai时，不管状态怎么转移，在n时刻，必然转移到N个状态中的其中一个，即任意状态下的转移概率之和为1已知已知s时刻时刻状态为状态为aiaia1n时刻时刻状态状态a2aiaNpi1(s,n)pi2(s,n)pii(s,n)piN(s,n)I3.马尔可夫链的转移概率矩阵P(s,n)湖南
17、大学教学课件：应用统计学与随机过程 马尔可夫过程N行N列的矩阵，其第i行第j列的元素为随机过程X(n)从第s时刻的状态ai转移到第n时刻的状态aj的转移概率pij(s,n)，该矩阵称为从s时刻到n时刻的转移概率矩阵，记为转移概率矩阵的约束性：(1)元素的值非负；(2)每行的元素值之和必须为1 (从s时刻的ai状态分别转移到n时刻的N个状态的概率之和，这是一个全概率)思考：每列之和的取值为什么不确定状态转移概率矩阵及状态转移图举例湖南大学教学课件：应用统计学与随机过程 马尔可夫过程a1a2a3a41/41/41/211/21/21/41/41/41/4思考：本例中，转移矩阵与n无关，说明什么？4
18、.已知s时刻的状态概率分布，通过转移概率矩阵计算n时刻的状态概率分布湖南大学教学课件：应用统计学与随机过程 马尔可夫过程设为s时刻X(s)的各种取值(状态)出现的概率所构成的矢量(状态概率分布列阵)为n时刻X(n)的各种取值(状态)出现的概率所构成的矢量，则根据前面的分析将上述N个线性方程组用矩阵与矢量形式表示为思考：元素值非负，且和值为1？湖南大学教学课件：应用统计学与随机过程 马尔可夫过程特别注意：状态转移矩阵要转置4.(离散情况下的)切普曼柯尔莫哥洛夫方程 对于任意的srn,已知从s时刻的状态转移到r时刻状态的各种转移概率P(s,r)=pij(s,r)以及从r时刻的状态转移到n时刻状态的
19、各种转移概率P(r,n) )=pij(r,n) ,如何计算从s时刻状态转移到n时刻状态的各种转移概率P(s,n) )=pij(s,n) 湖南大学教学课件：应用统计学与随机过程 马尔可夫过程物理理解：sX(s)=ainX(n)=ajra1pi1(s,r)p1j(r,n)a2pi2(s,r)aNp2j(r,n)piN(s,r)pNj(r,n)I转移事件的分解马尔可夫性质：此条件概率与i无关性质：湖南大学教学课件：应用统计学与随机过程 马尔可夫过程证：根据定义、全概率公式、贝叶斯公式以及马尔可夫过程性质全概率公式或二维联合概率分布与三维联合概率分布律之间的关系数学证明：sr s，通过归纳法(递推)可
20、以得到湖南大学教学课件：应用统计学与随机过程 马尔可夫过程6.马尔可夫链的“无后效性推广2”补充证：n+m 时刻的状态概率分布矢量(列阵)与n-1时刻的状态概率分布矢量(状态概率分布列阵)的关系为对任意的 m 0，满足矩阵P(n-1,n+m)的第 行第 列元素值令湖南大学教学课件：应用统计学与随机过程 马尔可夫过程若已知X(n-1)取值(状态)为 ，则第 个元素值为1，其余全为0在已知X(n-1)取值(状态) 情况下，n+m时刻出现各种状态的概率完全取决于状态转移矩阵P(n-1,n+m)以及n-1时刻的状态 ，与n-1时刻以前的状态无关。湖南大学教学课件：应用统计学与随机过程 马尔可夫过程附录
21、(自学)：马尔可夫链定义的等价性对任意的 m 0以及任意的如果则称该状态(随机变量取值)离散、时间也离散的随机过程称为马尔可夫链参见前面“无后效性推广2”的证明过程湖南大学教学课件：应用统计学与随机过程 马尔可夫过程7.马尔可夫链的联合概率分布的分解性质对于任意的M以及任意的n1n20)时刻的转移概率矩阵P(s,s+m)与起点时刻s无关，则称为齐次马尔可夫链，并将其转移概率矩阵P(s,s+m)与s无关记为P(m)定义：将齐次马尔可夫链任意s时刻的一步转移概率矩阵P(1)的转置P(1)T记为 根据前面得到的概率分布列阵之间的关系以及多步转移概率矩阵与一步转移概率矩阵之间的关系，有T表示矩阵转置湖
22、南大学教学课件：应用统计学与随机过程 马尔可夫过程9.平稳马尔可夫链及其特性如果马尔可夫链任意n时刻的概率分布列阵(列矢量)都相同(与n无关)，即：则称该马尔可夫链为平稳链。对于齐次链，如果转移概率矩阵T以及初始状态概率列阵足如下条件，则该链一定是平稳的，即证：齐次链是否平稳与一步转移概率矩阵以及初始状态概率列阵有关湖南大学教学课件：应用统计学与随机过程 马尔可夫过程10.平稳齐次链状态概率分布列阵的求解对于平稳齐次马尔可夫链，记则有：与n无关湖南大学教学课件：应用统计学与随机过程 马尔可夫过程上述N个方程没有唯一解，显然，若(p1,p2,pN)为解，则(ap1,ap2,apN)亦为解，即这N
23、个方程并不独立，独立的方程为N-1个，必须加一个约束条件才能得到唯一解。利用上述方程组中的任意N-1个方程与如下方程联立，思考:如果求出的概率值出现负数,说明什么情况?即可求出p1,p2,pN湖南大学教学课件：应用统计学与随机过程 马尔可夫过程11. 齐次马尔可夫链的遍历或渐近平稳条件在齐次马尔可夫链中，对任意的s，不管s时刻随机过程的状态概率分布如何，如果m时，s+m时刻随机过程处于状态aj的概率为常数pj(与s以及s时刻的状态概率分布无关),则称该链为遍历的，或渐近平稳的。要求对于所有的i,j，步转移矩阵P()的元素值pij()， s时刻的任意状态概率分布列阵为q1,q2,qNT (q1+
24、q2+qN=1) ，满足：要求矩阵P()的列趋于常数，即如下的极限存在湖南大学教学课件：应用统计学与随机过程 马尔可夫过程此时进一步可以得到：p1,p2,pN满足对任意的i成立,相当于P()的第j列趋于常数pj必要性:针对s时刻状态概率分布的某个qi=1,其他概率值为0,共N种情况得到极限解充分性:显然，上述极限解对任意的q矢量成立湖南大学教学课件：应用统计学与随机过程 马尔可夫过程定理：对于状态有限的齐次马尔可夫链，如果存在正数m，使得m步转移概率矩阵P(m)的所有元素值满足则该链是渐近平稳的，且极限状态概率分布列阵满足：定义：如果齐次马尔可夫链的任何一个状态都可以经过若干步的转移后到达其他
25、任何一个状态,则称其为不可约的。充要条件证明参见附录思考:渐近平稳齐次链为平稳链的条件湖南大学教学课件：应用统计学与随机过程 马尔可夫过程定义：齐次马尔可夫链的某个状态ai，如果存在正整数d1，只有当转移步长m=d,2d,3d,时，才有可能从该状态转移回到该状态，则称状态ai为具有周期性的状态。引理：对于状态有限的齐次马尔可夫链，如果是不可约的，且不存在周期性，则一定是渐近平稳(遍历)的。引理：如果方程组没有合理解(对所有i,满足1pi0)，则具有一步转移概率矩阵 T的齐次马尔可夫链不是渐近平稳(遍历)的。充要条件，证明参见后面附录必要条件举例:带反射壁的质点游动d=2湖南大学教学课件：应用统
26、计学与随机过程 马尔可夫过程马尔可夫链举例1：带有反射壁的质点随机游动过程t0X(t)12-1-2T2Ta1a2a3a4a5若质点s时刻在a5状态，则s+1时刻以概率1转移到a4；若质点s时刻在a1状态，则s+1时刻以概率1转移到a2；若质点s时刻在a2, a3 ,a4状态，则s+1时刻以概率1/2转移到上一个单位或下一个单位。显然，该过程是马尔可夫链，由于所有时刻s的一步转移概率矩阵都相同，则该链是齐次的。根据题意得到该链的一步转移矩阵为湖南大学教学课件：应用统计学与随机过程 马尔可夫过程根据一步转移概率矩阵得到该链的状态转移图为a1a2a3a4a51/211/21/21/21/21/21显
27、然，满足不可约性，但具有周期性(d=2)；例如：初始状态为a1时，则p11(2m+1)=0， p11(2m)0。而p12(2m+1)0， p12(2m)=0；转移步数m为奇数与偶数，转移概率的极限值pij(m)不同，m时极限不存在，不是渐近平稳的。湖南大学教学课件：应用统计学与随机过程 马尔可夫过程马尔可夫链举例2：设马尔可夫链一步转移矩阵为设马尔可夫链一步转移矩阵为当当m=2时时该该马尔可夫链马尔可夫链具有遍历性或渐近平稳性具有遍历性或渐近平稳性所有所有pij(m)0pa1a2a3ppqqq不可约且无周期性湖南大学教学课件：应用统计学与随机过程 马尔可夫过程不管初始状态如何，不管初始状态如何
28、，n n时，状态概率列阵为时，状态概率列阵为取前2独立个方程=p/q练习湖南大学教学课件：应用统计学与随机过程 马尔可夫过程特别地，当特别地，当对于任意的对于任意的n n 1,1,有有该链为平稳链。该链为平稳链。性质：如果齐次马尔可夫链的一步转移矩阵满足性质：如果齐次马尔可夫链的一步转移矩阵满足渐近平稳的条件，则当初始概率分布列阵为该链渐近平稳的条件，则当初始概率分布列阵为该链的平稳解时，该链是平稳的，齐次不一定平稳。的平稳解时，该链是平稳的，齐次不一定平稳。湖南大学教学课件：应用统计学与随机过程 马尔可夫过程马尔可夫链举例3：设马尔可夫链一步转移矩阵为设马尔可夫链一步转移矩阵为求其任意n(n
29、1)步转移概率矩阵解：对P(1)进行本征分解，两个特征根分别为1-，1；对应的单位特征向量(矢量各元素平方和为1)分别为练习湖南大学教学课件：应用统计学与随机过程 马尔可夫过程根据矩阵的本征分解理论(参见附录)：练习:运用数学归纳法证明湖南大学教学课件：应用统计学与随机过程 马尔可夫过程练习:复习矩阵求逆理论，并验证不管初始状态如何，最终处于状态1、2的概率分别为/(+)、 /(+)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程本节作业本节作业7-4,7-8,7-16,7-21湖南大学教学课件：应用统计学与随机过程 马尔可夫过程设MM维矩阵R的M个特征根以及对应的单位特征向量分别为附录(
30、自学)：矩阵的本征分解理论则：令：则：分块矩阵乘积等价于：对于对称矩阵R，练习湖南大学教学课件：应用统计学与随机过程 马尔可夫过程1：NN的转移概率矩阵P(1)满足行和为1的特性，则1必定是其特征值，且 为对应的单位特征向量附录(自学)：齐次马尔可夫链渐近平稳性的有关证明2：转移概率矩阵P(1)除满足行和为1外，所有元素值非负，称为随机矩阵，根据圆盘定理，其所有特征根的模小于等于1。圆盘定理：设矩阵第i行除对角线上元素的和值为ri，对角线元素为i，则所有特征根分布在复平面N个圆组成的区域内|z- i | ri，可得：|z| 1湖南大学教学课件：应用统计学与随机过程 马尔可夫过程3：如果转移概率
31、矩阵P(1)的特征根1不是重根(不妨假设为第1个特征根1)，其他特征根的模小于1，则所对应的马尔可夫链一定是渐近平稳的上式说明P()的第j列为常数pj=4：容易证明随机矩阵的乘积依然为随机矩阵，则P()的行和为1，元素值非负； p1+ p2 + pN =1 (0 pi 1)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程5：Perron定理：如果矩阵的所有元素值为正(称为正矩阵)，则它的模值最大的特征根为正的单根。结合前面3的推导可知：如果存在正整数m，P(m)为正的随机矩阵，则所对应的马尔可夫链一定是平稳的。利用任意l步转移矩阵的行和为1的特性由于P(m)为正阵, P(l)为随机矩阵,则
32、容易证明为P(n)为正阵,极限也为正的,即:1pi0湖南大学教学课件：应用统计学与随机过程 马尔可夫过程6：状态有限的不可约的马尔可夫链是非周期链的充要条件是：存在正整数m，使得P(m)为正矩阵；根据此性质结合5可以证明状态有限的不可约的非周期马尔可夫链是渐近平稳的。设从状态ai出发，经过ri(1)、 ri(2)、 ri(Ji)的倍数都可以返回(非周期)，其中ri(1)、 ri(2)、 ri(Ji)为最大公因子为1的正整数，Ji1；令ni= ri(1) ri(2) ri(Ji), K=maxn1,n2,nN,取nK+N,则对于任意的j,k；由于所有状态之间可到达，则一定可以经过不多于N-1步到
33、达，即存在mc0;根据余数定理,对于md=n-ncK，一定存在非负的整数di(1), di(2), di(Ji),使得从ak出发经md步可返回ak湖南大学教学课件：应用统计学与随机过程 马尔可夫过程马尔可夫链举例4：假设某天是否有雨依赖于前两天天气假设某天是否有雨依赖于前两天天气昨日天气雨无雨今日天气雨无雨雨无雨明日天气雨无雨雨无雨雨无雨雨无雨概率0.70.30.40.60.50.50.20.8后日天气雨无雨雨无雨雨无雨雨无雨概率?试运用马尔可夫链理论建立后日的天气与昨今两日天气状况的关系?湖南大学教学课件：应用统计学与随机过程 马尔可夫过程显然，原过程非马尔可夫链，先设法转化为马尔可夫链转化
34、方法：对每两日的天气进行组合，时间序列为:，大前/前，前/昨，昨/今，今/明，明/后，后/大后，则在某组时序组合中出现的状态(天气)组合确定的情况下，其后一组时序组合中各种状态(天气)出现的概率唯一确定，与该组合以前的组合的状态无关；这是马尔可夫链，而且是齐次的。设在每个时序组合可能出现的状态组合为 1：r/r，2：n/r，3：r/n，4：n/n (n:无雨, r:雨)对应的各种状态转移概率为：不可能的状态转换p11=P今r/明r|昨r/今r= P/明r|昨r/今r= 0.7p12=P今n/明r|昨r/今r= 0湖南大学教学课件：应用统计学与随机过程 马尔可夫过程同理可以求得其他转移概率，最终
35、得到一步转移概率矩阵为(练习)p13=P今r/明n|昨r/今r= P/明n|昨r/今r= 0.3p14=P今n/明n|昨r/今r= 0湖南大学教学课件：应用统计学与随机过程 马尔可夫过程二步转移概率矩阵“昨/今”各状态到“明/后”各状态的转移概率湖南大学教学课件：应用统计学与随机过程 马尔可夫过程明雨后雨明无雨后雨明雨后无雨明无雨后无雨后雨后无雨昨雨今雨0.490.120.210.180.610.39昨无雨今雨0.350.200.150.300.550.45昨雨今无雨0.200.120.200.480.320.68昨无雨今无雨0.100.160.100.640.260.74注：P后r|昨i/今
36、j= P明r/后r|昨i/今j+ P明n/后r|昨i/今jP后n|昨i/今j= P明r/后n|昨i/今j+ P明n/后n|昨i/今j湖南大学教学课件：应用统计学与随机过程 马尔可夫过程马尔可夫链举例5 ：设某地某人每天的工余活动行为仅仅依赖于当天的天气：假设该地天气为齐次马尔可夫链，从某天天气到其下一天天气的一步转移矩阵为：假设天气预报明天为无雨、雨的概率分别为0.8, 0.2 ；(1)根据连续三天的各种天气组合概率计算该人在明、后、大后连续三天购物的概率； (2)根据行为过程计算连续三日购物概率(拓展训练，自学)；(3)说明行为过程不是马尔可夫过程(拓展训练，自学)。湖南大学教学课件：应用统
37、计学与随机过程 马尔可夫过程解：(1)设X表示天气状态， “无雨”、 “雨”分别用1,2表示，n为时间(天)序号，n=1为明天； Y表示行为状态，“购物”、“体育运动”、“娱乐”分别用1,2,3表示；根据低维联合概率分布与高维联合概率分布关系及贝叶斯公式，有例：根据马尔可夫链性质湖南大学教学课件：应用统计学与随机过程 马尔可夫过程当日天气确定时,当日行为与其他因素无关例：根据条件贝叶斯公式湖南大学教学课件：应用统计学与随机过程 马尔可夫过程天气组合该组合出现概率该组合条件下连续购物概率联合概率(概率积)1110.3920.0080.0031361120.1680.0040.0006721210
38、.0960.0040.0003841220.1440.0020.0002882110.0560.0040.0002242120.0240.0020.0000482210.0480.0020.0000962220.0720.0010.000072共8种组合，8项联合概率之和为0.00492练习：验证湖南大学教学课件：应用统计学与随机过程 马尔可夫过程(2)(自学)思路：由Y(1)反推天气X(1)，X(2)，再根据天气X(2)计算Y(2)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程X(1)确定情况下X(2)与Y(1)无关湖南大学教学课件：应用统计学与随机过程 马尔可夫过程X(2)确定情况下
39、Y(2)与Y(1)无关思路：由Y(1),Y(2)反推天气X(2)，X(3)，再根据天气X(3)计算Y(3)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程X(2)确定情况下X(3)与Y(1),Y(2)无关湖南大学教学课件：应用统计学与随机过程 马尔可夫过程与前面的结果一致湖南大学教学课件：应用统计学与随机过程 马尔可夫过程(3)(自学)思路：由Y(2)反推天气X(2)，X(3)，再根据天气X(3)计算Y(3),得到PY(3)|Y(2)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程因此，行为过程不是马尔可夫过程。但可以通过马尔可夫过程来分析。湖南大学教学课件：应用统计学与随机过程 马尔
40、可夫过程马尔可夫链举例6 (拓展训练/自学)：隐马尔可夫过程设某类人群的行为受某种不可观测的(隐含的)状态所控制状态数目、状态转移概率矩阵以及各种状态下的行为概率矩阵未知(1)假设已获得该类人群中M个人在连续J天的行为序列Om1 Om2 OmJ ，如何得到状态数、状态转移概率、不同状态下的行为概率的估计；(2)已知某个未知类别人员的行为序列O1 O2 OJ ，判断该人是否属于此类人群？12 马尔可夫过程的状态分析湖南大学教学课件：应用统计学与随机过程 马尔可夫过程定义1：可到达。如果存在m1，使得pij(m)0，即由状态i出发经m次转移后可以正的概率(排除0概率,概率非负)转移到状态j，则称可
41、以由状态i到达状态j，记为ij定义2：不能到达。如果对任意的m 1 ，均有pij(m)=0，即由状态i出发，无论经多少步转移，都不能到达状态j，则称由状态i不能到达状态j。定义3：相通。如果由状态i可到达状态j ，由状态j也可到达状态i，则称状态i和j是相通的。定理1：“到达”的可传递性。若由状态i可到达状态j ，由状态j可到达状态k，则由状态i可到达状态k。练习:根据K-M公式证明湖南大学教学课件：应用统计学与随机过程 马尔可夫过程定理2：“相通”的可传递性。若状态i与状态j相通，状态j与状态k相通，则由状态i与状态k相通。定义4：闭集。设C为马尔可夫链状态空间的一个子集，如果由C中的状态不
42、能到达C外的任何状态，则称C为闭集。即对于任意的m以及任意的iC定义5：吸收态。如果某个状态i本身构成一个闭集，则称其为吸收态，该状态不能到达任何其他的状态(但其他状态有可能到达该状态)(只要进入该状态，则永远不变)定理4：不可约的马尔可夫链除整个状态空间外没有别的闭集(只有1个闭集：状态全集)，所有状态之间是相通的。以闭集为状态集,本身可以构成马尔可夫链湖南大学教学课件：应用统计学与随机过程 马尔可夫过程状态分析举例：设某个齐次马尔可夫链的状态集为0，1，2，3，一步转移概率矩阵为定理5：若闭集包含不止一个状态，则这些状态之间的转移概率构成随机矩阵p，满足闭集中的切科公式湖南大学教学课件：应
43、用统计学与随机过程 马尔可夫过程0,1相通，2可到达0,1,3；0,1不可到达2,3；3不可到达0,1,20,1集合内的转移构成随机矩阵湖南大学教学课件：应用统计学与随机过程 马尔可夫过程定义6：首次到达概率 fij(m)。由状态i出发经过m次转移才第1次到达j的概率定义7：迟早到达概率 fij。由i出发(迟早)到达j的概率显然显然不相容事件的分解,思考为什么不是pij(m)之和?湖南大学教学课件：应用统计学与随机过程 马尔可夫过程定义7：首次到达时间Tij (至少要多少步才能从i转移到j)定理6：根据概率论容易得到转移概率与首次到达概率之间的关系为(证明：略)当i=j时，Tii表示由状态i出
44、发首次折返到i所需的最小时间定理7：i可到达j的充要条件是迟早到达概率fij0；i,j相通的充要条件是fij0， fji0。根据不相容事件的分解由j出发经过(n-v)步转移处于状态j(包括转到其他再转回j)湖南大学教学课件：应用统计学与随机过程 马尔可夫过程定义8：常返态。如果fii=1，则称状态i为常返态，即从i出发，不管走什么路径，迟早能返回到i。定义9：滑过态。如果fii0采用反证法思考:湖南大学教学课件：应用统计学与随机过程 马尔可夫过程附录(自学)：定义随机过程则原式即X(0)=ai情况下序列X(0),X(1),X(k),.,X()出现ai的总次数的平均值。由于X(0)=ai情况下迟
45、早返回ai的概率为fii，用不返回ai的概率为(1-fii)，则X(0),X(1),X(k),.,X()出现ai的次数为m注： X(0)=ai已经算1次即m-1次返回后不再返回的概率为fiim-1(1-fii)，则从次数的平均值为湖南大学教学课件：应用统计学与随机过程 马尔可夫过程证毕。湖南大学教学课件：应用统计学与随机过程 马尔可夫过程定理10：对于有限状态的马尔可夫链，至少有一个状态为常返态。 理解：如果都是非常返态，则经过有限的时间后不访问所有的状态了，与“任意时刻必处于某一状态”相背。定理11：如果i与j相通，i是常返的，则j也是常返的。定理12：如果某个子集上的各个状态是彼此相通的，
46、称为一个类，如果一个状态为常返，则类中所有状态为常返，如果一个为非常返，则类中所有状态为非常返。定理13：若状态i为非常返的，则对任意的j，有湖南大学教学课件：应用统计学与随机过程 马尔可夫过程状态分析举例2 (自学)：有五个状态0,1,2,3,4的马尔可夫链，其一步转移概率矩阵如下，试对其状态进行分类012341/21/21/21/21/21/21/21/21/41/41/2常返态集常返态集2，3常返态集常返态集0，1滑过态滑过态湖南大学教学课件：应用统计学与随机过程 马尔可夫过程从0,1,2,3的任何一个状态出发(不管走什么路径)，可以返回，再出发，再返回，；其中0,1相通，构成常返态集；
47、2,3相通，构成另外一个常返态集；从状态4出发后，不管是转到0或1，都不会返回。10 110 0 1以m=3为例：1111,1101,1011,1001的转移概率1/8湖南大学教学课件：应用统计学与随机过程 马尔可夫过程状态分析举例3 (自学)：有三个状态0,1,2的马尔可夫链，其一步转移概率矩阵及二步转移概率矩阵如下:求从状态1(取值为0)出发分别经过3、2步、1步第1次返回0的概率，并验证定理6。解：根据马尔可夫过程的性质，有湖南大学教学课件：应用统计学与随机过程 马尔可夫过程i=1,j=1i=1,j=2i=2,j=1i=2,j=2湖南大学教学课件：应用统计学与随机过程 马尔可夫过程同理可
48、求得:湖南大学教学课件：应用统计学与随机过程 马尔可夫过程矩阵P(3)的第1行第1列,为P(1)的第1行与P(2)的第1列的内积或为P(2)的第1行与P(1)的第1列的内积泊松过程泊松过程7.51.泊松过程的数学定义湖南大学教学课件：应用统计学与随机过程 马尔可夫过程前面介绍了马尔可夫序列(时间离散状态连续)、马尔可夫链(时间状态均离散)、连续马尔可夫过程(时间状态均连续)，本节介绍时间连续但状态离散的马尔可夫过程，最典型的代表泊松过程一个随机过程X(t)(t0)若满足如下条件，称为泊松过程：(1)记开始观测的时间起点为t=0，X(0)=0；(2)X(t)是t的非减函数，取值为离散的非负整数，
49、且满足独立增量特性，即对任意的0t1t2t3t1B. 如果 t2t1 (同理可以推得)独立增量特性4.泊松过程有关特征的分布特性湖南大学教学课件：应用统计学与随机过程 马尔可夫过程(1) 第1个事件的到达时间分布这个事件发生的时间t是一个随机变量，记为T1举例：某处第1次有车通过的时刻相对于起点观测时刻的差T1是随机变量，不同的观测得到不同的值。显然：对于任意的t0随机变量T1的概率分布函数湖南大学教学课件：应用统计学与随机过程 马尔可夫过程(2) 事件之间的时间间隔分布显然：对于任意的t0与这两个事件发生的时间差为随机变量，记为Tn举例：从第n-1辆车通过某处至第n辆车通过该处的时间差为随机
50、变量泊松过程(记数过程)的取值发生变化称为事件参见泊松过程概率分布函数的第一种表达式与n无关,任意两个事件之间的时间间隔的概率密度分布相同湖南大学教学课件：应用统计学与随机过程 马尔可夫过程性质：事件之间的平均时间间隔为1/。单位时间内的平均事件数为1/1/= (的物理含义)(3) 等待时间的分布从t=0开始观测到X(t)=n所需要的时间t是一个随机变量,记为Sn。根据独立/平稳增量特性容易证明，T1,T2,Tn统计独立；根据前面的推导，它们是同分布的，则特征函数满足如下特性：性质：事件之间的时间间隔分布与事件本身(编号n)无关;与上一个事件的发生时刻 也无关。Ti 与上一个事件的发生时刻T1
51、+T2+Ti-1无关湖南大学教学课件：应用统计学与随机过程 马尔可夫过程分布(练习：证明其0到正无穷大区间积分为1)附录(自学)：湖南大学教学课件：应用统计学与随机过程 马尔可夫过程附录(自学)：另外一种证明方法湖南大学教学课件：应用统计学与随机过程 马尔可夫过程第1项作变量置换：k-1k(4) 到达时间的条件分布扩展训练/练习已知(0,T)时间内出现了n次事件，即X(T)=n (n1)，求Sn、Sn-1的条件分布及联合条件分布，证明其不相互独立。湖南大学教学课件：应用统计学与随机过程 马尔可夫过程根据事件等价性已知X(T)=1情况下S1在0,T范围内均匀分布湖南大学教学课件：应用统计学与随机
52、过程 马尔可夫过程事件的分解，利用独立增量特性湖南大学教学课件：应用统计学与随机过程 马尔可夫过程湖南大学教学课件：应用统计学与随机过程 马尔可夫过程不满足统计独立条件湖南大学教学课件：应用统计学与随机过程 马尔可夫过程验证：三角区内，对于给定的t1=t,t2只能在t,T内变化；对于给定的t2=t,t1只能在0,t内变化Tt2t1Ttt湖南大学教学课件：应用统计学与随机过程 马尔可夫过程附录：(自学)不妨假设i5 ，提前发车时发送人数21；不提前发车(等5分钟)且每次发送的乘客数为k(0k20)的概率为具体计算结果(略)，可以通过Matlab的积分函数计算思考：NEX(5)=35=15则平均每次发送的人数为
