概率统计讲课稿第十三章马尔可夫链第一节第二节(上)

第十三章 马尔可夫链马尔可夫过程是一类特殊的随机过程, 马尔可夫链是离散状态的马尔可夫过程,最初是由俄国数学家马尔可夫1896年提出和研究的.应用十分广泛,其应用领域涉及计算机,通信,自动控制,随机服务,可靠性,生物学,经济,管理,教育,气象,物理,化学等等.第一节 马尔可夫链的定义一．定义定义 1 设随机过程}),({T t t X ∈的状态空间S 是有限集或可列集,对任意正整数n ,对于T 内任意1+n 个参数121+<<⋅⋅⋅<<n n t t t t 和S 内任意1+n 个状态121,,,,+⋅⋅⋅n n j j j j ,如果条件概率})(,,)(,)(|)({221111n n n n j t X j t X j t X j t X P =⋅⋅⋅===++})(|)({11n n n n j t X j t X P ===++,(13.1) 恒成立,则称此过程为马尔可夫链. 式(13.1)称为马尔可夫性,或称无后效性.马氏性的直观含义可以解释如下: 将n t 看作为现在时刻,那末,121,,,-⋅⋅⋅n t t t 就是过去时刻,而1+n t 则是将来时刻.于是,(13.1)式是说,当已知系统现时情况的条件下,系统将来的发展变化与系统的过去无关.我们称之为无后效性.许多实际问题都具有这种无后效性.例如 生物基因遗传从这一代到下一代的转移中仅依赖于这一代而与以往各代无关.再如,每当评估一个复杂的计算机系统的性能时,就要充分利用系统在各个时刻的状态演变所具有的通常概率特性:即系统下一个将到达的状态,仅依赖于目前所处的状态,而与以往处过的状态无关.此外,诸如某公司的经营状况等等也常常具有或近似具有无后效性.二． 马尔可夫链的分类状态空间S 是离散的(有限集或可列集),参数集T 可为离散或连续的两类.三．离散参数马尔可夫链（1）转移概率定义2 在离散参数马尔可夫链},,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 中,条件概率)(})(|)({1m ij m m t p i t X j t X P ===+称为)(t X 在时刻(参数)m t 由状态i 一步转移到状态j 的一步转移概率, 简称转移概率.条件概率)(})(|)({)(m n ij m n m t p i t X j t X P ===+称为)(t X 在时刻(参数)m t 由状态i 经n 步转移到状态j 的n 步转移概率.(2)转移概率的性质:对于状态空间S 内的任意两个状态i 和j ,恒有(1) 0)()(≥m n ij t p ;(2)1)()(=∑∈m Sj n ij t p ,⋅⋅⋅=,2,1n ()()(m Sj n ij t p ∑∈ })(|)({i t X j t X P m n m Sj ===+∈∑ })({})(,)({i t X P i t X j tX P m S j m n m ====∑∈+ })({}})(}){)({({i t X P i t X j t X P m S j m n m ====∑∈+1})({})({====i t X P i t X P m m )四.离散参数齐次马尔可夫链定义3 在离散参数马尔可夫链},,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 中,如果一步转移概率)(m ij t p 不依赖于参数m t ,即对任意两个不等的参数m t 和k t ,k m ≠,有)(})(|)({1m ij m m t p i t X j t X P ===+ij k ij k k p t p i t X j t X P =====+)(})(|)({1则称此马尔可夫链具有齐次性或时齐性,称)(t X 为离散参数齐次马尔可夫链.例1 Bernoulli 序列是离散参数齐次马尔可夫链.验证 在Bernoulli 序列},3,2,1,{⋅⋅⋅=n X n 中, 对任意正整数 n , 121+<<⋅⋅⋅<<n n t t t t ,121,,,,+⋅⋅⋅n n t t t t X X X X 相互独立, 故对 ,1,0=k j )1,,2,1(+⋅⋅⋅=n k ,有},,,|{211211n t t t n t j X j X j X j X P n n =⋅⋅⋅===++}{11+==+n t j X P n}|{11n t n t j X j X P n n ===++即满足马尔可夫性,且}|{11n t n t j X j X P n n ==++⎩⎨⎧=-====++++0,11,}{1111n n n t j p j p j X P n 当当 , 不依赖于参数n t ,满足齐次性.故Bernoulli 序列是离散参数齐次马尔可夫链.例2 爱伦菲斯特(Ehrenfest)模型 一容器中有a 2个粒子在作随机运动.设想有一实际不存在的界面把容器分为左右容积相等的两部分.当右边粒子多于左边时,粒子向左边运动的概率要大一些,大出部分与两边粒子的差数成正比;反之,当右边粒子少于左边时,粒子向右边运动的概率要大一些.以nX 表示n 次变化后,右边粒子数与均分数a 之差,则状态空间},1,,2,1,0,1,,1,{a a a a S -⋅⋅⋅-⋅⋅⋅+--=,转移概率 ⎪⎪⎪⎩⎪⎪⎪⎨⎧==±≠∈-=+=+---+-1,),1(21),1(211,1,1,1,a a a a j j j j p p a j S j a j p a j p则 },3,2,1,{⋅⋅⋅=n X n 是齐次马尔可夫链.第二节 参数离散的齐次马尔可夫链对于离散参数齐次马尔可夫链,本节讨论以下四个问题.一. 转移概率矩阵设 },,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 是齐次马尔可夫链, 由于状态空间S 是离散的(有限集或可列集)，不妨设其状态空间 },,,2,1,0{⋅⋅⋅⋅⋅⋅=n S .则对S 内的任意两个状态i 和j ,由转移概率 ij p 排序一个矩阵⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅=ij i i j j p p p p p p p p p P 101111000100 称为(一步)转移概率矩阵 .})(|)({1i t X j t X P p m m ij ===+转移概率矩阵的性质：(1) 0≥ij p ,即元素均非负;(2) 1=∑∈S j ij p ,即每行和为1.具有以上两个特点的方阵称为随机矩阵.转移概率矩阵就是一个随机矩阵.例1 Bernoulli 序列的状态空间}1,0{=S ,转移概率矩阵⎝⎛=⎪⎪⎭⎫ ⎝⎛=q q p p p p P 11100100 ⎪⎪⎭⎫p p , })(|)({1i t X j t X P p m m ij ===+⎩⎨⎧=====+1,0,})({1j p j q j t X P m .例1 一维随机游动一个质点在直线上的五个位置:0,1,2,3,4之上随机游动.当它处在位置1或2或3时,以31的概率向左移动一步而以32的概率向右移动一步;当它到达位置0时,以概率1返回位置1;当它到达位置4时以概率1停留在该位置上(称位置0为反射壁,称位置4为吸收壁).以j t X n =)(表示时刻n t 质点处于位置j ,4,3,2,1,0=j ,则},,,),({210⋅⋅⋅=t t t t t X 是齐次马尔可夫链.其状态空间}4,3,2,1,0{=S ,状态0是反射状态,状态4是吸收状态.其转移概率矩阵⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛==1000032031000320310003203100010)(ij p P})(|)({1i t X j t X P p m m ij ===+分别以4,3,2,1,0,0==j i ； 4,3,2,1,0,1==j i ；4,3,2,1,0,2==j i ；4,3,2,1,0,3==j i ；4,3,2,1,0,4==j i按题设条件求出转移概率 })(|)({1i t X j t X P p m m ij ===+ 画出状态转移示意图如图例3（成功流）设在一串贝努里试验中,每次试验成功的概率为p ,令⎩⎨⎧≤≤=n k k n k n X n 1,,,0次成功次试验接连第第次试验失败第则},3,2,1,{⋅⋅⋅=n X n 是齐次马尔可夫链.其状态空间},,,2,1,0{⋅⋅⋅⋅⋅⋅=k S ,其转移概率pq X P i X X P n n n -======++1}0{}|0{11,p n P i X i X P n n =+==+=+}1{}|1{1次试验时成功第,,0,,020100===p p p q p ，⎪⎪⎩⎪⎪⎨⎧=≤<+=+≥====+0,0,01,2,0}|{1j q i j i j p i j i X j X P p n n ij , （ ,3,2,1=i ）于是转移概率矩阵⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅=ij i i j j p p p p p p p p p P 101111000100⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=p q p q p q p q 0000000000二． 切普曼-柯尔莫哥洛夫方程定理一 设 },,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X是马尔可夫链,则有)()()()()()(n m l kj km n ik m l n ij t p t p t p ++∑=, (13.6)称为切普曼-柯尔莫哥洛夫方程.证 由条件概率定义计算公式,利用全概率公式和马氏条件,得})(|)({)()(i t X j t X P t p m l n m m l n ij ===+++})({})(,)({i t X P j t X i t X P m l n m m ====++ })({}})(,)(}){)({({i t X P j t X i t X k t X P m Sk l n m m n m =====∑∈+++})({})(,)(,)({i t X P j t X k t X i tX P m Sk l n m n m m=====∑∈+++ })({})(,)({})(,)({})(,)(,)({i t X P k t X i t X P k t X i t X P j t X k t X i t X P m n m m kn m m l n m n m m ===⋅======+++++∑})(|)({})(,)(|)({i t X k t X P k t X i t X j t X P m n m n m m kl n m ==⋅====++++∑})(|)({})(|)({i t X k t X P k t X j t X P m n m n m kl n m ==⋅===++++∑)()()()(n m l kj km n ik t p t p +∑= 证毕.如果马尔可夫链具有齐次性,那么切普曼-柯尔莫哥洛夫方程化为)()()(l kjkn ik l n ij p p p ∑=+ ,(13.7)当1,1==l n 时,得到kj kik ij p p p ∑=)2(,进一步改写为矩阵形式 2)2(P P=其中)()2()2(ijp P =是两步转移概率矩阵,P 是一步转移概率矩阵.用数学归纳法可得 nn P P =)(,⋅⋅⋅=,4,3,2n (13.8) 式(13.8)表明:n 步转移概率矩阵)()()(n ij n p P =等于一步转移概率矩阵P 的n 次幂.因此也常把n P 作为n 步转移概率矩阵的符号.例2 在本节例2中,求)2(00p 和)2(31p.解 由kj kik ij p p p ∑=)2(,得3131140)2(00=⨯==∑=k k k p p p,913131413)2(31=⨯==∑=k k k p p p.或用2)2()2()(P p Pij==.例3 传输数字0和1的通讯系统,每个数字的传输需经过若干步骤,设每步传输正确的概率为109,传输错误的概率为101,(1)问:数字1经三步传输出1的概率是多少? (2)若某步传输出数字1,那么又接连两步都传输出1的概率是多少?解 以n X 表示第n 步传输出的数字,则},2,1,0,{⋅⋅⋅=n X n 是一齐次马尔可夫链,0X 是初始状态,状态空间}1,0{=S ,一步转移概率矩阵⎝⎛=101109P ⎪⎪⎪⎪⎭⎫109101 (1) 2)2(P P =⎝⎛=101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109 ⎪⎪⎪⎪⎭⎫109101= ⎝⎛1001810082⎪⎪⎪⎪⎭⎫10082100183)3(P P =⎝⎛=101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101= ⎝⎛1001810082⎪⎪⎪⎪⎭⎫1008210018 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101=⎝⎛10002441000756 ⎪⎪⎪⎪⎭⎫10007561000244,756.01000756)3(11==p ; (2) }1|1,1{21===++n n n X X X P}1|1{1===+n n X X P }1,1|1{12===⋅++n n n X X X P}1|1{1===+n n X X P }1|1{12==⋅++n n X X P81.0)109(21111==⋅=p p .。

马尔可夫链模型（Markov Chain Model）目录[隐藏]1 马尔可夫链模型概述2 马尔可夫链模型的性质3 离散状态空间中的马尔可夫链模型4 马尔可夫链模型的应用o 4.1 科学中的应用o 4.2 人力资源中的应用5 马尔可夫模型案例分析[1]o 5.1 马尔可夫模型的建立o 5.2 马尔可夫模型的应用6 参考文献[编辑]马尔可夫链模型概述马尔可夫链因安德烈·马尔可夫（Andrey Markov，1856－1922）得名，是数学中具有马尔可夫性质的离散时间随机过程。

该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。

时间和状态都是离散的马尔可夫过程称为马尔可夫链, 简记为。

马尔可夫链是随机变量的一个数列。

这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而Xn的值则是在时间n的状态。

如果Xn + 1对于过去状态的条件概率分布仅是Xn的一个函数，则这里x为过程中的某个状态。

上面这个恒等式可以被看作是马尔可夫性质。

马尔可夫在1906年首先做出了这类过程。

而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。

马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。

马尔可夫链是满足下面两个假设的一种随机过程：1、t+l时刻系统状态的概率分布只与t时刻的状态有关，与t时刻以前的状态无关；2、从t时刻到t+l时刻的状态转移与t的值无关。

一个马尔可夫链模型可表示为=(S，P，Q)，其中各元的含义如下：1）S是系统所有可能的状态所组成的非空的状态集，有时也称之为系统的状态空间，它可以是有限的、可列的集合或任意非空集。

本文中假定S是可数集(即有限或可列)。

用小写字母i,j(或S i,S j)等来表示状态。

2）是系统的状态转移概率矩阵，其中P ij表示系统在时刻t处于状态i，在下一时刻t+l处于状态i的概率，N是系统所有可能的状态的个数。

马尔可夫链▏小白都能看懂的马尔可夫链详解1.什么是马尔可夫链在机器学习算法中，马尔可夫链(Markov chain)是个很重要的概念。

马尔可夫链（Markov chain），又称离散时间马尔可夫链（discrete-time Markov chain），因俄国数学家安德烈·马尔可夫（俄语：Андрей Андреевич Марков）得名，为状态空间中经过从一个状态到另一个状态的转换的随机过程。

该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。

这种特定类型的“无记忆性”称作马尔可夫性质。

马尔科夫链作为实际过程的统计模型具有许多应用。

在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状态，也可以保持当前状态。

状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率。

随机漫步就是马尔可夫链的例子。

随机漫步中每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概率都是相同的（无论之前漫步路径是如何的）。

2.一个经典的马尔科夫链实例用一句话来概括马尔科夫链的话，那就是某一时刻状态转移的概率只依赖于它的前一个状态。

举个简单的例子，假如每天的天气是一个状态的话，那个今天是不是晴天只依赖于昨天的天气，而和前天的天气没有任何关系。

这么说可能有些不严谨，但是这样做可以大大简化模型的复杂度，因此马尔科夫链在很多时间序列模型中得到广泛的应用，比如循环神经网络RNN，隐式马尔科夫模型HMM等。

假设状态序列为由马尔科夫链定义可知，时刻Xt+1 的状态只与Xt 有关，用数学公式来描述就是：既然某一时刻状态转移的概率只依赖前一个状态，那么只要求出系统中任意两个状态之间的转移概率，这个马尔科夫链的模型就定了。

看一个具体的例子。

这个马尔科夫链是表示股市模型的，共有三种状态：牛市（Bull market）, 熊市（Bear market）和横盘（Stagnant market）。

马尔可夫链的概念及转移概率第四章4.1 马尔可夫链的的概念及转移概率一、知识回顾二、马尔可夫链的的定义三、转移概率四、马尔可夫链的一些简单例子五、总结一、知识回顾1. 条件概率定义：设A，B为两个事件，且，称为事件A发生条件下B事件发生的条件概率。

将条件概率公式移项即得到所谓的乘法公式：2.全概率公式设试验E的样本空间为S，A为E的事件，若为S的一个完备事件组，既满足条件：1)两两互不相容，即2).，且有，则此式称为全概率公式。

3.矩阵乘法矩阵乘法的定义，如果那么矩阵C叫做矩阵A和B的乘积，记作4.马尔可夫过程的分类马尔可夫过程按其状态和时间参数是连续的或离散的，可分为三类：（1）时间、状态都是离散的马尔科夫过程，称为马尔可夫链；（2）时间连续、状态离散的马尔科夫过程称为连续时间的马尔可夫链的；（3）时间、状态都连续的马尔科夫过程。

二、马尔科夫链的定义定义4.1设有随机过程，若对于任意的整数和任意的，条件概率都满足(4.1.1) 则称为马尔科夫链，简称马氏链。

式(4.1.1)即为马氏链，他表明在状态已知的条件下，的条件概率与无关，而仅与所处的状态有关。

式(4.1.1)是马尔科夫链的马氏性（或无后效性）的数学表达式。

由定义知===可见，马尔科夫链的统计特性完全由条件概率所决定。

如何确定这个条件概率，是马尔科夫链理论和应用中的重要问题之一。

现举一例说明上述概念：例4.1.1 箱中装有c个白球和d个黑球，每次从箱子中任取一球，抽出的球要到从箱子中再抽出一球后才放回箱中，每抽出一球作为一次取样试验。

现引进随机变量序列为,每次取样试验的所有可能结果只有两个，即白球或黑球。

若以数代表白球，以数代表黑球则有由上所述的抽球规则可知，任意第n次抽到黑球或白球的概率只与第n-1次抽得球的结果有关，而与抽的球的结果无关，由此可知上述随机变量序列,为马氏链。

三、转移概率定义4.2称条件概率为马尔科夫链在时刻N的一步转移概率，其中，简称为转移概率。

第13章 马尔可夫链13.1 复习笔记一、马尔可夫过程及其概率分布 马尔可夫过程的概率分布 （1）转移概率及其转移概率矩阵 ①转移概率(,){|}ij m n j m i P m m n P X a X a ++===为马氏链在m 时处于a i 的条件下，到m ＋n 时转移到状态a j 的转移概率。

1(,)1,1,2,ij j P m m n i +∞=+==∑②转移概率矩阵 (,)((,))ij P m m n P m m n +=+性质：各元素非负，每行之和为1（2）齐次马氏链的转移概率及转移概率矩阵 一步转移概率为(){}11ij ij m j m i p P P X a X a +====一步转移概率矩阵()11211112122122212=1m j j mj i i i ijX a a a a p p p X a p pp P P a p p p +⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦的状态的记成状态二、多步转移概率的确定1．C-K 方程1()()(),,1,2,ij ik kj k P u v P u P v i j +∞=+==∑2．n 歩转移概率齐次马尔可夫链的n 歩转移概率矩阵P （n ）＝P n三、遍历性 1．定义转移概率()ij P n 存在极限或()()121212jj n jP n P n πππππππππ⎡⎤⎢⎥⎢⎥⎢⎥=→∞⎢⎥⎢⎥⎢⎥⎣⎦则此链具有遍历性，若1jjπ=∑，则12(,,)πππ=为链的极限分布。

2．有限链遍历性的充分条件设齐次马氏链{X n ，n ≥l}的状态空间为12{,,,}N I a a a =，P 是它的一步转移概率矩阵，如果∃m ∈N ＋，使对∀,i j a a I ∈，都有()0,,1,2,,ij P m i j N >=则此链具有遍历性，且有极限分布12(,,,)N ππππ=，它是方程组π＝πP 或1,1,2,Nj i ij i p j Nππ===∑满足条件10,1Nj j j ππ=>=∑的唯一解。