下载文档原格式
马尔科夫链专题讲义马尔科夫链是以俄罗斯数学家安德烈·马尔科夫的名字命名,是一个数学随机模型,描述了一连串可能发生的事件,从一个状态到另外一个状态,也可以是保持当前状态的随机过程.下一个状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关.高中数学中经常与条件概率,全概率公式,贝叶斯公式相结合,构造递推关系求的概率.一、马尔科夫链的性质马尔科夫链具有状态空间,无记忆性,转移概率(转移矩阵)等三个要素,马尔科夫链是从一个状态到另一个状态转化的随机过程,每个状态称为状态空间.无记忆性是而的事件均与之无关.这种特定类型的“无记忆性”称作马尔科天性.在马尔科夫链的每一步,根据概率分布,可以从个状态变频另外一个状态,也可以保持当前状态.状态的改变叫做转移,与不同状态改变相关的概率叫做转移项率.对于随机变量序列X m已知第n小时的状态X n.如果X n−1的随机变化规律与前面的各项X1,X2,⋯,X n−1的取值都没有关系,那么称随机变量序列X n具有马尔科夫性,称具有马尔科夫性的随机变量序列{X n}为马尔科夫链。
二、马尔科夫链基本原理虽然贝叶斯公式不做要求,但是全概率公式已经是新高考考查内容,利用全概率公式,我们既可以构造某些递推关系求解概率,还可以推导经典的一维随机游走模型,即设数轴上一个点,它的位置只能位于整点处,在时刻t=0时,位于点X=i(i∈N∗)一个时刻,它将以概率α或者β(α∈(0,1),α+β=1)向左或者向右平移一个单位.若记状态X t=i表示在时刻t该点位于位置X=i(i∈N∗),那么由全概率公式可得P(X t+1=i)=P(X t=i−1)⋅P(X t+1=i∣X t=i−1)+P(X t=i+1)⋅P(X t+1=i∣X t=i+1).另一方面,由于P(X t+1=i∣X t=i−1)=β,P(X t+1=i∣X t=i+1)=α,代入上式可得P i=α⋅P i+1+β⋅P i−1.进一步,我们假设在x=0与x=m(m>0,m∈N∗)处各有一个吸收壁,当点到达吸收壁时被吸收,不再游走.于是P0=0,P m=1.随机游走模型是一个典型的马尔科夫过程.进一步,若点在某个位置后有三种情况:向左平移一个单位,其概率为a,原地不动,其概率为b,向右平移一个单位,其概率为c,那么根据全概率公式可得P i=aP i−1+bP i+cP i+1.三、应用举例1.药物试验问题例1（2019全国1卷21）为治疗某种欢病,研制了甲、乙两种新药,希望知道哪种新药更有效,为此进行动物试验.试验方案如下:每一轮选取两只白鼠对药效进行对比试验.对于两只白鼠,随机选一只施以甲药,另一只施以乙药.轮的治疗结果得出后,再安排下一轮试验.当其中一种药治愈的白鼠比另一种药治愈的白鼠多4只时,脱停止试验,并认为治愈只数多的药更有效.为了方便描述问题,约定:对于每轮试验,若施以甲药的白贝治愈且施以乙药的白鼠未治愈则甲药得1分,乙药得−1分;若施以乙药的白鼠治愈且施以甲药的白鼠未治愈则乙药得1分,甲药得-1分;若都治愈或都未治愈则两种药均得0分.甲、乙两种药的治愈半分别记为α和β,一轮试验中甲药的得分记为X.(1)求X的分布列:(2)若甲药、乙药在试验开始时都赋予4分,p i(i=0,1.⋯.8)表示“甲药的累计得分为i时,最终认为甲药比乙药更有效”的概率,则p0=0,p i=1,p i=ap i−1+bp i+cp i+1(i=1,2,⋯,7),其中a=P(X=−1),b=P(X=0),c=P(X=1).假设α=0.5,β=0.8.(i)证明:{p i−1−p i}(i=0,1,2,⋯,7)为等比数列;(iii)求p c,并根据p c的值解释这种试验方案的合理性.解:(1)由超意知,X的所有可能取值为-1.0,1.P(X=−1)=(1−α)β,P(X=0)=αβ+(1−α)(1−β),P(X=1)=a(1−β),∴X的分布列为X−10 1P(1−α)βαβ+(1−α)(1−β)α(1−β)(2)(i)由(1)知,a=(1−0.5)×0.8=0.4,b=0.5×0.8+(1−0.5)(1−0.8)=0.5,c=0.5×(1−0.8=0.1.∴p i=0.4p i−1+0.5p i+0.1p i+1,∴0.1(p i+1−p i)=0.4(p i−p i−1),∴p i+1−p i=4(p i−p i−1),又p1−p0=p1≠0,∴{p i+1−p i}(i=0,1,2,⋯,7)是首项为p1,公比为4的等比数列. (ii)由(i)可得p i+1−p i=p1⋅4i,∴p8=p8−p7+p7−p6+⋯+p1−p0+p0=(p8−p7)+(p7−p6)+⋯+(p1−p0)=p1(47+46+⋯+4)=4(1−47) 1−4p1=48−4 3p1∵p8=1,∴48−43p1=1,∴p1=348−4.∴p4=(p4−p3)+(p3−p2)+(p2−p1)+(p1−p0)=p1(43+42+4+1)=1−44 1−4p1=44−13p1=44−13×348−4 =144+1=1257p4表示最终认为甲药更有效的概率.由计算结果可以看出,在甲药治愈率为0.5,乙药治愈率为0.8时,认为甲药更有效的概率为p4=1257≈0.0039,此时得出错误结论的概率非常小,说明这种试验注：虽然当时学生未学过全概率公式,但命题人直接把p i=ap i−1+bp i+cp i+1给出,并没有让考生推导这个递推关系,实际上,这就是一个一维随机游走模型。
证明从略
讲解从略关键点
讲解从略
判定定理
闭集的特性
空间分解与基本闭集的处理观察与思考
分步处理,逐一筛选
有限状态
的总结证明从略
空间结构是什么特别观察与理解
特点的处理与技巧
互通性
探索与观察
有限与无限互换的处理技巧
注意处理方式
传播性
正常返的规律性与统计模式
6.6 极限特性与平稳分布
平稳分布
定义与计算
理论证明与
处理
重复处理重复处理
总结
能想到的
例子是什么?
反证处理
构造性证明
推广
特殊情况
注意:
平均返回时间的计算1
12
3
观图
极限分布平稳分布区别与联
系。
第四章 马尔可夫链随机过程在不同时刻下的状态之间一般具有某种关系，马尔可夫（Markov ）过程就是描述一类状态之间具有某种特殊统计联系的随机过程.Markov 过程在近代物理学、生物学、管理科学、信息处理与数字计算方法等领域都有重要的应用.按其状态和时间参数是连续的或离散的，它可分为三类：（1）时间、状态都是离散的Markov 过程，称为Markov 链；（2）时间连续、状态离散的Markov 过程，称为连续时间的Markov 链；（3）时间、状态都连续的Markov 过程.本章主要讨论Markov 链，有关连续时间的Markov 链的相关理论将在下章讨论.4.1 马尔可夫链的概念和例子独立随机试验模型最直接的推广就是Markov 链模型，早在1906年俄国数学家Markov 对它进行研究而得名，以后Kolmogorov 、Feller 、Doob 等数学家发展了这一理论.4.1 .1 Markov 链的定义假设Markov 过程{,}n X n T ∈的参数集T 是离散时间集合，即{0,1,2,}T =，相应n X 可能取值的全体组成的状态空间是离散状态集012{,,,}I i i i =.定义 4.1 设有一随机过程{,}n X n T ∈，若对于任意整数n T ∈和任意011,,,n i i i I +∈，条件概率满足11001111{|,,,}{|}n n n n n n n n P X i X i X i X i P X i X i ++++=======则称{,}n X n T ∈为离散时间的Markov 链，简称Markov 链（Markov chains ）或马氏链.从定义可以看出：Markov 链具有Markov 性（即无后效性），如果把时刻n 看作现在，那么，1n +是将来的时刻，而0,1,2,,1n -是过去的时刻.Markov 性表示在确切知道系统现在状态的条件下，系统将来的状况与过去的状况无关，而且Markov 链的统计特征完全由条件概率11{|}n n n n P X i X i ++==所决定. 因此，如何确定这个条件概率，是研究Markov 链理论和应用中十分重要的问题之一. 4.1.2 转移概率定义 4.2 称条件概率1(){|}ij n n p n P X j X i +=== （4.1）为Markov 链{,}n X n T ∈在时刻n 的一步转移概率，其中,i j I ∈，简称转移概率（transition probability ）.一般地，转移概率()ij p n 不仅仅与状态,i j 有关，而且与时刻n 有关，如果()ij p n 不依赖时刻n 时，则称Markov 链具有平稳转移概率.定义 4.3 若对任意,i j I ∈，Markov 链{,}n X n T ∈的转移概率()ij p n 与n 无关，则称Markov 链是齐次的（或称时齐的）（time homogeneous -），并记()ij p n 为ij p . 下面只讨论齐次Markov 链，并且通常将“齐次”两字省去.定义 4.4 设P 表示一步转移概率ij p 所组成的矩阵，且状态空间{1,2,}I =，则1112121222...........................n n p p p P p p p ⎛⎫ ⎪= ⎪ ⎪⎝⎭称为系统状态的一步转移概率矩阵（transition probability matrix ），它具有性质： （1）0,,ij p i j I ≥∈； （2）1,ijj Ipi I ∈=∈∑.（2）式说明一步转移概率矩阵中任一行元素之和为1，通常称满足性质（1）（2）的矩阵为随机矩阵.定义 4.5 称条件概率(){|},n ij m n m p P X j X i +=== ,,0,1i j I m n ∈≥≥ （4.2）为Markov 链{,}n X n T ∈的n 步转移概率，并称()()()n n ij P p =为Markov 链{,}n X n T ∈的n 步转移矩阵.其中()()0,1n n ij ij j Ip p ∈≥=∑，即()n P 也是一个随机矩阵.特别地，当1n =时，(1)ij ij p p =，此时，一步转移矩阵(1)P P =.我们还规定(0)0,1,iji jpi j ≠⎧=⎨=⎩Markov 链n 步转移概率满足重要的Chapman Kolmogorov -方程（简称C K -方程）。
不可约马尔可夫链例子什么是不可约马尔可夫链？不可约马尔可夫链是一种马尔可夫过程，其特点在于该链中所有状态都是连通的，即任何状态都可以通过有限步数到达任意其他状态。
这与可约马尔可夫链不同，可约马尔可夫链中某些状态无法到达其他状态。
不可约马尔可夫链的基本性质不可约马尔可夫链的基本性质有以下几点：1. 平稳分布存在且唯一：在不可约马尔可夫链中，总存在一个平稳分布，即一个稳定状态，该状态不随时间变化而改变。
并且，这个平稳分布是唯一的。
2. 转移概率存在极限：在不可约马尔可夫链中，无论起始状态是什么，经过足够长的时间后，状态转移的概率会收敛到一个固定的值，称之为稳定分布。
3. 可逆性：如果一条不可约马尔可夫链任意两个状态之间的转移概率与它们的逆序转移概率相等，那么它是可逆的。
不可约马尔可夫链的应用不可约马尔可夫链在许多领域都有着重要的应用。
比如：1. 序列分析：在序列分析中，利用不可约马尔可夫链对序列进行建模，进而进行序列预测、分类等任务。
2. 社交网络分析：将社交网络中的用户作为状态进行建模，然后研究和预测用户之间的关系变化。
3. 模式识别：基于不可约马尔可夫链的模型可以用来进行模式识别，如识别声音、图像等。
4. 推荐系统：基于用户行为的不可约马尔可夫链可以被用来构建推荐系统，从而预测用户对特定商品的偏好或喜好。
总结不可约马尔可夫链是一类具有重要意义的随机过程，在许多领域都有重要的应用。
在使用该方法进行建模和预测时，需要保证其状态是连通的，即任何状态都能相互到达。
同时需要注意的是，不可约马尔可夫链存在的平稳分布唯一，该分布可以用来计算出系统的稳定状态。
