马尔科夫链基础

第六章离散时间马尔可夫链马尔可夫过程是前苏联数学家A.A.Markov首先提出和研究的一类随机过程.十九世纪后二十年Markov主要致力于独立随机变量和古典极值理论的研究,并改进和完善了大数定律和中心极限定理．

二十世纪初

Markov的兴趣转移到相依随机变量序列的研究,

并创立了以他命名的著名概率模型——马尔可夫链．经过世界各国几代数学家的相继努力,马尔可夫过程已成为内容十分丰富,理论上相当完整,应用非常广泛的一门数学分支.应用领域涉及计算机、通讯、自动控制、随机服务、可靠性、生物、经济、管理、气象、物理、化学等.马尔可夫链的定义马尔可夫链的概率分布齐次马尔可夫链的状态分类转移概率的极限与平稳分布本章内容作业:2,4,8,9,11,(2)(4),12,13,(1)(4),19.离散时间马尔可夫链的定义(6.1)式表示的马氏性指：在已知过程现在状态的条件下，过程将来处于那个状态的概率不依赖于过程过去经历的状态.也称之为无记忆性.马氏性的直观解释如果将时刻n看作现在，则时刻0，1，…，n-1就表示过去，而时刻n+1就表示将来，一般地，有以下定义k=1时，特别约定，当k＝０时，不难验证，转移概率矩阵是随机矩阵，即齐次马尔可夫链为方便，一般常将齐次马氏链的起始时刻取为零．即相应的一步转移概率矩阵分别记为

例6.1.1(随机游动)设一质点在直线上的整数格点上作随机游动，移动规则如下：ii+1i-1马尔可夫链举例一步转移概率的直观表示—状态转移图

(有限制随机游动)设质点在直线上的{0，1，···，a}各点上作随机游动，移动规则如下：ii+1i-101a-1a其一步转移概率矩阵为

例6.1.2群体增长

设某种生物群体的每个个体在其生存期内彼此独立的产生后代，假设每个个体都以概率pk产生k个后代，且有用Xn表示第n代生物群体的总数，则例6.1.3(天气变化)如果明天是否有雨仅与今天的天气有关，而与过去的天气无关.并设今天下雨、明天有雨的概率为a，今天无雨而明天有雨的概率为b，又假设有雨称为0状态天气，无雨称为1状态天气.Xn表示时刻n时的天气状态，则其一步转移概率矩阵为如果任意一天的天气与前两天的天气有关，即是以下状态空间上的齐次马尔可夫链.一步转移概率矩阵为如果Xn仍表示时刻n的天气状态，则例6.1.4(网页浏览)

因特网中所有的网页用以下集合表示另设网页上的超级链接数例6.1.5

设一个坛子中装有m个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反颜色的球.设经过n次摸换,坛中黑球数为Xn,则其一步转移概率矩阵为例6.1.6

设一个坛子中装有b个黑球和r个球，每次随机的从坛子中摸出一球再放回去，并加入c个同颜色的球.设Xn表示第n次摸放后坛中的黑球数,则其一步转移概率为例6.1.7切谱曼—柯尔莫哥洛夫方程马尔可夫链的概率分布初始分布绝对分布有限维分布本节主要内容马尔可夫链的概率分布Chapman-kolmogorov方程(C-K方程)定理6.2.1或矩阵形式证明系统在n时从状态i出发,经k+m步转移,于n+k+m时到达状态j,可以是系统在n时从状态i出发，先经k步转移，于n+k时到达某种中间状态l,再在n+k时从该中间状态l出发又经m步转移，于n+k+m时到达状态j，而中间状态l要取遍整个状态空间S.C-K方程的直观意义：若取m=1,则由C-K方程的矩阵形式:得结论：马尔可夫链的k步转移概率由其一步转移概率所完全确定.分量形式例6.2.1

设X={Xn，n≥0}是描述天气变化的齐次马氏链.状态空间为S={0，1}，其中0与1分别表示有雨和无雨天气.X的一步转移概率矩阵为对任意的状态i，j∈S，计算三步转移概率比较各个概率值，并思考如果转移步数增大，上述概率如何变化或有什么规律？初始分布马尔可夫链的概率分布称向量为马尔可夫链的初始分布向量.

定义6.2.1马氏链X={Xn，n≥0}的状态空间为S绝对分布称向量为马氏链X的绝对分布向量.

定义6.2.2马氏链X={Xn，n≥0}的状态空间为S定理6.2.3马尔可夫链X的绝对分布由其初始分布和一步转移概率完全确定.对于齐次马尔可夫链，上述结论可表示为有限维分布定理6.2.2马尔可夫链X的有限维分布由其初始分布和一步转移概率所完全确定.证明又因为马尔可夫链的k步转移概率由一步转移概率所完全确定.所以马尔可夫链的有限维分布由其初始分布和一步转移概率完全确定.为齐次马氏链，状态空间为S={0，1，2}.转移概率矩阵为初始分布试求：解例6.2.3社会学家将家庭的个体收入分为低、中、高三个等级，分别表示为1、2、3。研究者发现，个体收入等级在很大程度上取决于其父代收入的等级，

