马尔可夫过程

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