第1章离散时间的马尔可夫链.doc

《第1章离散时间的马尔可夫链.doc》由会员分享，可在线阅读，更多相关《第1章离散时间的马尔可夫链.doc（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.第1章 离散时间的马尔可夫链1 随机过程的基本概念 定义1 设是概率空间，是可测空间，是指标集. 若对任何，有，且，则称是上的取值于中的随机过程，在无混淆的情况下简称为随机过程，称为状态空间或相空间，称中的元素为状态，称为时间域. 对每个固定的，称为对应于的轨道或现实，对每个固定的，称为值随机元. 有时也记为 设，是中的一族单调增的子代数（代数流），即 ，且是代数； . 若，则称是适应的随机过程，或适应于的随机过程. 特别地，若令是由所生成的代数，则是适应的随机过程.当时，称为实值随机过程；当时，称为复值随机过程；当时，称为维随机过程；当是可列集（有限集）时，称为可列（有限）随机过程；当或时

2、，称为连续参数的随机过程；当或时，称为离散参数的随机过程（随机序列）；当或时，称为随机场.随机过程的四种类型：（1）指标集离散，状态空间离散的随机过程；（2）指标集离散，状态空间连续的随机过程；（3）指标集连续，状态空间离散的随机过程；（4）指标集连续，状态空间连续的随机过程. 然而，以上分类是表面的，更深刻的是按随机过程的概率结构而分类. 例如：马尔可夫（Markov）过程、平稳过程、独立增量过程、二阶矩过程、正态过程、泊松（Poisson）过程、生灭过程、分枝过程、更新过程、鞅等. 对于随机过程而言，可以这样设想，有一个作随机游动的质点，以表示在时刻质点的位置，于是描绘了质点所作的随机运动

3、的变化过程，一般把“”形象地说成“在时刻质点处于状态”. 定义2 设是概率空间上的、以为状态空间的随机过程，（或或直线上的任一区间）.如果，有 则称是可测的. 设是中的一族单调增的子代数. 如果 有则称关于循序可测. 命题1 设，是中的一族单调增的子代数. 如果关于循序可测，则是可测的. 定义3 设是随机过程，称为随机过程的一维分布函数；称为随机过程的二维分布函数；一般地，称为随机过程的维分布函数；而称为随机过程的有限维分布函数族. 随机过程的有限维分布函数族具有下列性质： 1. 对，及的任意排列，有 （对称性） 2. 对，有 （相容性） 注 若知道了随机过程的有限维分布函数族，便知道了这一随

4、机过程中任意有限个随机变量的联合分布，也就可以完全确定它们之间的相互关系. 可见，随机过程的有限维分布函数族能够完整地描述随机过程的统计特征. 但是在实际问题中，要知道随机过程的有限维分布函数族是不可能的，因此，人们想到了用随机过程的某些数字特征来刻画随机过程. 定义4 设是随机过程，称为的均值函数；称为的方差函数；称为的协方差函数；称为的相关函数. 注 若是复值随机过程，则方差函数的定义为协方差函数的定义为相关函数的定义为 性质 （1）； （2）； （3）若，则 .2 马尔可夫链的定义 在实际中有一类很广泛的随机过程，其特点是：过去只影响现在，而不影响将来. 这种随机过程称为马尔可夫过程.

5、状态离散的马尔可夫过程称为马尔可夫链，本章介绍时间离散的马尔可夫链（简称马尔可夫链）. 马尔可夫（Markov）过程的研究始于1906年，是随机过程的一个重要分支，它在近代物理、生物学、管理科学、信息处理、自动控制、金融保险等方面有着许多重要应用. 在本章中，无特别声明我们总是假设： 1. 参数集合；2. 状态空间或或其子集. 定义5 设是定义在概率空间上的随机过程，状态空间为. 若对于任意的及任意的整数 ，有则称为马尔可夫链，简称马氏链. 等式称为马氏性或无后效性，且假定式两端的条件概率都有意义（以下涉及到条件概率的式子都作类似的假定）. 定理1 随机过程是马尔可夫链的充要条件是对任意的及任