令Xn，表示一个家庭第n代个体的收入等级，则该家庭相继后代收入等级的变化可用齐次马氏链X={Xn，n≥0}描述，状态空间为S={1，2，3}.且有一步转移概率矩阵如果个体当前收入等级为3，试分析经过三代后个体收入等级转变为2的可能性，进一步分析经过n代后个体收入等级的概率分布，并具体计算n=10时，个体收入等级的概率分布。马尔可夫链状态的分类本节内容状态类型定义状态类型判断状态之间的关系状态空间的分解状态类型定义定义6.3.1利用量概率fii可以定义状态类型利用量可以进一步定义状态类型例6.3.1

设状态空间S={1,2,3,4}的马尔可夫链,它的一步转移概率矩阵为试分析马氏链的状态的常返与否2314解:马氏链的状态转移图为2314类似可以讨论状态2和4.例6.3.2

设状态空间S={1,2,3,4,5}的齐次马氏链,一步转移概率矩阵为马氏链的状态转移图为23145定义6.3.4证明引理6.3.1状态类型的判断定理6.3.2引理6.3.2定理6.3.3证明推论6.3.1定理6.3.4非周期态的判断则利用

hi有可以计算di例6.3.3证明定义6.3.5状态之间的关系状态的可达与互通满足以下性质上述性质的验证留作练习.定理6.3.5证明则从状态i(注意到是常返的)出发最终不能到达i的概率为:证明所以,i,j或者同为非常返态，或者同为常返态.下面考虑当i,j同为常返态时的情况:所以,i,j或者同为零常返态,或者同为正常返态.下面证明当i,j同为正常返态时,周期相同所以,i,j或者同为正常返非周期状态(遍历态),

或者同为正常返周期状态,且周期相同.例6.3.4

设马氏链的状态空间S={0,1,2,…},一步转移概率为试分析马氏链各状态的类型解:马氏链的状态转移图为120n状态空间的分解证明(1)用数学归纳法闭集C的性质下面讨论状态空间的分解证明定理6.3.8齐次马氏链的状态空间S可唯一地分解为有限或可列无限多个互不相交的状态子集的并.即其中D是所有非常返状态构成的状态子集.均是由常返态构成的不可约闭集.每个状态子集中的状态有着相同的状态类型:(即或者均为零常返,或者均为正常返非周期,或者均为正常返周期且周期相同.)定理6.3.9设X是状态有限的齐次马氏链，则(1)X的非常返状态集D不可能是闭集.(2)X不存在零常返状态.(3)若X是不可约的，则X所有的状态都是正常返的.

证明例6.3.5

设状态空间S={0,1,2}的马氏链,一步转移概率矩阵为分解状态空间，并指出状态类型120例6.3.6

设马氏链的状态空间为S={1,2,3,4},一步转移概率矩阵为试分析状态类型1234例6.3.7

试分析描述直线上随机游动质点的马氏链(见例6.1.1)的状态类型.证明思路:(1)分解式的存在性(2)转移规则的正确性(3)分解式的唯一性证明(1)分解式的存在性(2)转移规则的正确性(3)分解式的唯一性例6.3.8

设齐次马尔可夫链的状态空间S={1,2,3,4,5,6,7,8},其一步转移概率矩阵为12534678例6.3.9

设齐次马尔可夫链的状态空间S={1,2,3,4,5,6,},

其一步转移概率矩阵为试分解此马尔可夫链,并写出各状态类型及周期.123564例1（补）

设{Xn,n=0,1,2,…}是一齐次马尔可夫链,状态空间S={1,2,3,4,5},其一步转移概率矩阵为试分析状态类型12354例2(补)设齐次马尔可夫链的状态空间S={0,1,2,3,},其一步转移概率矩阵为试分析过程的周期性1203极限分布回忆：什么样的马氏链存在极限？回忆：不可约的遍历链回忆：如何计算极限分布？2平稳分布定理6.4.3

设是齐次马氏链的一个平稳分布，如果取为的初始分布，即(1)

则对任意的正整数n，都有(2)并且对任意的正整数n，m,以及定理说明：若马氏链存在平稳分布,则以平稳分布作为初始分布,就有以下结论：（1）马氏链的绝对分布是确定的,保持不变.（2）该马氏链是一个严平稳时间序列.齐次马尔可夫链是否存在平稳分布?思考：一个重要的问题:如果存在,是否唯一?如何计算?按照以下情况分别讨论不可约的遍历链不可约的正常返的马氏链一般的齐次马氏链且此时的极限分布就是平稳分布.平稳分布可通过求解下列方程组得到齐次马尔可夫链是不可约的遍历链例1

设状态空间为S={0,1,2,}的马尔可夫链,其一步转移概率矩阵为试分析它的极限分布，平稳分布是否存在？并计算解易知此链为不可约遍历链.故极限分布存在，平稳分布存在唯一，且平稳分布就是其极限分布。例2

设齐次马尔可夫链的状态空间S={0,1,2,3,4},其一步转移概率矩阵为分析平稳分布存在？并计算解易知是不可约链,且为遍历链.故其平稳分布存在且唯一.平稳分布为定理6.4.4设平稳分布通过求解方程组齐次马尔可夫链是不可约的正常返链因此对于一切j成立有定理6.4.5其中D是非常返状态集，C0是零常返状态集，是正常返状态的不可约闭集，一般齐次马尔可夫链