三章Markov过程 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望第一节 Markov链的定义和例子n n定义定义3.1 如果对任何一列状态 及对任何 ，随机过程 满足Markov性质： 则称 为离散时间Markov链。n n定义定义3.2 设 为一离散时间Markov链。给定 在状态 时 处于 状态的条件概率 称为Markov链的一步转移概率，记作 。当这一概率与n无关时称该Markov链有平稳转移概率，并记之为 ，对应Markov链称为时齐Markov链。 记n步转移概率为 ，以 为元 的矩阵 记作 ，称为Markov链的n步转移概率矩阵。n n定理定理定理定理3.1 3.1 MarkovMarkov链的链的n n步转移概率矩阵满足步转移概率矩阵满足 ，在上式中我们定在上式中我们定 。 n n例例例例3.13.1（一维随机游动）设一质点在直线上的点集（一维随机游动）设一质点在直线上的点集 上作随机游动，每秒钟发生一次游动，游动规则是：如果上作随机游动，每秒钟发生一次游动，游动规则是：如果质点处于质点处于2 2，3 3，4 4点处，则在下一秒钟，质点均以的概率点处，则在下一秒钟，质点均以的概率向左，右移动一单位或停留在原处；如果质点处于向左，右移动一单位或停留在原处；如果质点处于1 1处，处，则在下一秒钟以概率则在下一秒钟以概率1 1移动到移动到2 2处；如果质点处于处；如果质点处于5 5处，则处，则在下一秒钟以概率在下一秒钟以概率1 1移动到移动到4 4处因为质点不可越出处因为质点不可越出1 1，5 5两两点，故称为不可越壁的随机游动用点，故称为不可越壁的随机游动用 表示在时刻表示在时刻n n质点质点的位置，则的位置，则 是是个齐次马氏链个齐次马氏链 (1) (1) 试写出它的一步转移矩阵和二步转移矩阵；试写出它的一步转移矩阵和二步转移矩阵； (2) (2) 若初始分布为若初始分布为 ，试求在时的绝对分布，试求在时的绝对分布 解：(1)一步转移矩阵二步转移矩阵（2）例例例例3.23.2 设建筑物受到地震的损害程度为齐次马氏链，按损害设建筑物受到地震的损害程度为齐次马氏链，按损害程度分为程度分为5 5种状态：无损害称为处于状态种状态：无损害称为处于状态1 1，轻损害称为处，轻损害称为处于状态于状态2 2，中等损害称为处于状态，中等损害称为处于状态3 3，严重损害称公处于状，严重损害称公处于状态态4 4，全部倒塌称为处于状态，全部倒塌称为处于状态5 5设一步转移矩阵为设一步转移矩阵为 初始分布为初始分布为 试求接连发生两次地震时，该建筑物的各状态的概率分布，试求接连发生两次地震时，该建筑物的各状态的概率分布， 指出接连发生两次地震后，该建筑物完全倒塌的概率为多少指出接连发生两次地震后，该建筑物完全倒塌的概率为多少? ? 严重损害概率为多少严重损害概率为多少? ?中等以上损害概率为多少中等以上损害概率为多少? ? 解：时的绝对分布为解：时的绝对分布为 从而知接连发生两次地震后，建筑物完全倒塌的概率为从而知接连发生两次地震后，建筑物完全倒塌的概率为 严重损害的概率为严重损害的概率为 中等以上损害的概率为：中等以上损害的概率为：例例例例3.33.3 (0 (0l l传输系统传输系统) )一个通信传输系统，通过一个通信传输系统，通过n n个阶段传输个阶段传输数字数字0 0和和1 1，设在每一个阶段被下一个阶段接受的数字仍与，设在每一个阶段被下一个阶段接受的数字仍与这这阶段相同的转移概率为阶段相同的转移概率为 ，且记第，且记第n n阶段被接受到的数阶段被接受到的数为为 则则 是一个齐次马氏链，其一步转移概率矩阵为是一个齐次马氏链，其一步转移概率矩阵为(1)(1)设设 求系统经过二级传输后的传真率和四级传输后的误码率求系统经过二级传输后的传真率和四级传输后的误码率( (输入输入和输出相同的概率为传真率，相反的情况称误码率和输出相同的概率为传真率，相反的情况称误码率) ) (2)(2)设设 又设初始分布为又设初始分布为 ，若己知系统经过，若己知系统经过n n级传输后的输级传输后的输出为出为l l，问原发信号也为，问原发信号也为l l的概率为多少？的概率为多少？解解 (1)(1)由由 可知系统二级传输后的传真率为：可知系统二级传输后的传真率为： 系统四级传输后的误码率为：系统四级传输后的误码率为： （2 2）根据贝叶斯公式，当已知系统经过）根据贝叶斯公式，当已知系统经过n n级传输后输出为级传输后输出为1 1，原发信，原发信号也为号也为1 1的概率为：的概率为：第二节 Markov链的状态分类n n3.2.1 互达性和周期性定义定义定义定义3.33.3 可达与互达如果对某一可达与互达如果对某一 ，有，有 则称状态则称状态是从状态是从状态 可达的记作可达的记作 ，它表示从状态，它表示从状态 经过有限步的经过有限步的转移可以到达状态转移可以到达状态 。两个互相可达的状态。两个互相可达的状态 和和 则称为是则称为是互达的记作互达的记作 . .命题命题命题命题3.1 3.1 互达性是等价关系互达性是等价关系1) 1) 自反性，自反性，2)2)若若 ，则，则 ，对称性，对称性，3)3)若若 ，则，则 ，则，则 ，传递性。，传递性。 两个状态如果是互达的就称他们是处在同一类中两个状态如果是互达的就称他们是处在同一类中MarkovMarkov链的所有状态就由链的所有状态就由互达这一等价关系而分割成不同的等价类由命题互达这一等价关系而分割成不同的等价类由命题3.13.1我们立刻知道两个类要我们立刻知道两个类要么互不相交，要么完全重合如果在互达性这一等价关系下么互不相交，要么完全重合如果在互达性这一等价关系下MarkovMarkov链的所有链的所有状态都居于同一类那么就称这个状态都居于同一类那么就称这个MarkovMarkov链是不可约的换言之，不可约过程链是不可约的换言之，不可约过程的各个状态都是互达的的各个状态都是互达的n n例例3.4 3.4 若若MarkovMarkov链有转移概率矩阵链有转移概率矩阵则显见则显见 和和 是状态在互达意义下的是状态在互达意义下的两个等价类。这个链是可约的。可以把两个等价类。这个链是可约的。可以把它分成两个链来研究。它分成两个链来研究。定义定义定义定义3.43.4 状态状态 的周期为的周期为MarkovMarkov链的一个状态，使链的一个状态，使 的所有的所有 的最大公约数称作是状态的最大公约数称作是状态 的周期记作的周期记作 如果对所有如果对所有 ，都有，都有 则约定周期为则约定周期为 ； 的状态的状态 称为是非周期的称为是非周期的由定义立即可知如由定义立即可知如 不能被周期不能被周期 整除则必有整除则必有 例例3.6 Markov3.6 Markov链有状态链有状态o o，1 1，2 2，3 3和转移概率阵和转移概率阵 试求状态试求状态0 0的周期。的周期。解：不难直接算出解：不难直接算出 而而。而。而 的最大公约数为的最大公约数为2 2。所以。所以命题命题命题命题3.2 3.2 如果如果 则则命题命题命题命题3.3 3.3 如果状态如果状态 有周期有周期 ，则存在整数，则存在整数 使得对所有使得对所有的恒有的恒有 推论推论推论推论3.1 3.1 如果如果 ，则存在正整数，则存在正整数 使得对使得对 恒有恒有 。命题命题命题命题3.43.4 令令 为不可约、非周期、有限状态为不可约、非周期、有限状态MarkovMarkov链的转移链的转移概率矩阵则必存在概率矩阵则必存在 使得当使得当 时时n n步转移概率阵步转移概率阵 的所的所有元素都非零有元素都非零n n3.2.2 3.2.2 常返与瞬过常返与瞬过引入一个重要的概率引入一个重要的概率 ，它表示从出发在，它表示从出发在n n步转移时首次到步转移时首次到达达 的概率。即：的概率。即：记记 ，它是从，它是从 出发最终转入状态出发最终转入状态 的概率。的概率。n n定义定义定义定义3.43.4 如果如果 我们称状态我们称状态 是常返的，一个非常返状是常返的，一个非常返状态就称为是瞬过的态就称为是瞬过的n n定理定理定理定理3.2 3.2 状态状态 常返的充分必要条件是常返的充分必要条件是 当然与此等价地有，状态当然与此等价地有，状态 是瞬过的当且仅当是瞬过的当且仅当 推论推论推论推论3.2 3.2 如果如果 是常返的，且是常返的，且 ，则，则 也是常返的也是常返的n n定义定义定义定义3.5 3.5 一个常返状态一个常返状态 当且仅当当且仅当 时称为是零常返的时称为是零常返的而当且仅当而当且仅当 时称为正常返的时称为正常返的n n例例例例3.7 3.7 设马氏链的状态空间为设马氏链的状态空间为 ，其一步转移概率矩，其一步转移概率矩阵为阵为 试讨论该马氏链各状态的常返性。试讨论该马氏链各状态的常返性。解：步转移概率矩阵为：解：步转移概率矩阵为：由由得：得：因此状态因此状态1 1，2 2，4 4都是常返态，状态都是常返态，状态3 3是非常返态。当是非常返态。当 时，时， 都不趋于都不趋于0 0。所以状态。所以状态1 1，2 2，4 4都是正常返态。都是正常返态。第三节第三节 MarkovMarkov链的极限定理与平稳分布链的极限定理与平稳分布n n定理定理定理定理3.33.3 Markov Markov链的基本极限定理链的基本极限定理a)a)若状态是瞬过的或者是零常返的，则若状态是瞬过的或者是零常返的，则b)b)若状态是周期为的常返状态，则若状态是周期为的常返状态，则 c)c)当状态是非周期的正常返状态（也称为遍历的），则当状态是非周期的正常返状态（也称为遍历的），则 推论推论推论推论3.33.3 如果状态如果状态 是遍历的则对所有是遍历的则对所有 有有：定义定义定义定义3.6 3.6 MarkovMarkov链有转移概率阵链有转移概率阵 。一个概率分布。一个概率分布 如如果满足果满足 则称作是这一则称作是这一MarkovMarkov链的平稳分布。链的平稳分布。定理定理定理定理3.4 3.4 若一个不可约若一个不可约MarkovMarkov链中的所有状态都是遍历的，则对所链中的所有状态都是遍历的，则对所有有 ，极限，极限 存在且存在且 为平稳分布也即为平稳分布也即 n n反之，若反之，若个不可约个不可约MarkovMarkov链存在一个平稳分布，即满足链存在一个平稳分布，即满足(3(31)1)式，式，且这个且这个MarkovMarkov链的所有状态都是遍历的则该平稳分布就是这一链的所有状态都是遍历的则该平稳分布就是这一MarkovMarkov链的极限分布，即对任何有链的极限分布，即对任何有例例例例3.8 3.8 设齐次马氏链设齐次马氏链 的状态空间的状态空间 ，一步转移概率矩为，一步转移概率矩为试证此链具有遍历性，并求其极限分布试证此链具有遍历性，并求其极限分布。解解： n n所以当所以当 时，无零元素，由定理时，无零元素，由定理1 1知，此链具有遍历性。设其极限分布为知，此链具有遍历性。设其极限分布为 则则 ，即，即 （3.23.2） 以及：以及： （3.33.3） n n由（由（3.23.2）式可得）式可得：n n n n代入（代入（3.33.3）式得）式得：n n容易验证，当容易验证，当 ，极限分布为，极限分布为n n当当 ，极限分布为，极限分布为n n当当 ，极限分布为，极限分布为 第四节第四节 分支过程分支过程n n定理定理定理定理3.5 3.5 对分支过程对分支过程 ，若，若 ， ，则有，则有 （a a）群体消亡概率）群体消亡概率 是方程是方程 的最小正解，其中的最小正解，其中 ， 是是 与与 的概率分布。的概率分布。（b b） 当且仅当当且仅当 ，其中，其中 第五节第五节 连续时间连续时间MarkovMarkov链链n n3.5.1 3.5.1 连续时间连续时间MarkovMarkov链链 定义定义定义定义3.83.8若对所有若对所有 和任何非负整数和任何非负整数 ， ，随机过程，随机过程 满足满足 则称为是连续时间则称为是连续时间MarkovMarkov链链命题命题命题命题3.53.5 连续时间连续时间MarkovMarkov链的转移概率链的转移概率 和和 完全确定了过程的所有完全确定了过程的所有联合分布联合分布定理定理定理定理3.63.6 函数函数 作为无瞬即转移的作为无瞬即转移的MarkovMarkov过程转移概率函数的充分必要过程转移概率函数的充分必要条件是它满足下面条件：条件是它满足下面条件：（a a）（b b）（c c）n n3.5.2 3.5.2 纯生过程纯生过程当当 满足以下满足以下4 4条假定时就称为是一个纯生过程：条假定时就称为是一个纯生过程：1 1）2 2）3 3）4 4） 第六节第六节 生灭过程生灭过程n n3.6.1 生灭过程n n假定假定 是状态是状态 上的上的MarkovMarkov链，其转移概率链，其转移概率 是平是平稳的，即对所有稳的，即对所有 有有 ，此外还假，此外还假定：定：（1 1）（2 2）（3 3）（4 4）（5 5）满足上述假设条件的随机过程称为生灭过程。其中满足上述假设条件的随机过程称为生灭过程。其中 和和 分别称为新生分别称为新生率和死亡率。率和死亡率。n n3.6.2 Kolmogorov3.6.2 Kolmogorov向后向前微分方程向后向前微分方程n n定理定理定理定理3.7 3.7 对生灭过程对生灭过程 的转移概率的转移概率 有有KolmogorovKolmogorov向后向后微分方程微分方程 和和KolmogorovKolmogorov向前微分方程向前微分方程例例例例3.93.9 带移民带移民 的线性增长和线性死亡模型取的线性增长和线性死亡模型取 其中其中 这在人口问题中是常见的我们最感兴趣这在人口问题中是常见的我们最感兴趣的是在时刻的期望人口数的是在时刻的期望人口数 。利用向前微分方程。利用向前微分方程将将 代入即有：代入即有：n n记记 ，于是，于是 应满足方程应满足方程设初始条件为设初始条件为 则则 。当。当 时容易求出时容易求出 ，当，当 时时当当 时，若时，若 而当而当 时的极限为时的极限为 。经过长时期后人口的平均数将趋于统计平衡。经过长时期后人口的平均数将趋于统计平衡。定义定义定义定义3.73.7 随机过程随机过程 ，若对任何，若对任何 ，其，其条件概率分布函数满足条件概率分布函数满足则称为是一个则称为是一个MarkovMarkov过程。过程。 谢谢观看！