《随机过程与排队论08概要》由会员分享，可在线阅读，更多相关《随机过程与排队论08概要（37页珍藏版）》请在金锄头文库上搜索。
1、随机过程与排队论,计算机科学与工程学院 顾小丰 Email：guxf 2019年10月27日星期日,2019/10/27,计算机科学与工程学院 顾小丰,372,上一讲内容回顾,马尔可夫过程 马尔可夫过程的概念 马尔可夫过程的分类 离散参数马氏链 k步转移概率、 k步转移矩阵 齐次马尔可夫链,2019/10/27,计算机科学与工程学院 顾小丰,373,本讲主要内容,离散参数马氏链 齐次马氏链的性质链 初始分布、绝对分布、极限分布 遍历性 平稳性,2019/10/27,计算机科学与工程学院 顾小丰,374,3.2 离散参数马氏链,状态空间E和参数集T都是离散的马尔可夫过 程称为离散参数马氏链，简称
2、马氏链。即,设X(n),n=0,1,2,为随机序列，状态空间 E=0,1,2,。如果对于任意非负整数k、n1 n2njm及in1,in2,inj,im,im+kE马尔可夫性 PX(m+k)=im+k|X(n1)=in1, X(n2)=in2,X(nj)=inj,X(m)=im PX(m+k)=im+k|X(m)=im 成立，则称X(n),n=0,1,2,为离散参数马尔可夫链，简称马氏链。,2019/10/27,计算机科学与工程学院 顾小丰,375,k步转移概率,设X(n),n=0,1,2,为马氏链，E=0,1,2, ，称条件概率 pij(m,k)PX(m+k)=j|X(m)=i 为马氏链X(n
3、),n=0,1,在m时刻的k步转移概率.,k步转移概率的直观意义是：质点在时刻m时处于状态i，再经过k步(k个单位时间)处于状态j的条件概率。,特别地，k=1时， pij(m,1)PX(m+1)=j|X(m)=i 称为一步转移概率，简称转移概率。,2019/10/27,计算机科学与工程学院 顾小丰,376,k步转移矩阵,称矩阵,为马氏链X(n),n=0,1,在m时刻的k步转移矩阵。一步转移矩阵P(m,1)简称转移矩阵。,由转移概率的定义，显然有：,2019/10/27,计算机科学与工程学院 顾小丰,377,齐次马尔可夫链,若马氏链X(n),n=0,1,2,的转移概率pij(m,k)与m,无关，
4、即 pij(m,k)PX(m+k)=j|X(m)=ipij(k)； pij(m,1)PX(m+1)=j|X(m)=ipij(1)pij； 则称X(n),n=0,1,2,为齐次马尔可夫链，简称齐次马氏链。,齐次马氏链的k步转移矩阵记为： P(m,k)P(k)(pij(k)i,jE 一步转移矩阵，简称转移矩阵，记为： P(m,1)P(1)P(pij)i,jE 齐次马氏链的转移概率具有如下性质： 0pij(k)1， 0pij1，,2019/10/27,计算机科学与工程学院 顾小丰,378,例1 贝努里序列,如上节例2所述，贝努里序列是一个齐次马氏链，其转移矩阵为,一般地，独立同分布的离散随机变量序列
5、X(n),n=0,1,2,都是齐次马氏链。,2019/10/27,计算机科学与工程学院 顾小丰,379,例2 随机游动,一质点在数轴上的整数点上作随机游动的， 以X(n)表示时刻n质点的位置。质点在某一时刻m 时处于状态i，即X(m)=i，则下一步以概率q左移 到状态i-1，即pi,i-1(m,1)=q；而以概率p右移到状 态i+1，即pi,i+1(m,1)=p。因而质点将来所处的状 态X(m+1),X(m+2),X(m+k)等仅与现在所处的 状态X(m)=i有关，而与过去所处的状态无关。因 此，随机游动X(n),n=0,1,2,是齐次马氏链。 随机游动的统计特征由它在边界的特点决定， 下面给
6、出几种特殊的情形。,2019/10/27,计算机科学与工程学院 顾小丰,3710,1.自由(无限制)随机游动,状态空间E,-2,-1,0,1,2,两端无限 制。转移概率： pi,i-1q，pi,i+1p，其余pi,j0，ji-1,i+1,转移矩阵：,2019/10/27,计算机科学与工程学院 顾小丰,3711,2.两个吸收壁随机游动,状态空间E1,2,3,4,5。转移概率 p11p551；p1j0，j1；p5j0，j5； pi,i-1q，pi,i+1p，i=2,3,4； pi,j0，ji-1,i+1。 质点运动到1,5时，永远留在那里，称状态1,5为 吸收壁(状态)。,转移矩阵：,2019/1
7、0/27,计算机科学与工程学院 顾小丰,3712,3.带有两个反射壁的随机游动,状态空间E1,2,3,4,5。转移概率： p110，p121，p1j0，j=3,4,5； p550，p541，p5j0，j=1,2,3； pi,i-1q，pi,i+1p，i=2,3,4； pij0，ji-1,i+1，i=2,3,4。 状态1和5永远不能停留，称为反射壁。,转移矩阵：,2019/10/27,计算机科学与工程学院 顾小丰,3713,3.带有两个弹性壁的随机游动,状态空间E1,2,3,4,5。转移概率： p11q，p12p，p1j0，j=3,4,5； p55p，p54q，p5j0，j=1,2,3； pi,
8、i-1q，pi,i+1p，i=2,3,4； pij0，ji-1,i+1，i=2,3,4。 状态1和5称为弹性壁。,转移矩阵：,2019/10/27,计算机科学与工程学院 顾小丰,3714,齐次马氏链的性质1,齐次马氏链X(n),n=0,1,2,的转移概率pij(k)满足C-K方程(Chapman-Kolmogrov)。,采用矩阵记号为： P(k+s)P(k)P(s)。,证明,pij(k+s)PX(m+k+s)=j|X(m)=i,带条件的乘法公式： P(A1A2|B)=P(A1|B)P(A2|A1B),全概率公式,2019/10/27,计算机科学与工程学院 顾小丰,3715,齐次马氏链的性质2,
9、齐次马氏链X(n),n=0,1,2,的n步转移矩阵等于一步转移矩阵的n次方，即：P(n)Pn。,证明 由C-K方程有： P(k+s)P(k)P(s)。 令k=s=1，有：P(2)P(1)P(1)P2； 令k=2,s=1，有：P(3)P(2)P(1)P2PP3； 由数学归纳法得：P(n)Pn。 齐次马氏链的n布转移概率由一步转移概率确定,2019/10/27,计算机科学与工程学院 顾小丰,3716,齐次马氏链的性质3,给定齐次马氏链X(n),n=0,1,2,，称 piPX(0)=i iE， 即X(0)概率分布，为齐次马氏链的初始分布。 其中0pi1,iE且 1，记,证明 pj(n)PX(n)=j
10、,性质3 绝对分布由初始分布和转移概率确定，且满足,给定齐次马氏链X(n),n=0,1,2,，称 pi(n)PX(n)=i iE， 即X(n)概率分布，为齐次马氏链的绝对分布。 其中0pi(n)1,iE且 1，记,或记为,2019/10/27,计算机科学与工程学院 顾小丰,3717,齐次马氏链的性质4,齐次马氏链的有限维分布由初始分布和转移概率确定，且满足,证明 PX(n1)=i1,X(n2)=i1,X(nk)=ik,PX(n1)=i1,X(n2)=i1,X(nk)=ik,其中PX(n1)=i1,X(n2)=i1,X(nk)=ik为齐次马氏链的k维概率分布。,2019/10/27,计算机科学与
11、工程学院 顾小丰,3718,遍历性、极限分布,设X(n),n=0,1,2,为齐次马氏链，如果对,一切状态i和j，存在与i无关的极限,则称此马氏链具有遍历性。,如果j0, jE且 1，则称(j,jE)为齐次马氏链X(n),n=0,1,2,的极限分布，或称最终分布，记为 (j,jE),2019/10/27,计算机科学与工程学院 顾小丰,3719,齐次马氏链的性质5,设齐次马氏链X(n),n=0,1,2,的状态空间,E=1,2,s为有限，若存在正整数n0,对任意i, jE，有pij(n0)0，则此马氏链是遍历的，且极限分布是方程组,在满足条件,下的唯一解。,2019/10/27,计算机科学与工程学院
12、 顾小丰,3720,推论,设齐次马氏链X(n),n=0,1,2,具有遍历性，则,即遍历的齐次马氏链的绝对分布与转移概率有相同的极限。,证明 由绝对分布的性质,两边对n取极限,2019/10/27,计算机科学与工程学院 顾小丰,3721,齐次马氏链的性质6,设X(n),n=0,1,2,为齐次马氏链，若存在一个分,布V=(vj,jE)满足下列条件,则称此马氏链是平稳的，称V=(vj,jE)为此马氏链的平稳分布，即VVP。,性质6 遍历的齐次马氏链的极限分布是平稳分布。,证明 设齐次马氏链X(n),n=0,1,2,具有遍历性，即,故j,jE为极限分布，由C-K方程,令n有：,则(j,jE)为马氏链X
13、(n),n=0,1,2,的平稳分布。,2019/10/27,计算机科学与工程学院 顾小丰,3722,齐次马氏链的性质7,设X(n),n=0,1,2,的平稳分布为vj,jE，则有 VVPn， n=0,1,2,证明 由平稳分布的定义和C-K方程得,即有：VVP2。,容易由数学归纳法证得：,即证得：VVPn。,2019/10/27,计算机科学与工程学院 顾小丰,3723,齐次马氏链的性质8,如果齐次马氏链X(n),n=0,1,2,的初始分布pj,jE恰好是平稳分布，则对一切n有 pj(n)pj， n=0,1,2,，jE 即,证明 设初始分布pj,jE是平稳分布，由性质3和性质7得,由此性质可知，如果
14、齐次马氏链的初始分布为平稳分布，则绝对分布将始终等于初始分布，而不随时间的推移而改变，即系统具有平稳性。,2019/10/27,计算机科学与工程学院 顾小丰,3724,重要推论,设齐次马氏链X(n),n=0,1,2,的状态空间有,限E=1,2,s，若存在正整数n0,对任意i,jE，n0步转移概率pij(n0)0，则此链是遍历的，且极限分布等于平稳分布。,此结果在概率上可以具体求出平稳分布，在代数上是方程组的求解问题，即系数矩阵是转移矩阵的方程组的求解问题。,2019/10/27,计算机科学与工程学院 顾小丰,3725,齐次马氏链例3,在传送数字0和1的通讯系统中，每一传送数字必须经过若干级。第
15、i级正确传送的概率为pi，X(0)表示进入系统第一级的数字，X(n)表示离开通讯系统第n级的数字。X(n)，n=0,1,2,是状态空间E0,1的齐次马氏链。若更设pip（与状态无关）。,(1)转移概率矩阵,(2)n步转移矩阵,为求Pn，先求P的特征值和特征向量,求得特征值1=1和2=p-q，特征向量,2019/10/27,计算机科学与工程学院 顾小丰,3726,齐次马氏链例3(续1),正交，将其单位化得,得正交矩阵,2019/10/27,计算机科学与工程学院 顾小丰,3727,齐次马氏链例3(续2),(3)讨论遍历性，求极限分布和平稳分布,令n，由于|p-q|1，所以,由遍历性的定义，此马氏链遍历。（也可利用性质5，状态有限，n01，pij0，i,jE，知其遍历）,平稳分布等于极限分布,故(0,1),2019/10/27,计算机科学与工程学院 顾小丰,3728,齐次马氏链例4,设有6个球(其中2个红球4个白球)分别放于甲、乙两个盒子中，每盒3个。令每次从两个盒子中各取一个球进行交换，X(0)表示开始时甲盒中红球的个数，X(n),n=1,2,表示经过n
