马尔可夫过程基础

,马尔可夫过程,第一节马尔可夫链的定义及其性质,第二节马尔可夫链的状态分类,第三节平稳分布与遍历性,第四节时间连续的马尔可夫链,第一节马尔可夫链的定义及其性质,一、马尔可夫链的定义,1马尔可夫链,注:,而与以前的状态,有限马氏链,状态空间是有限集I=0,1,2,，k,2一步转移概率,马氏链在时刻n处于状态i的条件下，到时刻n+1转移到状态j的条件概率，,即,称为在时刻n的一步转移概率，,注:,由于概率是非负的，且过程从一状态出发，经过一步转移后，必到达状态空间中的某个状态,一步转移概率满足,3一步转移矩阵,称为在时刻n的一步转移矩阵,即有,有限马氏链,状态空间I=0，1，2，k,4齐次马氏链,即,则称此马氏链为齐次马氏链（即关于时间为齐次）,5初始分布,注,马氏链在初始时刻有可能处于I中任意状态，初始分布就是马氏链在初始时刻的概率分布。,6绝对分布,概率分布,称为马氏链的绝对分布或称绝对概率,定态分布,即,例1不可越壁的随机游动,设一质点在线段1，5上随机游动，状态空间I=1，2，3，4，5，每秒钟发生一次随机游动，移动的规则是：,（1）若移动前在2，3，4处，则均以概率向左或向右移动一单位，或停留在原处；,（2）若移动前在1处，则以概率1移到2处；,（3）若移动前在5处，则以概率1移到4处。,试写出一步转移矩阵.,分析,故,其一步转移矩阵为,若将移动规则改为,（1）若移动前在2，3，4处，则均以概率向左或向右移动一单位；（2）若移动前在1，5处，则以概率1停留在原处。,因为质点在1，5两点被“吸收”，,故称,有两个吸收壁的随机游动,分析,例2赌徒输光问题,赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为，求甲输光的概率。,这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢1元）的概率为p，向左移（即输1元）的概率为q。如果一旦到达0（即甲输光）或a+b（即乙输光）这个游动就停止。这时的状态空间为0，1，2，c，c=a+b，。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。,考虑质点从j出发移动一步后的情况,解,同理,根据全概率公式有,这一方程实质上是一差分方程，它的边界条件是,于是,设,则可得到两个相邻差分间的递推关系,于是,欲求,先求,需讨论r,当,而,两式相比,故,当,而,因此,故,用同样的方法可以求得乙先输光的概率,由以上计算结果可知,例3排队问题,顾客到服务台排队等候服务，在每一个服务周期中只要服务台前有顾客在等待，就要对排在前面的一位提供服务，若服务台前无顾客时就不能实施服务。,则有,求其转移矩阵,在第n周期已有一个顾客在服务，到第n+1周期已服务完毕,解,先求出转移概率,所以转移矩阵为,说明：,二、基本性质,性质1,的联合分布可由初始分布及转移概率所决定，即有,则,性质2,表明,一个马氏链，如果按相反方向的时间排列，所成的序列也是一个马氏链。,性质3,表明,若已知现在，则过去与未来是独立的。,则,性质4,表明,若已知现在，则过去同时对将来各时刻的状态都不产生影响。,特别,则,性质5,表明,马氏链的子链也是马氏链,在马氏链的研究中，须研究“从已知状态i出发，经过n次转移后，系统将处于状态j”的概率.,三、n步转移矩阵,1n步转移概率,系统在时刻m从状态i经过n步转移后处于状态j的概率,称为n步转移概率,由于马氏链是齐次的，这个概率与m无关,显然有,2n步转移矩阵,称为n步转移矩阵,规定,3绝对概率公式,定理1,绝对概率由初始分布和n维转移概率完全确定,即有,证,注,若对定态分布，则,4切普曼-柯尔莫哥洛夫方程,定理2,则,证,注,（1）用一步转移概率表示多步转移概率,注,I=1，2，N,由矩阵的乘法规则，得,表示：在时刻n，各状态的概率等于其初始状态的概率与n步转移概率矩阵之积。,若链是齐次的，则有,例4,甲、乙两人进行比赛，设每局比赛中甲胜的概率是p，乙胜的概率是q，和局的概率是，（）。设每局比赛后，胜者记“+1”分，负者记“1”分，和局不记分。当两人中有一人获得2分结束比赛。以表示比赛至第n局时甲获得的分数。,（1）写出状态空间；,（3）问在甲获得1分的情况下，再赛二局可以结束比赛的概率是多少？,解,（1）,记甲获得“负2分”为状态1，获得“负1分”为状态2，获得“0分”为状态3，获得“正1分”为状态4，获得“正2分”为状态5，则状态空间为,一步转移概率矩阵,（2）二步转移概率矩阵,（3）,从而结束比赛的概率；,从而结束比赛的概率。,所以题中所求概率为,返回,第二节马尔可夫链的状态分类,一、相通与闭集,1相通,则称自状态i可到达状态j,则称状态i和状态j相通,说明,如果自状态i不能到达状态j，,定理1,即它满足,（1）自反性,（2）对称性,证,（3）传递性,（1），（2）显然，下证（3）,证3,则由相通定义，,根据切普曼-柯尔莫哥洛夫方程，有,同理可证,说明,按相通关系是等价关系，可以把状态空间I划分为若干个不相交的集合（或者说等价类），并称之为状态类。若两个状态相通，则这两个状态属于同一类。任意两个类或不相交或者相同。,2闭集,设C为状态空间I的一个子集，,则C称为闭集,注1,若C为闭集，则表示自C内任意状态i出发，始终不能到达C以外的任何状态j。显然，整个状态空间构成一个闭集。,吸收态,指一个闭集中只含一个状态,注2,若状态空间含有吸收状态，那么这个吸收状态构成一个最小的闭集。,3不可约的,若除整个状态空间I以外没有其它的闭集，则称此马氏链是不可约的。,如果闭集C的状态都是相通的，则称闭集C是不可约的。,例1,其一步转移矩阵为,试研究各状态间的关系，并画出状态传递图。,解,先按一步转移概率，画出各状态间的传递图,由图可知,状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0。,因此，状态空间I的各状态都是互通的。,又由于I的任意状态i(i=0，1，2)不能到达I以外的任何状态，,所以I是一个闭集,而且I中没有其它闭集,所以此马氏链是不可约的。,例2,其一步转移矩阵为,试讨论哪些状态是吸收态、闭集及不可约链。,解,先按一步转移概率，画出各状态间的传递图,闭集，,由图可知,状态3为吸收态,且,闭集，,闭集，,其中是不可约的。,又因状态空间I有闭子集，,故此链为非不可约链。,二、首达时间和状态分类,1首达时间,系统从状态i出发，首次到达状态j的时刻,称为从状态i出发首次进入状态j的时间，,或称自i到j的首达时间。,如果这样的n不存在，就规定,说明,自状态i出发，经过n步首次到达状态j的概率,自状态i出发，经有穷步终于到达状态j的概率,注1,对于首次到达时间,表示从状态i出发首次返回状态i所需的时间,相应的便是从状态i出发，经有限步终于返回状态i的概率，,2首次到达分解式,定理2,证,设系统从状态i经n步转移到状态j，,由条件概率及马氏性得,对任意,及,，有,说明,(m=1，2，n),的所有可能值进行分解，,定理3,证,充分性,由定理2得,从而,所以,必要性,由定理2得,所以,推论,3常返态与瞬时态,则称状态i为常返态,则称状态i为瞬时态,注,“常返”一词，有时又称“返回”、“常驻”或“持久”,“瞬时”也称“滑过”或“非常返”,定理4,证,则系统从状态i出发，经过有限次转移之后，必定以概率1返回状态i。,再由马氏性,系统返回状态i要重复发生,这样，系统从状态i出发，又返回，再出发，再返回，随着时间的无限推移，将无限次访问状态i。,将“不返回i”称为成功，,则首次成功出现的次数服从几何分布，,这就是说,也就是说以概率1只有有穷次返回i。,定理5,证,令,n=0，1，2，,因此，从状态i出发，访问状态i的平均次数为,由定理4，得证。,说明,本定理的等价形式：,i为瞬时态，当且仅当,定理6,证,如果i为常返态，且，则j也是常返态。,因,由切普曼-可尔莫哥洛夫方程得,上式两边对所有的s相加，得,又因为i为常返态，,所以,故得,从而,即状态j也是常返态,定理7,所有常返态构成一个闭集,证,设i为常返态，,即i和j相通。,这是因为,若自j出发不能到达i，那么从i出发到达j后，就不能再返回i，这与i是常返态的相矛盾。,再由定理6知，j也是常返态，,这就是说，,自常返态出发，只能到达常返态，不能到达瞬时态。,故常返态全体构成一个闭集,4状态空间的分解,如果已知类中有一个常返态，则这个类中其它状态都是常返的；,若类中有一个瞬时态，则类中其它状态都是瞬时态。,若对不可约马氏链，则要么全是常返态，要么全是瞬时态。,定理8,任一马氏链的状态空间I必可分解为,其中N是瞬时态集，,而且,证,记C为全体常返态所构成的集合，,则由定理7知C为闭集,将C按相通关系分类：,那么再从余下的状态中任取一个状态,如此进行下去，,并且显然满足条件（1）和（2）。,5正常返态与零常返态,平均返回时间,从状态i出发，首次返回状态i的平均时间,称为状态i平均返回时间.,根据的值是有限或无限，可把常返态分为两类：,设i是常返态，,则称i为正常返态；,则称i为零常返态。,定理9,设i是常返态，则,（1）i是零常返态的充要条件是,（2）i是正常返态的充要条件是,证明（略）,推论,证,因为,如果j是零常返态，i是任一状态，则,由定理9，上式第一项有,从而推论得证。,说明,用极限判断状态类型的准则,（2）i是零常返态,（2）i是正常返态,（1）i是瞬时态,且,且,定理10,证明,由切普曼-可尔莫哥洛夫方程得,由此可知,由定理9知,6有限马氏链,对有限状态的马氏链我们给出不加证明的性质,定理11,（1）瞬时态集N不可能是闭集；（2）至少有一个常返态；（3）不存在零常返态；（4）若链是不可约的，那么状态都是正常返的（5）其状态空间可分解为,是互不相交的由正常返态组成的闭集。,例3,转移矩阵,试对其状态分类。,解,按一步转移概率，画出各状态间的传递图,从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。,考虑状态1是否常返，,类似地可求得,所以,于是状态1是常返的。,又因为,所以状态1是正常返的。,由定理可知，此链所有状态都是正常返的。,例4,设马氏链的状态空间I=0,1,2,，其一步转移概率为,其中,试证此马氏链是一个不可约常返态链,证,先证I不可约,设i，j是I中任意两个状态，,则有,类似地可证,所以,即I中任意两个状态都是相通的。,因此，I是一个不可约的闭集,再证I中状态0是一个常返态：,由状态的转移规则，得,所以,由定义知状态0为常返态。,因此，由定理知I中所有状态都是常返态。,故此马氏链为不可约常返链。,三、状态的周期与遍历,1周期状态,对于任意的，令,其中GCD表示最大公约数,则称为周期态，,则称为非周期态。,定理12,证,所以存在正整数m、n，使,则有,则有,因此有,类似地可证得,故,（2）,所以,从而i为非周期态。,又因为马氏链不可约，,所以j也是非周期态，,从而该马氏链是非周期链。,2遍历状态,若状态i是正常返且非周期，则称i为遍历状态。,例5,设马氏链的状态空间I=0,1,2,，转移概率为,试讨论各状态的遍历性。,解,根据转移概率作出状态传递图,从图可知，对任一状态都有，,故由定理可知，I中的所以状态都是相通的，,因此只需考虑状态0是否正常返即可。,故,从而0是常返态。,又因为,所以状态0为正常返。,又由于,故状态0为非周期的,从而状态0是遍历的。,故所有状态i都是遍历的。,返回,习题,1带有两个反射壁的随机游动,如果状态空间I=0，1，2，m，移动的规则是：（1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）；（2）若移动前在m处，则下一步以概率q向左移动一个单位，以概率p停留在原处；（3）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。,设表示在时刻n质点的位置，则，是一个齐次马氏链，写出其一步转移概率矩阵。,2带有反射壁的随机游动,设随机游动的状态空间I=0，1，2，移动的规则是：（1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）；（2）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。,设表示在时刻n质点的位置，则，是一个齐次马氏链，写出其一步转移概率。,3一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作随机游动，移动的规则是：质点总是以概率p顺时针游动一格，以概率逆时针游动一格。试求转移概率矩阵。,4一个质点在全直线的整数点上作随机游动，移动的规则是：以概率p从i移到i-1，以概率q从i移到i+1，以概率r停留在i，且，试求转移概率矩阵。,5设袋中有a个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。若在袋里有k个白球，则称系统处于状态k，试用马尔可夫链描述这个模型（称为爱伦菲斯特模型），并求转移概率矩阵。,解这是一个齐次马氏链，其状态空间为,I=a，a+1，1，0，1，2，a,一步转移矩阵是,6设马氏链的状态空间I=1，2，3，4，其一步转移矩阵为,解,试对其状态分类。,按一步转移概率，画出各状态间的传递图,它是有限状态的马氏链，故必有一个常返态，又链中四个状态都是互通的。因此，所有状态都是常返态，这是一个有限状态不可约的马氏链。,可继续讨论是否为正常返态,可讨论状态1,状态1是常返态,状态1是正常返态,所以，全部状态都是正常返态,7设马氏链的状态空间I=1，2，3，4，5，其一步转移矩阵为,试研究各状态的类及周期性,解,各状态间的传递图,对于任意有，即I为不可再分闭集。,所以I中每一个状态都是常返态，且此马氏链为有限状态不可约常返链。,所以状态1的周期为3，由定理知，I中所有状态都为周期态，且周期都为3。因此，这个马氏链又是以3为周期的周期链。,又因为马氏链为有限状态不可约链，所以所有状态都是正常返状态。,8设马氏链的状态空间为I=1，2，3，其一步转移矩阵为,试研究各状态间的关系。,解,可继续讨论正常返,首页,9设马氏链的状态空间为I=1，2，3，4，其一步转移矩阵为,试研究各状态间的关系。,解,状态空间为I分两个部分：=1，2，3，=4,是闭集,中状态4可到达中各状态，且它非吸收状态，所以不是闭集。,返回,第三节平稳分布与遍历性,一、平稳分布,定义1,其满足,绝对分布,定态分布,绝对概率公式,绝对概率由初始分布和n维转移概率完全确定,即,注,若对定态分布，则,性质1,定态分布一定是平稳分布,性质2,若初始分布是平稳分布，则绝对分布也是平稳分布,证,是平稳分布，则,从而得,（初始分布为平稳分布）,（切普曼-可尔莫哥洛夫方程）,由上式得,于是这时绝对分布是定态分布，从而它也是平稳分布。,二、遍历性,非周期、正常返状态为遍历状态,定义2,使得,则称此马氏链具有遍历性,马氏链的遍历性表明,不论从哪一个状态i出发，当转移的步数n充分大时，转移到状态j的概率都接近于正常数,定理1,则此马氏链是遍历的，,且,中的,是方程组,j=0，1，2，s,的满足条件,的唯一解,注1,定理表明不论从链中哪一状态i出发，都能以正概率经有限次转移到达链中预先指定的其它任一状态。,定理给出了求平稳分布的方法。,注2,例1,其一步转移矩阵为,试证此链具有遍历性，并求出平稳分布。,解,由于,所以,因此，该马氏链具有遍历性。,由定理1得,解得,所以马氏链的平稳分布为,定理2,（1）若状态是正常返，则该链存在平稳分布，且平稳分布,（其中是从状态j出发首次返回状态j的平均时间）,（2）若所有状态是瞬时态，或所有状态是零常返态，则不存在平稳分布。,（3）若是有限马氏链，则一定存在平稳分布。,（4）绝对分布的极限是平稳分布，即,例2,设有6个球（其中2个红球，4个白球）分放于甲、乙两个盒子中，每盒放3个，今每次从两个盒中各任取一球并进行交换，以表示开始时甲盒中红球的个数，（）表示经n次交换后甲盒中的红球数。,(1)求马氏链，的转移概率矩阵；,(2)证明，是遍历的；,（3）求,（4）求,解,其一步转移矩阵为,甲,乙,红球0白球3,红球2白球1,红球1白球2,红球1白球2,红球2白球1,红球0白球3,并作出状态传递图,（2）由于它是一个有限马氏链，故必有一个常返态，,又链中三个状态0、1、2都相通，所以每个状态都是常返态。所以是一个不可约的有限马氏链，从而每个状态都是正常返的。,所以此链为非周期的。,故此链是不可约非周期的正常返链，即此链是遍历的。,（2）可以利用定理证明遍历性,解之得,故得,（4）,例3,市场占有率预测,设某地有1600户居民，某产品只有甲、乙、丙3厂家在该地销售。经调查，8月份买甲、乙、丙三厂的户数分别为480，320，800。9月份里，原买甲的有48户转买乙产品，有96户转买丙产品；原买乙的有32户转买甲产品，有64户转买丙产品；原买丙的有64户转买甲产品，有32户转买乙产品。用状态1、2、3分别表示甲、乙、丙三厂，试求,（1）转移概率矩阵；（2）9月份市场占有率的分布；（3）12月份市场占有率的分布；（4）当顾客流如此长期稳定下去市场占有率的分布。,解,（1）由题意得频数转移矩阵为,再用频数估计概率，得转移概率矩阵为,（2）以1600除以N中各行元素之和，得初始概率分布（即初始市场占有率）,所以9月份市场占有率分布为,（3）12月份市场占有率分布为,（4）由于该链不可约、非周期、状态有限正常返的，所以是遍历的。,解方程组,即得当顾客流如此长期稳定下去是市场占有率的分布为,首页,讨论对时间连续状态离散的马尔可夫过程，取时间参数，状态空间I=0,1,2,第四节时间连续的马尔可夫链,一、定义及性质,时间连续的马尔可夫链,转移概率,齐次马氏链,转移概率仅由t决定而与s无关,2性质,性质1,切普曼柯尔莫哥洛夫方程,性质2,连续时间齐次马氏链的有限维概率分布由它的初始分布和转移矩阵所确定,注,性质3,注,对时间来说是可逆性,性质4,已知现在，那么过去与将来是独立,注,性质5（遍历性定理）,马尔可夫定理,设,是状态空间I=0,1，2,s的时间连续的齐次马氏链，,则,的满足条件,的唯一解。,例1,考虑一个电话总机接到的呼唤流，以表示这个总机在0，t中接到的呼唤次数，由于呼唤流在不相交的时间区间中接到的呼唤次数是相互独立的，且服从泊松分布，所以是一个时间连续状态离散的马氏过程，而且是齐次的。写出它的转移概率。,当呼唤次数时,转移概率,当时,其状态空间I=0，1，2，,转移概率为,1随机连续,则称是随机连续的。,定理1,二、可尔莫哥洛夫微分方程,时间连续的齐次马氏链,是随机连续的充要条件为：对任意的，有,随机连续直观意义,当系统经过很短时间，其状态几乎不变。,标准转移概率,若时间连续的齐次马氏链是随机连续的，则称其转移概率是标准的。并且满足性质:,2转移概率的性质,性质1,性质2,定理2,