6、意的，有3 转移概率 对于马尔可夫链，描述它概率性质最重要的是它在时刻的一步转移概率. 马尔可夫链是描述某些特定的随机现象的数学模型，而产生这种特定的随机现象的具体模型一般称为系统，因此我们经常把事件说成是在时刻时系统处于状态，把说成已知在时刻时系统处于状态，而在时刻时系统转移到状态的概率等等. 定义6 设是状态空间为的马尔可夫链，称为系统在时刻时处于状态的条件下， 经步转移到状态的步转移概率，简称时刻的步转移概率. 显然，具有下列性质： （1）； （2）. 上述性质说明了，对于任意给定的及，是一个概率分布. 规定： （1）； （2） 若与无关，则称是时齐的或齐次的马尔可夫链. 此时，记；一步

7、转移概率记为. 对时齐的马尔可夫链，有 以下恒设马尔可夫链是时齐的，并简称为马尔可夫链. 性质 马尔可夫链的步转移概率具有下列性质（1）； （2）. 定理2（Chapman-Kolmogorov） 设是马尔可夫链的步转移概率，则，有 （C-K方程） 证明 定理3 马尔可夫链的一步转移概率可以确定所有的步转移概率. 证明 由C-K方程，显然. 记. 称为马尔可夫链的步转移矩阵，称为马尔可夫链的（一步）转移矩阵. 此时，C-K方程可表示为且. 定义7 设是马尔可夫链，对任意的，称，为绝对概率，特别地，称为初始概率. 显然，绝对概率和初始概率具有下列性质： 故对任意，是概率分布，通常称为绝对（概率）

8、分布；特别，称为初始（概率）分布. 记. 定理4 设是马尔可夫链， 则它的任意有限维概率分布完全由初始分布和一步转移概率决定. 证明 对任意的，任意的整数及任意的，有4 若干例子 定义8 设是取整数值的独立同分布的随机变量序列，令，则称为随机游动. 定理5 随机游动是时齐的马尔可夫链. （证明略） 例1（无限制的随机游动）若随机游动的状态空间为 ，且转移概率为其中. 求：步转移概率. 解 设在步转移中，向右移动步，向左移动步，则经步从到达，和应满足. 所以由于只能取正整数，故与必须是偶数. 又因在步转移中有步向右移动，故经步转移由到共有种方式，于是特别 例2（带有一个吸收壁的随机游动） 设是随

9、机游动，其状态空间为，若转移概率为则称为带有吸收壁的随机游动. 其转移矩阵为 例3（带有两个吸收壁的随机游动） 设是随机游动，其状态空间为，其转移概率为其转移矩阵为 例4（带有一个反射壁的随机游动） 设是随机游动，其状态空间为，其转移概率为其转移矩阵为 例5（带有两个反射壁的随机游动） 设是随机游动，其状态空间为，其转移概率为其转移矩阵为 例6（带有弹性壁的随机游动） 设是随机游动，其状态空间为，其转移概率为其转移矩阵为 例7 设是只有两个状态（）的随机游动，其转移矩阵为这里未必等于. 求，. 解 由C-K方程，得 同理可求，故设初始分布为，则 故，同理 . 例8 设是马尔可夫链，状态空间，转

10、移矩阵为初始分布为，求 （1）二步转移矩阵； （2）； （3）. 解 （1）. （2）由全概率公式、乘法公式、马氏性，得 （注：也可直接由定理4得到） （3）由加法公式、乘法公式、马氏性，得 例9 设随机游动的状态空间，其中和是吸收壁，初始状态为，转移概率为求质点被点吸收的概率. 解 设表示质点初始位置为而被点吸收的概率，则由于，故. （1）若，则（常数），故 因，故，从而，故. （2）若，则从而相加，得 ，所以故 5 状态的分类设是马氏链，为状态空间，为转移概率. 定义9 设，令称为首达的时刻（或的首达时），是随机变量，其可能值为 当为单点集时，记为. 令则表示系统从状态出发， 经步首次到达

11、状态的概率. 利用乘法公式、马氏性易知： 表示系统从出发， 经步首次返回的概率. 下面的定理是联系转移概率和首达概率之间关系的常用定理. 定理6 对任意状态 ，有 证明 令则表示系统从状态出发，经有限次到达状态的概率（也可以说成系统从状态出发，迟早要到达状态的概率）. 显然有特别，表示从状态出发，迟早要返回状态的概率. 定义10 若，则称是常返状态；若，则称是非常返状态或滑过状态. （显然，吸收状态是常返状态）对于常返状态，因，这表明，从状态出发必定要返回它自身. 记，则 例10 设马氏链的状态空间为，转移矩阵为 试判别状态的常返性. 解 故 记，则表示系统从状态出发，首达状态的平均时间；表示

