深圳大学：《概率论与数理统计》课程教学资源（PPT课件讲稿）第十一章 马尔可夫链

第十一章马尔可夫链 §1马尔可夫过程及其概率分 布

2 第十一章 马尔可夫链 §1 马尔可夫过程及其概率分 布

在物理学中,很多确定性现象遵从如下演变原 则:由时刻t系统或过程所处的状态,可以决 定系统或过程在时刻t所处的状态,而无需 借助于以前系统或过程所处状态的历史资 料.如微分方程初值问题所描绘的物理过程 将这样的原则延伸到随机现象,引入马尔可夫 性或无后效性:过程(或系统)在时刻所处的 状态为已知条件下,过程在时刻个t所处状态 的条件分布与过程在时刻t之前的状态无关 即已经知道过程"现在"的条件下,其"将来 不依赖于"过去

3 在物理学中, 很多确定性现象遵从如下演变原 则: 由时刻t0系统或过程所处的状态, 可以决 定系统或过程在时刻t>t0所处的状态, 而无需 借助于t0以前系统或过程所处状态的历史资 料. 如微分方程初值问题所描绘的物理过程. 将这样的原则延伸到随机现象, 引入马尔可夫 性或无后效性: 过程(或系统)在时刻t0所处的 状态为已知条件下, 过程在时刻t>t0所处状态 的条件分布与过程在时刻t0之前的状态无关. 即已经知道过程"现在"的条件下, 其"将来" 不依赖于"过去

