应用随机过程(二):马尔可夫链
对应随机数学(六)马尔可夫过程第 1—4 条:马尔可夫链的转移概率与时齐性,C-K 方程与多步转移,状态的可达、互通、周期,常返性与遍历性,平稳分布,状态类与状态空间分解。
本节导读
这一节对应「(六)马尔可夫过程」的前四条:
- 马尔可夫链的概率转移函数;时齐性。
- 查普曼-柯尔莫哥洛夫(Chapman-Kolmogorov)方程(C-K 方程)。
- 常返性与遍历性;平稳分布。
- 状态类与状态空间分解。
后四条(马尔可夫过程、随机游动、泊松过程、布朗运动)在第 7 节。学完要做到:会写转移矩阵并用 C-K 方程求多步转移概率和任一时刻的分布;会判断可达、互通、周期、常返与非常返;会求平稳分布;会把状态空间分解成非常返集和若干个闭的常返类。
本节记号:状态空间 S;n 步转移概率 pij(n),一步时简写 pij;转移矩阵 P(粗体,与第 2 节的概率 P(⋅) 区分);绝对分布(行向量)p(n);平稳分布 π=(πj)。
转移概率与时齐性
时间、状态都离散、具有马尔可夫性的过程 {Xn,n=0,1,2,⋯} 叫马尔可夫链。它的概率转移函数是
pij(m,m+n)=P{Xm+n=j∣Xm=i}若它与起点 m 无关、只与步数 n 有关,称为时齐的马尔可夫链,这时记作 pij(n)。时齐链完全由初始分布 p(0) 和一步转移矩阵 P=(pij) 确定。P 的每个元素非负、每一行之和为 1(随机矩阵)。
通信里一个常见的例子是信道的「好—坏」两状态模型:信道处在好状态时误码很少,处在坏状态时误码成串出现,下一时刻的状态只与当前状态有关。
C-K 方程与多步转移
查普曼-柯尔莫哥洛夫方程说,从 i 走 m+n 步到 j,可以按第 m 步落在哪个状态 k 分解:
pij(m+n)=k∈S∑pik(m)pkj(n)写成矩阵是 P(m+n)=P(m)P(n),于是 n 步转移矩阵 P(n)=Pn。任一时刻的绝对分布 p(n)=p(0)Pn。求两步转移概率时,把所有中间状态的路径都加起来,一条都不能漏。
状态的分类
- 可达与互通:存在 n 使 pij(n)>0,称 i 可达 j;相互可达称互通。互通是等价关系,把状态空间分成若干个互通类;只有一个互通类的链叫不可约链。
- 周期:di 是使 pii(n)>0 的所有 n 的最大公约数。di>1 为周期状态,di=1 为非周期状态;同一互通类的状态周期相同。有自环(pii>0)的状态一定非周期。
- 常返与非常返:记 fii 为从 i 出发终将返回 i 的概率。fii=1 称常返,fii<1 称非常返(暂态)。常返态又按平均返回时间 μi 有限或无穷分为正常返与零常返。等价判据:i 常返 ⇔ ∑npii(n)=∞。
- 遍历态:非周期的正常返态。
几条常用结论:同一互通类的状态同为常返或同为非常返;有限状态链至少有一个常返态,且没有零常返态;有限不可约链的状态都是正常返的。
状态空间分解
一个状态集合 C 若从里面出发永远走不出去(对 i∈C、j∈/C 都有 pij=0),称为闭集;只含一个状态的闭集就是吸收态。状态空间可以唯一地分解为
S=N∪C1∪C2∪⋯N 是全部非常返态组成的集合,每个 Ck 是由常返态组成的、互通的闭集。链从非常返态出发,最终会进入某个常返闭集并停留在其中。做分解时,先画状态转移图,按箭头找出互通类,再看每一类是不是闭的:有限链中闭的互通类是常返类,不闭的类里都是非常返态。
遍历性与平稳分布
满足 π=πP、∑jπj=1、πj≥0 的分布叫平稳分布:以它为初始分布,以后每一时刻的分布都不变。
遍历定理:有限状态的马尔可夫链若不可约、非周期,则对一切 i,n→∞limpij(n)=πj 存在、与 i 无关,π 就是唯一的平稳分布,并且 πj=μj1。直观地说,长时间运行后,链落在 j 的时间比例约为 πj。
两状态链 P=[1−aba1−b](0<a,b<1)的平稳分布有现成的式子:π1=a+bb,π2=a+ba。状态多时,列 π=πP 的方程组,去掉一个方程、加上归一化条件求解。
易错提醒
-
❌ 转移矩阵每一列之和为 1。
✅ 按行看:第 i 行是从状态 i 出发去各状态的条件概率,行和为 1。 -
❌ 有限状态的马尔可夫链里也常有零常返态。
✅ 有限状态链没有零常返态;零常返只出现在无限状态链中,例如直线上对称的简单随机游动(第 7 节)。 -
❌ C-K 方程只对时齐链成立。
✅ 非时齐链同样满足 C-K 方程,只是要带上起点:P(m,m+n+l)=P(m,m+n)P(m+n,m+n+l);时齐时才化成矩阵的幂。
例题精讲
例题 1(计算:两状态信道的两步转移与平稳分布)
信道每个时隙处于「好」(状态 1)或「坏」(状态 2),P=[0.90.30.10.7]。已知当前为好状态,求两个时隙后处于坏状态的概率,以及长期处于坏状态的时间比例。
解:两步转移,按中间状态分两条路:
p12(2)=0.9×0.1+0.1×0.7=0.16链不可约,又有自环、非周期,平稳分布 π2=0.1+0.30.1=0.25。长期看约 25% 的时隙信道处于坏状态。
点评:两步概率 0.16 还没到 0.25,说明链还在向平稳分布靠近;步数越多越接近。
例题 2(判断:状态空间分解)
四状态链的一步转移概率为:p11=0.5,p12=0.5;p21=0.6,p22=0.4;p31=0.2,p33=0.5,p34=0.3;p44=1。做状态空间分解。
解:1、2 互通,从它们出发只能到 1、2,{1,2} 是闭的互通类,常返;4 是吸收态,{4} 是闭集,常返;3 能到 1 和 4,却不能从它们回到 3,是非常返态。所以 S={3}∪{1,2}∪{4}。
点评:从 3 出发,最终会以一定概率被 {1,2} 吸收,其余概率被 4 吸收,不会永远停在 3。
本节小结
- 时齐马尔可夫链由初始分布和一步转移矩阵确定;转移矩阵行和为 1。
- C-K 方程:P(n)=Pn,p(n)=p(0)Pn;两步概率要加遍所有中间状态。
- 状态分类:可达、互通、周期、常返(fii=1)与非常返、正常返与零常返、遍历态。
- 状态空间分解:S=N∪C1∪C2∪⋯,非常返集加若干闭的常返类。
- 有限、不可约、非周期 ⇒ 极限分布存在且等于唯一的平稳分布,πj=1/μj。
学完练一练
按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。
本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。