12、系统从状态出发，首次返回的平均时间. 记表示系统经过的次数，是随机变量，表示系统在时刻经过状态的次数，即 则 记，则表示系统从状态出发，经过状态的平均次数；表示系统从状态出发，返回状态的平均次数. 定理7 设，则 证明 定理8 设 ，则 证明 而 故 推论 设 ，则 该推论说明了定义6的合理性，即：如果状态是常返的，则以概率1，系统无穷次返回状态；如果状态是非常返的，则以概率1，系统只有有限次返回状态，亦即系统无穷次返回状态的概率为0. 定理9 设 ，则 证明 （1）若，则，有，由定理6知，有，所以 . （2）若，则由定理8知，所以 . （3）若，则由定理8知，所以 推论 设 ，则 定义11

13、设 ，若，使，则称状态可达状态，记为；若，有，则称状态不可达状态，记为；若且，则称状态和状态相通（或互通），记为. 定理10 （1）若且，则；（2）若且，则. 证明 因且，所以，使得，由C-K方程，有，故. （2）由（1）易知（2）成立. 定理11 设 ，则（1）；（2）. 证明 只证明（1）. 设，则，使，而因此，中至少有一个大于，从而. 设，因，所以，使，故即 . 定理12 （1）； （2），这时必有； （3）若，则，且. 证明 由定理7及定理9的推论即知（1）和（2）；（3）略. 对于常返状态，即，由于，因此是一个概率分布，故易知 定义12 设状态是常返的，即. 若，则称是正常返的；若，

14、则称是零常返的. 记 . 定义13 （1）设，若，有，则称是闭集；（2）设，若，都有，则称是不可约的；（3）若是不可约的，则称马氏链是不可约的（即）. 定理13 设，则下列各条等价 （1）是闭集； （2）； （3）. 注 （1）若是闭集，则，有. （2）整个状态空间是闭集，是最大的闭集；吸收状态（即）是闭集，是最小的闭集. 定理14 都是闭集. 证明 设 若，则，故. 矛盾，从而，由上面的定理13，知是闭集. 同理可证也是闭集. 例11 设是马尔可夫链，状态空间为，转移矩阵为问状态空间中是否含有真的不可约的闭子集？是否是不可约马尔可夫链. 解 易知，状态3是吸收状态，故是闭集；均是闭集；其中均

15、是不可约的；因为含有真的闭子集，所以为非不可约马尔可夫链. 例12 设马尔可夫链的状态空间为，状态之间的转移概率如图所示. 由图可见：自状态1出发，再返回状态1的可能步数为 显然的最大公约数为2. 但，即自状态1出发经过2步不能返回状态1. 但我们仍把2定义为状态2的周期. 896572941 定义14 设马尔可夫链的状态空间为，步转移概率为，对于，若集合非空，则称该集合的最大公约数为状态的周期. 如果，称状态为周期的，如果，称状态为非周期的. 若是空集，则不对状态定义周期. 由定义知，如果状态有周期，则对一切，都有. 但这并不是说对任意的，都有. 如在例12中，状态1的周期，但. 然而有如下

16、结论. 定理15 设状态的周期为，则存在正整数，对一切，有. 证明 略（证明用到了初等数论的知识）. 定理16 设状态，如果集合非空，则 证明 记 ，由定理6有从而，于是有 . 如果，则. 如果，只需证明，为此只需证明是的公约数即可. 换言之，只需证明对于一切，都有. 实际上，由的定义知，当时，有. 于是，对，有现假设当 时，有. 注意到时，有. 则由定理6得 于是，由归纳法知，当时，有. 定理17 设状态常返且有周期，则 .（其中为状态的平均返回时间，当时，约定） 证明 见可数状态的马尔可夫过程，胡迪鹤，武汉大学出版社，1983，. 定义15 非周期的正常返状态称为遍历状态. 定理18 设是

