马尔科夫链的状态分类要点课件

马尔可夫链的状态分类一、互通与闭集1．互通则称自状态i可到达状态j则称状态i和状态j互通说明如果自状态i不能到达状态j，马尔可夫链的状态分类一、互通与闭集1．互通则称自状态i可到达定理1即它满足（1）自反性（2）对称性证（3）传递性（1），（2）显然，下证（3）定理1即它满足（1）自反性（2）对称性证（3）传递性（1），证3则由相通定义，根据切普曼---柯尔莫哥洛夫方程，有同理可证证3则由相通定义，根据切普曼---柯尔莫哥洛夫方程，有同理可说明

按互通关系是等价关系，可以把状态空间S划分为若干个不相交的集合（或者说等价类），并称之为状态类。若两个状态互通，则这两个状态属于同一类。任意两个类或不相交或者相同。2．闭集设C为状态空间S的一个子集，则C称为闭集注1

若C为闭集，则表示自C内任意状态i出发，始终不能到达C以外的任何状态j。显然，整个状态空间构成一个闭集。说明按互通关系是等价关系，可以把状态空间S吸收态指一个闭集中只含一个状态注2若状态空间含有吸收状态，那么这个吸收状态构成一个最小的闭集。3．不可约的

若除整个状态空间S以外没有其它的闭集，则称此马氏链是不可约的。

如果闭集C的状态都是互通的，则称闭集C是不可约的。吸收态指一个闭集中只含一个状态注2若状态空间含有吸收状态，那例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。解先按一步转移概率，画出各状态间的传递图例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。2/31/41/41/31/21/20121/2图3---1由图可知状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0。因此，状态空间S的各状态都是互通的。又由于S的任意状态i(i=0，1，2)不能到达S以外的任何状态，所以S是一个闭集而且S中没有其它闭集所以此马氏链是不可约的。2/31/41/41/31/21/20121/2图3---1例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。解先按一步转移概率，画出各状态间的传递图例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。111/21/21/2311/2图3---24521

闭集，由图可知状态3为吸收态且闭集，闭集，其中是不可约的。又因状态空间S有闭子集，故此链为非不可约链。111/21/21/2311/2图3---24521二、首达时间和状态分类1．首达时间系统从状态i出发，首次到达状态j的时刻称为从状态i出发首次进入状态j的时间，或称自i到j的首达时间。如果这样的n不存在，就规定说明二、首达时间和状态分类1．首达时间系统从状态i出发，首次到自状态i出发，经过n步首次到达状态j的概率自状态i出发，经有穷步终于到达状态j的概率注1自状态i出发，经过n步首次到达状态j的概率自状态i出发，对于首次到达时间表示从状态i出发首次返回状态i所需的时间相应的便是从状态i出发，经有限步终于返回状态i的概率，对于首次到达时间表示从状态i出发首次返回状态i所需的时间相2．首次到达分解式定理2

证设系统从状态i经n步转移到状态j，由条件概率及马氏性得对任意IjiÎ,及1³n，有2．首次到达分解式定理2证设系统从状态i经n步转移到状态说明(m=1，2，…，n)的所有可能值进行分解，定理3

证充分性由定理2得从而所以说明(m=1，2，…，n)的所有可能值进行分解，定理3必要性由定理2得所以推论必要性由定理2得所以推论3．常返态与瞬时态则称状态i为常返态则称状态i为瞬时态注“常返”一词，有时又称“返回”、“常驻”或“持久”“瞬时”也称“滑过”或“非常返”定理4证则系统从状态i出发，经过有限次转移之后，必定以概率1返回状态i。再由马氏性系统返回状态i要重复发生3．常返态与瞬时态则称状态i为常返态则称状态i为瞬时态注“常这样，系统从状态i出发，又返回，再出发，再返回，随着时间的无限推移，将无限次访问状态i。将“不返回i”称为成功，则首次成功出现的次数服从几何分布，这就是说也就是说以概率1只有有穷次返回i。这样，系统从状态i出发，又返回，再出发，再返回，随着时间的无定理5证