设随机过程{X(,t∈仍的状态空间为.如果对 任意n个时间值t1<2…<n,n≥3,∈T,在条件 X(t)=xpx∈l,i=1,2,,n-1下 PX(tnsrnlx(ti=x1, x(2=x2sxX(t-1=Xm-1 P{X(tn)≤xn|X(tn1)=xn1B,xn∈R,(1.1) 或写成 tnt1…( n n 19299n-1919299n-1 F nI'n-1 nn t n 则称过程{X(,t∈T}具有马尔可夫性或无后效 性,并称此过程为马尔可夫过程

4 设随机过程{X(t), tT}的状态空间为I. 如果对 任意n个时间值t1<t2<...<tn , n3, t iT, 在条件 X(t i )=xi ,xiI, i=1,2,...,n-1下, P{X(tn )xn |x(t1 )=x1 , X(t2 )=x2 ,...,X(tn-1 )=xn-1 } =P{X(tn )xn |X(tn-1 )=xn-1 }, xnR, (1.1) 或写成 ( , | , ), ( , | , , , ; , , , ) | 1 1 | 1 2 1 1 2 1 1 1 - - - - - = t t n n n n t t t n n n n F x t x t F x t x x x t t t n n n  n   则称过程{X(t), tT}具有马尔可夫性或无后效 性, 并称此过程为马尔可夫过程

例1设{X(O),公0}是独立增量过程,且X(0)=0, 证明{X(2≥0是一个马尔可夫过程 证由(11)式知,只要证明在已知X(tn1)=xn1的 条件下X()与X(),=1,2,…,n-2相互独立即可 而当0n1户12…,-2时,增量 X(4)-X(0)与X(tn)-X(n21) 相互独立根据条件X()=0和X(n)=xn1,知 X()与X(n)xn-1 相互独立此时X(tn)与X(t=1,2,,n-2相互 独立这表明X(具有无后效性,即{X(),0} 是一个马尔可夫过程

5 例1 设{X(t),t0}是独立增量过程, 且X(0)=0, 证明{X(t),t0}是一个马尔可夫过程. 证 由(1.1)式知, 只要证明在已知X(tn-1 )=xn-1的 条件下X(tn )与X(t j ), j=1,2,...,n-2相互独立即可. 而当0<t j<tn-1<tn , j=1,2,...,n-2时, 增量 X(t j )-X(0) 与 X(tn )-X(tn-1 ) 相互独立. 根据条件X(0)=0和X(tn-1 )=xn-1 , 知 X(t j ) 与 X(tn )-xn-1 相互独立. 此时X(tn )与X(t j ), j=1,2,...,n-2相互 独立. 这表明X(t)具有无后效性, 即{X(t),t0} 是一个马尔可夫过程

由此可知,泊松过程是时间连续状态离散的马 氏过程,维纳过程是时间状态都连续的马氏过 程 时间和状态都是离散的马尔可夫过程称为互 尔可夫链简称马氏链,记为{Xn=X(m),n=0,1, 2,},它可以看作在时间集T1={0,1,2,}上对 离散状态的马氏过程相继观察的结果我们约 定记链的状态空间F={a1a2,,a1∈R

6 由此可知, 泊松过程是时间连续状态离散的马 氏过程, 维纳过程是时间状态都连续的马氏过 程. 时间和状态都是离散的马尔可夫过程称为马 尔可夫链, 简称马氏链, 记为{Xn =X(n), n=0, 1, 2,...}, 它可以看作在时间集T1={0,1,2,...}上对 离散状态的马氏过程相继观察的结果. 我们约 定记链的状态空间I={a1 ,a2 ,...}, aiR

对链的情形对任意的正整数nr和0≤1<(2x m;tm,n+m∈T1,有 PiX m+n 7nX64=1,X2=a2;…,X,=a1,Xm=n1} = PXmn=aXm=ai3 (1.2) 其中a∈L记上式右端为Pm,mn+m)称 Pi(m, m+n)=PXm=aim=ai3(1.3) 为马氏链在时刻m处于状态a条件下,在时刻 m+n转移到状态a;的转移概率.易知 ∑(m,m+m)=1,i=1,2,…(14)

7 对链的情形, 对任意的正整数n,r和0t1<t2<...< t r <m; t i , m, n+mT1 , 有 { | }, (1.2) { | , , , , } 1 1 2 2 m n j m i m n j t i t i t i m i P X a X a P X a X a X a X a X a r r = = = = = = = = + +  ( , ) 1, 1,2, . (1.4) 1  + = =   = P m m n i j i j 其中aiI. 记上式右端为Pij(m,m+n), 称 Pij(m,m+n)=P{Xm+n =aj |Xm =ai } (1.3) 为马氏链在时刻m处于状态ai条件下, 在时刻 m+n转移到状态aj的转移概率. 易知

转移概率组成的矩阵P(m,m+n)=(Pm,m+mn) 称为马氏链的转移概率矩阵,上式表明此矩阵 的每一行元素之和等于1 当转移概率P;(m,m+n)只与及时间间距n有 关时,把它记为P(m,即 Pi (m, m+n=Pi(n) 并称此转移概率具有平稳性.同时也称此链是 齐次的或时齐的.以下仅限于讨论齐次马氏 链

8 转移概率组成的矩阵P(m,m+n)=(Pij(m,m+n)) 称为马氏链的转移概率矩阵, 上式表明此矩阵 的每一行元素之和等于1. 当转移概率Pij(m,m+n)只与i,j及时间间距n有 关时, 把它记为Pij(n), 即 Pij(m,m+n)=Pij(n) 并称此转移概率具有平稳性. 同时也称此链是 齐次的或时齐的. 以下仅限于讨论齐次马氏 链

在马氏链为齐次的情形下,转移概率 P∴(m)=P(Xm+n=4,Xm=a 称为马氏链的n步转移概率,P(n)=(Pm)为n 步转移概率矩阵.在以下的讨论中特别重要的 是一步转移概率 PipI ()=PXm+=a, ai 或由它们组成的一步转移概率矩阵

9 在马氏链为齐次的情形下, 转移概率 Pij(n)=P{Xm+n =aj |Xm =ai } (1.5) 称为马氏链的n步转移概率, P(n)=(Pij(n))为n 步转移概率矩阵. 在以下的讨论中特别重要的 是一步转移概率 pij=Pij(1)=P{Xm+1=aj |Xm =ai } 或由它们组成的一步转移概率矩阵

Xn的状态 X的状态 app app 12 记成 21 p2 P(1)=P Pil p 在上述矩阵的左侧和上边标上状态a14a2,是 为了显示;是由状态a步转移到状态的概 率

10 在上述矩阵的左侧和上边标上状态a1 ,a2 ,...,是 为了显示pij是由状态ai一步转移到状态aj的概 率. • + = =               P P p p p p p p p p p a a a a a a X X i i i j j j i j m m 记 成 态 状 的 的状态 (1) 1 2 2 1 2 2 2 1 1 1 2 1 2 1 1 2 1                

例2如图所示只传输数字0和1的系统串联系 统中,设每一级传真率为p,误码率为q=1-p, 设一个单位时间传输一级,Ⅺ是第一级的输入, Xn是第n级的输出(n21,则{Xnn=0,1,2,}是 随机过程状态空间={0,1},当Xn=i,i为 已知时,X所处的状态的概率分布只与Xn=i 有关,而与时刻n以前的状态无关,所以它是 个齐次的马氏链

11 例2 如图所示只传输数字0和1的系统串联系 统中, 设每一级传真率为p, 误码率为q=1-p, 设一个单位时间传输一级, X0是第一级的输入, Xn是第n级的输出(n1). 则{Xn , n=0,1,2,...}是 一随机过程, 状态空间I={0,1}, 当Xn =i, iI为 已知时, Xn+1所处的状态的概率分布只与Xn =i 有关, 而与时刻n以前的状态无关, 所以它是 一个齐次的马氏链. 1 2 n X0 X1 X2 Xn-1 Xn