17、常返状态，则 是零常返状态； 是遍历状态. 证明 设是零常返状态，则，由定理17，得 ，而当时，有，于是得. 反之，设，假设是正常返状态，则，于是由定理17，得，矛盾. 设，由知，不能是零常返状态，从而只能是正常返状态，由定理17，得，注意到，得，所以，是遍历状态. 反之，由定理17是显然的. 定理19 设状态，且，则 （1）与同为常返状态或同为非常返状态；如果同为常返状态，则它们同为正常返状态或同为零常返状态. （2）与有相同的周期. 证明 （1）由于，由可达的定义知存在和，使得由C-K方程，对任意的，总有，将上式两边从1到求和，得， 可见，与相互控制，所以它们同为无穷或同为有限. 由定理1

18、2知，与同为常返状态或同为非常返状态. 若与同为常返状态，在以上的不等式中取极限，令，得， 因此，与同为正或同为零，由定理18知，与同为正常返状态或同为零常返状态. （2）设状态的周期为，状态的周期为. 因为 ，所以对任一使的，必有，从而可除尽. 又因为，所以也可除尽. 因此，可除尽. 这说明. 同理可证. 故，即状态与有相同的周期. 注 状态的常返性与马尔可夫链的初始分布是无关的 定理20 状态空间可唯一地分解成有限个或可列无穷个互不相交的子集之和，即 ，且使得 （1）每个是常返状态组成的不可约闭集； （2）中的状态或全是正常返状态，或全是零常返状态，且有相同的周期； （3）是由全体非常返状

19、态组成，自中的状态不能到达中的状态. 定理21 周期为的不可约马尔可夫链，其状态空间可唯一地分解为个互不相交的子集之和，即，且使得自中任一状态出发，经一步转移必进入中，. （约定：） 证明 （1）任意取定一状态，令，因是不可约的，即中的状态是互通的，故. （2）若（），由定义知，必存在非负整数和使得，. 又由于，必存在正整数，使，于是由C-K方程，有， 所以，能除尽，又能除尽，从而能除尽故能除尽，注意到 ，故只能，这说明，当时，. （3）下面证明对任一，有. 事实上最后一个等式是因：，由定义有，而当时，由定义有，由C-K方程，有，故. （4）最后证明分解的唯一性，这只需证明不依赖于最初取定的状

20、态. 亦即只需证明：对取定的状态，如果，则对另取的状态，仍有（可以与不同）. 设对的分解为，对的分解为，又设，. 于是，当时，自出发，以概率1只能在 等这些步上转移到或，从而；当时，自出发，以概率1只能在等这些步上转移到或，从而. 定理22 设是周期为的不可约的马尔可夫链，则得一新的马尔可夫链，其一步转移矩阵为，原马尔可夫链按照定理21分解出的每个，是新马尔可夫链的不可约的闭集，且中的状态对新马尔可夫链是非周期的. （证明略） 例13 设不可约马尔可夫链的状态空间为，周期为，转移矩阵为对取定的状态1，易知故. 马尔可夫链的转移矩阵为6 步转移概率的渐近性质与平稳分布 对极限性质，我们讨论两个问

21、题. 一是是否存在；二是其极限是否与有关. 这就与马尔可夫链的所谓平稳分布有密切联系. 定理23 若是非常返状态或零常返状态，则对任意，有. 证明 因是非常返状态或零常返状态，所以（由定理12和定理18）. 由定理6，对正整数，有固定，令，得再令，因，所以. 推论1 如果马尔可夫链的状态空间是有限集，则中的状态不可能全是非常返状态，也不可能含有零常返状态，从而不可约的有限马尔可夫链的状态都是正常返状态. 证明 设. 如果所有状态都是非常返状态，则对任意，由定理23知，从而 （）. 矛盾. 如果中有零常返状态，设，若，由定理12，有，即中的状态是互通的，从而是不可约. 又由定理19知，中全是零常

22、返状态，从而由定理14知，是闭集，即是不可约的闭集. 故. 令，注意到是有限集，由定理23得（）. 矛盾. 于是，有限马尔可夫链的状态空间必含有正常返状态. 对于不可约的有限马尔可夫链，由于所有状态是互通的，故所有状态都是正常返状态. 推论2 若马尔可夫链的非常返状态构成的集合是有限集，则不是闭集. 证明 若是闭集，将产生矛盾. 推论3 若马尔可夫链的状态空间有一个零常返状态，则必有无限多个零常返状态. 证明 设有零常返状态，令，若是有限集，将产生矛盾. 定理23考虑的是非常返状态或零常返状态的渐近分布，但当是正常返状态时，不一定存在，即使存在也可能与有关. 因此，我们退而研究及的极限. 记.