令n=0，1，2，…因此，从状态i出发，访问状态i的平均次数为由定理4，得证。定理5证令n=0，1，2，…因此，从状态i出发，访问状说明本定理的等价形式：i为瞬时态，当且仅当定理6证如果i为常返态，且，则j也是常返态。因由切普曼---可尔莫哥洛夫方程得上式两边对所有的s相加，得又因为i为常返态，所以说明本定理的等价形式：i为瞬时态，当且仅当定理6证如果i为常故得从而即状态j也是常返态定理7所有常返态构成一个闭集证设i为常返态，即i和j相通。这是因为若自j出发不能到达i，那么从i出发到达j后，就不能再返回i，这与i是常返态的相矛盾。再由定理6知，j也是常返态，这就是说，自常返态出发，只能到达常返态，不能到达瞬时态。故常返态全体构成一个闭集故得从而即状态j也是常返态定理7所有常返态构成一个闭集证设i4．状态空间的分解如果已知类中有一个常返态，则这个类中其它状态都是常返的；若类中有一个瞬时态，则类中其它状态都是瞬时态。若对不可约马氏链，则要么全是常返态，要么全是瞬时态。定理8任一马氏链的状态空间S必可分解为其中N是瞬时态集，而且4．状态空间的分解如果已知类中有一个常返态，则这个类中其它状证记C为全体常返态所构成的集合，则由定理7知C为闭集将C按互通关系分类：那么再从余下的状态中任取一个状态如此进行下去，并且显然满足条件（1）和（2）。证记C为全体常返态所构成的集合，则由定理7知C为闭集将C按互5．正常返态与零常返态平均返回时间从状态i出发，首次返回状态i的平均时间称为状态i平均返回时间.根据的值是有限或无限，可把常返态分为两类：设i是常返态，则称i为正常返态；则称i为零常返态。5．正常返态与零常返态平均返回时间从状态i出发，首次返回状态定理9设i是常返态，则（1）i是零常返态的充要条件是（2）i是正常返态的充要条件是证明（略）推论证因为如果j是零常返态，i是任一状态，则定理9设i是常返态，则（1）i是零常返态的充要条件是（2）i由定理9，上式第一项有从而推论得证。由定理9，上式第一项有从而推论得证。说明用极限判断状态类型的准则（2）i是零常返态（2）i是正常返态（1）i是瞬时态且且说明用极限判断状态类型的准则（2）i是零常返态（2）i是正常定理10证明由切普曼---可尔莫哥洛夫方程得由此可知由定理9知定理10证明由切普曼---可尔莫哥洛夫方程得由此可知由定理96．有限马氏链对有限状态的马氏链我们给出不加证明的性质定理11（1）瞬时态集N不可能是闭集；（2）至少有一个常返态；（3）不存在零常返态；（4）若链是不可约的，那么状态都是正常返的（5）其状态空间可分解为是互不相交的由正常返态组成的闭集。6．有限马氏链对有限状态的马氏链我们给出不加证明的性质定理1例3转移矩阵试对其状态分类。解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143例3转移矩阵试对其状态分类。解按一步转移概率，21/4111从图可知，此链的每一状态都可到达另一状态，即4个状态都是互通的。考虑状态1是否常返，从图可知，此链的每一状态都可到达另一状态，即4个状态都是互通类似地可求得所以于是状态1是常返的。又因为所以状态1是正常返的。由定理可知，此链所有状态都是正常返的。类似地可求得所以于是状态1是常返的。又因为所以状态1是正常返例4