23、 则表示系统从状态出发，经步首次到达状态的概率，显然 定理24 设是正常返状态，周期为，则及，有 证明 因为当时，. 所以于是，对，有固定，令，由定理17，得再令，得于是，得 推论 设周期为的、不可约的、正常返的马尔可夫链的状态空间为，则对一切，有其中为定理21中所给出. 特别，当时，对一切，有 证明 在定理24中，令，得其中. 如果与不在同一个中，则由定理21知，注意到，得，故. 如果与同属于某个，则当时，从而，故由定理12（3）知，. 定理25 对任意状态，有 证明 当为非常返状态或零常返状态时，由定理23知，故现设为正常返状态，周期为. 注意到：如果有数列满足. 则必有令. 由定理24，

24、有从而得 推论 设不可约的、常返的马尔可夫链的状态空间为，则对，有当时，约定. 证明 由定理19知，中的状态或全为正常返状态或全为零常返状态. 如果全为正常返状态，则（定理12），由定理25得如果全为零常返状态，则，由定理25得 注 由定理25知，当为正常返状态时，尽管不一定存在，但其平均值极限总存在. 特别，当马尔可夫链还是不可约时，与无关. 定义16 设是状态空间为的马尔可夫链，如果存在实数集合，满足 （1）； （2）； （3）.则称是平稳的马尔可夫链，称为马尔可夫链的平稳分布. 对于平稳分布，有一般，有 . 若初始分布是马尔可夫链的平稳分布，则 即对任何，绝对概率等于初始概率. 由此可见

25、，当我们能判定马尔可夫链的初始分布是一平稳分布时，则该马尔可夫链在任何时刻的绝对分布都与初始分布相同. 事实上，平稳分布就是不因转移步数变化而改变的分布. 马尔可夫链处于状态的概率与时间推移无关，即具有平稳性. 与平稳分布相关的是所谓极限分布的概念. 对于不可约的马尔可夫链，若状态是非周期的，则以后称为极限分布. 定理26 非周期不可约的马尔可夫链是正常返的充分必要条件是它存在平稳分布，且此平稳分布就是极限分布. 证明 “”设存在平稳分布，于是有由于和，故可以交换极限与求和顺序，两边令得因为，故至少存在一个，即，从而 ，故是正常返的，从而马尔可夫链是正常返的，且所有的 . “”设马尔可夫链是正

26、常返的，于是由C-K方程，对任意正整数（若是有限集，则不必如此），有两边令，得再令，得 （）下面进一步证明，只能等式成立. 由先令，再令，得将（）式对求和，并假定对某个，（）式为严格大于，则于是导致自相矛盾的结果故（）式对一切都只能成立等式再令，得由此可知故是平稳分布. 推论1 非周期的、不可约的、正常返的马尔可夫链的平稳分布是唯一的，就是极限分布. 推论2 若不可约的马尔可夫链的所有状态是非常返或零常返的，则不存在平稳分布. 证明 用反正法. 设是马尔可夫链的平稳分布，则由定理23，有故 ，从而，与平稳分布矛盾. 例14 设马尔可夫链的转移矩阵为求马尔可夫链的平稳分布及各状态的平均返回时间. 解 因马尔可夫链是不可约的、非周期的，且状态有限，所以该马尔可夫链存在平稳分布，满足，即解上述方程组，得平稳分布为由定理26，得各状态的平均返回时间分别为7 可逆性 设马尔可夫链的初始分布为，状态空间为可列集，步转移概率为. 定义17 称马尔可夫链可逆，如果：对任意的，及任意的，均有 定理27 马尔可夫链可逆的充分必要条件是：对任意的，有 证明 “”设马尔可夫链可逆，由定义，对任意的及任意的，有，从而即 ，当时，有. “”设对任意的，有. 则对任意的，及任意的，由定理4，有 由定义知，马尔可夫链是可逆的.