设马氏链的状态空间S={0,1,2,…}，其一步转移概率为其中试证此马氏链是一个不可约常返态链证先证S不可约设i，j是I中任意两个状态，则有例4设马氏链的状态空间S={0,1,2,…}，其一步转移概类似地可证所以即I中任意两个状态都是相通的。因此，S是一个不可约的闭集再证S中状态0是一个常返态：由状态的转移规则，得所以类似地可证所以即I中任意两个状态都是相通的。因此，S是一个不由定义知状态0为常返态。因此，由定理知S中所有状态都是常返态。故此马氏链为不可约常返链。由定义知状态0为常返态。因此，由定理知S中所有状态都是常返态三、状态的周期与遍历1．周期状态对于任意的，令其中GCD表示最大公约数则称为周期态，则称为非周期态。定理12三、状态的周期与遍历1．周期状态对于任意的证所以存在正整数m、n，使则有则有因此有类似地可证得故证所以存在正整数m、n，使则有则有因此有类似地可证得故（2）所以从而i为非周期态。又因为马氏链不可约，所以j也是非周期态，从而该马氏链是非周期链。2．遍历状态若状态i是正常返且非周期，则称i为遍历状态。（2）所以从而i为非周期态。又因为马氏链不可约，所以j也是非例5设马氏链的状态空间S={0,1,2,…}，转移概率为试讨论各状态的遍历性。解根据转移概率作出状态传递图…1/21/21/21/21/21/20121/2图3---431/2例5设马氏链的状态空间S={0,1,2,…}，转移概率为从图可知，对任一状态都有，故由定理可知，S中的所以状态都是相通的，因此只需考虑状态0是否正常返即可。…故从而0是常返态。又因为所以状态0为正常返。又由于故状态0为非周期的从而状态0是遍历的。故所有状态i都是遍历的。从图可知，对任一状态都有习题课1．带有两个反射壁的随机游动如果状态空间S={0，1，2，…，m}，移动的规则是：（1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）；（2）若移动前在m处，则下一步以概率q向左移动一个单位，以概率p停留在原处；（3）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设表示在时刻n质点的位置，则{，}是一个齐次马氏链，写出其一步转移概率矩阵。习题课1．带有两个反射壁的随机游动如果状态空间S={0，qp右反射壁m-1mpq左反射壁120qp右反射壁m-1mpq左反射壁1202．带有反射壁的随机游动设随机游动的状态空间S={0，1，2，…}，移动的规则是：（1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）；（2）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设表示在时刻n质点的位置，则{，}是一个齐次马氏链，写出其一步转移概率。2．带有反射壁的随机游动设随机游动的状态空间S={0，1pq反射壁1230pq反射壁12303．一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作随机游动，移动的规则是：质点总是以概率p顺时针游动一格，以概率逆时针游动一格。试求转移概率矩阵。3．一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作4．一个质点在全直线的整数点上作随机游动，移动的规则是：以概率p从i移到i-1，以概率q从i移到i+1，以概率r停留在i，且，试求转移概率矩阵。4．一个质点在全直线的整数点上作随机游动，移动的规则是：以概5．设袋中有a个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。若在袋里有k个白球，则称系统处于状态k，试用马尔可夫链描述这个模型（称为爱伦菲斯特模型），并求转移概率矩阵。解这是一个齐次马氏链，其状态空间为S={—a，—a+1，…，—1，0，1，2，…，a}一步转移矩阵是5．设袋中有a个球，球为黑色的或白色的，今随机地从袋中取一个1/31/211/31/211/312346．设马氏链的状态空间S={1，2，3，4}，其一步转移矩阵为解试对其状态分类。按一步转移概率，画出各状态间的传递图它是有限状态的马氏链，故必有一个常返态，又链中四个状态都是互通的。因此，所有状态都是常返态，这是一个有限状态不可约的马氏链。可继续讨论是否为正常返态1/31/211/31/211/312346．设马氏链的状态可讨论状态11/31/211/31/211/31234可讨论状态11/31/211/31/211/31234状态1是常返态状态1是正常返态所以，全部状态都是正常返态状态1是常返态状态1是正常返态所以，全部状态都是正常返态7．设马氏链的状态空间S={1，2，3，4，5}，其一步转移矩阵为试研究各状态的类及周期性解各状态间的传递图7．设马氏链的状态空间S={1，2，3，4，5}，其一步转移对于任意有，即S为不可再分闭集。所以S中每一个状态都是常返态，且此马氏链为有限状态不可约常返链。0.40.2110.50.50.80.631254所以状态1的周期为3，由定理知，S中所有状态都为周期态，且周期都为3。因此，这个马氏链又是以3为周期的周期链。又因为马氏链为有限状态不可约链，所以所有状态都是正常返状态。对于任意有，所以S8．设马氏链的状态空间为S={1，2，3}，其一步转移矩阵为试研究各状态间的关系。解0.50.50.5120.513可继续讨论正常返8．设马氏链的状态空间为S={1，2，3}，其一步转移矩9．设马氏链的状态空间为S={1，2，3，4}，其一步转移矩阵为试研究各状态间的关系。解10.60.20.20.71120.334状态空间为S分两个部分：={1，2，3}，={4}

是闭集

中状态4可到达中各状态，且它非吸收状态，所以不是闭集。9．设马氏链的状态空间为S={1，2，3，4}，其一步转马尔可夫链的状态分类一、互通与闭集1．互通则称自状态i可到达状态j则称状态i和状态j互通说明如果自状态i不能到达状态j，马尔可夫链的状态分类一、互通与闭集1．互通则称自状态i可到达定理1即它满足（1）自反性（2）对称性证（3）传递性（1），（2）显然，下证（3）定理1即它满足（1）自反性（2）对称性证（3）传递性（1），证3则由相通定义，根据切普曼---柯尔莫哥洛夫方程，有同理可证证3则由相通定义，根据切普曼---柯尔莫哥洛夫方程，有同理可说明

按互通关系是等价关系，可以把状态空间S划分为若干个不相交的集合（或者说等价类），并称之为状态类。若两个状态互通，则这两个状态属于同一类。任意两个类或不相交或者相同。2．闭集设C为状态空间S的一个子集，则C称为闭集注1

若C为闭集，则表示自C内任意状态i出发，始终不能到达C以外的任何状态j。显然，整个状态空间构成一个闭集。说明按互通关系是等价关系，可以把状态空间S吸收态指一个闭集中只含一个状态注2若状态空间含有吸收状态，那么这个吸收状态构成一个最小的闭集。3．不可约的

若除整个状态空间S以外没有其它的闭集，则称此马氏链是不可约的。

如果闭集C的状态都是互通的，则称闭集C是不可约的。吸收态指一个闭集中只含一个状态注2若状态空间含有吸收状态，那例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。解先按一步转移概率，画出各状态间的传递图例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。2/31/41/41/31/21/20121/2图3---1由图可知状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0。因此，状态空间S的各状态都是互通的。又由于S的任意状态i(i=0，1，2)不能到达S以外的任何状态，所以S是一个闭集而且S中没有其它闭集所以此马氏链是不可约的。2/31/41/41/31/21/20121/2图3---1例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。解先按一步转移概率，画出各状态间的传递图例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。111/21/21/2311/2图3---24521

闭集，由图可知状态3为吸收态且闭集，闭集，其中是不可约的。又因状态空间S有闭子集，故此链为非不可约链。111/21/21/2311/2图3---24521二、首达时间和状态分类1．首达时间系统从状态i出发，首次到达状态j的时刻称为从状态i出发首次进入状态j的时间，或称自i到j的首达时间。如果这样的n不存在，就规定说明二、首达时间和状态分类1．首达时间系统从状态i出发，首次到自状态i出发，经过n步首次到达状态j的概率自状态i出发，经有穷步终于到达状态j的概率注1自状态i出发，经过n步首次到达状态j的概率自状态i出发，对于首次到达时间表示从状态i出发首次返回状态i所需的时间相应的便是从状态i出发，经有限步终于返回状态i的概率，对于首次到达时间表示从状态i出发首次返回状态i所需的时间相2．首次到达分解式定理2

证设系统从状态i经n步转移到状态j，由条件概率及马氏性得对任意IjiÎ,及1³n，有2．首次到达分解式定理2证设系统从状态i经n步转移到状态说明(m=1，2，…，n)的所有可能值进行分解，定理3

证充分性由定理2得从而所以说明(m=1，2，…，n)的所有可能值进行分解，定理3必要性由定理2得所以推论必要性由定理2得所以推论3．常返态与瞬时态则称状态i为常返态则称状态i为瞬时态注“常返”一词，有时又称“返回”、“常驻”或“持久”“瞬时”也称“滑过”或“非常返”定理4证则系统从状态i出发，经过有限次转移之后，必定以概率1返回状态i。再由马氏性系统返回状态i要重复发生3．常返态与瞬时态则称状态i为常返态则称状态i为瞬时态注“常这样，系统从状态i出发，又返回，再出发，再返回，随着时间的无限推移，将无限次访问状态i。将“不返回i”称为成功，则首次成功出现的次数服从几何分布，这就是说也就是说以概率1只有有穷次返回i。这样，系统从状态i出发，又返回，再出发，再返回，随着时间的无定理5证

令n=0，1，2，…因此，从状态i出发，访问状态i的平均次数为由定理4，得证。定理5证令n=0，1，2，…因此，从状态i出发，访问状说明本定理的等价形式：i为瞬时态，当且仅当定理6证如果i为常返态，且，则j也是常返态。因由切普曼---可尔莫哥洛夫方程得上式两边对所有的s相加，得又因为i为常返态，所以说明本定理的等价形式：i为瞬时态，当且仅当定理6证如果i为常故得从而即状态j也是常返态定理7所有常返态构成一个闭集证设i为常返态，即i和j相通。这是因为若自j出发不能到达i，那么从i出发到达j后，就不能再返回i，这与i是常返态的相矛盾。再由定理6知，j也是常返态，这就是说，自常返态出发，只能到达常返态，不能到达瞬时态。故常返态全体构成一个闭集故得从而即状态j也是常返态定理7所有常返态构成一个闭集证设i4．状态空间的分解如果已知类中有一个常返态，则这个类中其它状态都是常返的；若类中有一个瞬时态，则类中其它状态都是瞬时态。若对不可约马氏链，则要么全是常返态，要么全是瞬时态。定理8任一马氏链的状态空间S必可分解为其中N是瞬时态集，而且4．状态空间的分解如果已知类中有一个常返态，则这个类中其它状证记C为全体常返态所构成的集合，则由定理7知C为闭集将C按互通关系分类：那么再从余下的状态中任取一个状态如此进行下去，并且显然满足条件（1）和（2）。证记C为全体常返态所构成的集合，则由定理7知C为闭集将C按互5．正常返态与零常返态平均返回时间从状态i出发，首次返回状态i的平均时间称为状态i平均返回时间.根据的值是有限或无限，可把常返态分为两类：设i是常返态，则称i为正常返态；则称i为零常返态。5．正常返态与零常返态平均返回时间从状态i出发，首次返回状态定理9设i是常返态，则（1）i是零常返态的充要条件是（2）i是正常返态的充要条件是证明（略）推论证因为如果j是零常返态，i是任一状态，则定理9设i是常返态，则（1）i是零常返态的充要条件是（2）i由定理9，上式第一项有从而推论得证。由定理9，上式第一项有从而推论得证。说明用极限判断状态类型的准则（2）i是零常返态（2）i是正常返态（1）i是瞬时态且且说明用极限判断状态类型的准则（2）i是零常返态（2）i是正常定理10证明由切普曼---可尔莫哥洛夫方程得由此可知由定理9知定理10证明由切普曼---可尔莫哥洛夫方程得由此可知由定理96．有限马氏链对有限状态的马氏链我们给出不加证明的性质定理11（1）瞬时态集N不可能是闭集；（2）至少有一个常返态；（3）不存在零常返态；（4）若链是不可约的，那么状态都是正常返的（5）其状态空间可分解为是互不相交的由正常返态组成的闭集。6．有限马氏链对有限状态的马氏链我们给出不加证明的性质定理1例3转移矩阵试对其状态分类。解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143例3转移矩阵试对其状态分类。解按一步转移概率，21/4111从图可知，此链的每一状态都可到达另一状态，即4个状态都是互通的。考虑状态1是否常返，从图可知，此链的每一状态都可到达另一状态，即4个状态都是互通类似地可求得所以于是状态1是常返的。又因为所以状态1是正常返的。由定理可知，此链所有状态都是正常返的。类似地可求得所以于是状态1是常返的。又因为所以状态1是正常返例4

设马氏链的状态空间S={0,1,2,…}，其一步转移概率为其中试证此马氏链是一个不可约常返态链证先证S不可约设i，j是I中任意两个状态，则有例4设马氏链的状态空间S={0,1,2,…}，其一步转移概类似地可证所以即I中任意两个状态都是相通的。因此，S是一个不可约的闭集再证S中状态0是一个常返态：由状态的转移规则，得所以类似地可证所以即I中任意两个状态都是相通的。因此，S是一个不由定义知状态0为常返态。因此，由定理知S中所有状态都是常返态。故此马氏链为不可约常返链。由定义知状态0为常返态。因此，由定理知S中所有状态都是常返态三、状态的周期与遍历1．周期状态对于任意的，令其中GCD表示最大公约数则称为周期态，则称为非周期态。定理12三、状态的周期与遍历1．周期状态对于任意的证所以存在正整数m、n，使则有则有因此有类似地可证得故证所以存在正整数m、n，使则有则有因此有类似地可证得故（2）所以从而i为非周期态。又因为马氏链不可约，所以j也是非周期态，从而该马氏链是非周期链。2．遍历状态若状态i是正常返且非周期，则称i为遍历状态。（2）所以从而i为非周期态。又因为马氏链不可约，所以j也是非例5设马氏链的状态空间S={0,1,2,…}，转移概率为试讨论各状态的遍历性。解根据转移概率作出状态传递图…1/21/21/21/21/21/20121/2图3---431/2例5设马氏链的状态空间S={0,1,2,…}，转移概率为从图可知，对任一状态都有，故由定理可知，S中的所以状态都是相通的，因此只需考虑状态0是否正常返即可。…故从而0是常返态。又因为所以状态0为正常返。又由于故状态0为非周期的从而状态0是遍历的。故所有状态i都是遍历的。从图可知，对任一状态都有习题课1．带有两个反射壁的随机游动如果状态空间S={0，1，2，…，m}，移动的规则是：（1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）；（2）若移动前在m处，则下一步以概率q向左移动一个单位，以概率p停留在原处；（3）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设表示在时刻n质点的位置，则{，}是一个齐次马氏链，写出其一步转移概率矩阵。习题课1．带有两个反射壁的随机游动如果状态空间S={0，qp右反射壁m-1mpq左反射壁120qp右反射壁m-1mpq左反射壁1202．带有反射壁的随机游动设随机游动的状态空间S={0，1，2，…}，移动的规则是：（1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）；（2）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设表示在时刻n质点的位置，则{，}是一个齐次马氏链，写出其一步转移概率。2．带有反射壁的随机游动设随机游动的状态空间S={0，1pq反射壁1230pq反射壁12303．一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作随机游动，移动的规则是：质点总是以概率p顺时针游动一格，以概率逆时针游动一格。试求转移概率矩阵。3．一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作4．一个质点在全