杭州紫金港培训学校(紫金港专升本)杭州紫金港培训学校(紫金港专升本)
同等学力申硕信息与通信工程学科综合考前辅导第一门 随机数学(必选)第 6 节 / 共 32 节约 30 分钟免费

应用随机过程(二):马尔可夫链

对应随机数学(六)马尔可夫过程第 1—4 条:马尔可夫链的转移概率与时齐性,C-K 方程与多步转移,状态的可达、互通、周期,常返性与遍历性,平稳分布,状态类与状态空间分解。

本节考点:转移概率与时齐性C-K 方程状态分类与空间分解常返性与遍历性平稳分布

本节导读

这一节对应「(六)马尔可夫过程」的前四条:

  1. 马尔可夫链的概率转移函数;时齐性。
  2. 查普曼-柯尔莫哥洛夫(Chapman-Kolmogorov)方程(C-K 方程)。
  3. 常返性与遍历性;平稳分布。
  4. 状态类与状态空间分解。

后四条(马尔可夫过程、随机游动、泊松过程、布朗运动)在第 7 节。学完要做到:会写转移矩阵并用 C-K 方程求多步转移概率和任一时刻的分布;会判断可达、互通、周期、常返与非常返;会求平稳分布;会把状态空间分解成非常返集和若干个闭的常返类。

本节记号:状态空间 SSS;nnn 步转移概率 pij(n)p_{ij}^{(n)}pij(n)​,一步时简写 pijp_{ij}pij​;转移矩阵 P\mathbf PP(粗体,与第 2 节的概率 P(⋅)P(\cdot)P(⋅) 区分);绝对分布(行向量)p(n)\mathbf p(n)p(n);平稳分布 π=(πj)\boldsymbol\pi=(\pi_j)π=(πj​)。

转移概率与时齐性

时间、状态都离散、具有马尔可夫性的过程 {Xn,n=0,1,2,⋯ }\{X_n,n=0,1,2,\cdots\}{Xn​,n=0,1,2,⋯} 叫马尔可夫链。它的概率转移函数是

pij(m,m+n)=P{Xm+n=j∣Xm=i}p_{ij}(m,m+n)=P\{X_{m+n}=j\mid X_m=i\}pij​(m,m+n)=P{Xm+n​=j∣Xm​=i}

若它与起点 mmm 无关、只与步数 nnn 有关,称为时齐的马尔可夫链,这时记作 pij(n)p_{ij}^{(n)}pij(n)​。时齐链完全由初始分布 p(0)\mathbf p(0)p(0) 和一步转移矩阵 P=(pij)\mathbf P=(p_{ij})P=(pij​) 确定。P\mathbf PP 的每个元素非负、每一行之和为 1(随机矩阵)。

通信里一个常见的例子是信道的「好—坏」两状态模型:信道处在好状态时误码很少,处在坏状态时误码成串出现,下一时刻的状态只与当前状态有关。

C-K 方程与多步转移

查普曼-柯尔莫哥洛夫方程说,从 iii 走 m+nm+nm+n 步到 jjj,可以按第 mmm 步落在哪个状态 kkk 分解:

pij(m+n)=∑k∈Spik(m)pkj(n)p_{ij}^{(m+n)}=\sum_{k\in S}p_{ik}^{(m)}p_{kj}^{(n)}pij(m+n)​=k∈S∑​pik(m)​pkj(n)​

写成矩阵是 P(m+n)=P(m)P(n)\mathbf P^{(m+n)}=\mathbf P^{(m)}\mathbf P^{(n)}P(m+n)=P(m)P(n),于是 nnn 步转移矩阵 P(n)=Pn\mathbf P^{(n)}=\mathbf P^nP(n)=Pn。任一时刻的绝对分布 p(n)=p(0)Pn\mathbf p(n)=\mathbf p(0)\mathbf P^np(n)=p(0)Pn。求两步转移概率时,把所有中间状态的路径都加起来,一条都不能漏。

状态的分类

  • 可达与互通:存在 nnn 使 pij(n)>0p_{ij}^{(n)}\gt 0pij(n)​>0,称 iii 可达 jjj;相互可达称互通。互通是等价关系,把状态空间分成若干个互通类;只有一个互通类的链叫不可约链。
  • 周期:did_idi​ 是使 pii(n)>0p_{ii}^{(n)}\gt 0pii(n)​>0 的所有 nnn 的最大公约数。di>1d_i\gt 1di​>1 为周期状态,di=1d_i=1di​=1 为非周期状态;同一互通类的状态周期相同。有自环(pii>0p_{ii}\gt 0pii​>0)的状态一定非周期。
  • 常返与非常返:记 fiif_{ii}fii​ 为从 iii 出发终将返回 iii 的概率。fii=1f_{ii}=1fii​=1 称常返,fii<1f_{ii}\lt 1fii​<1 称非常返(暂态)。常返态又按平均返回时间 μi\mu_iμi​ 有限或无穷分为正常返与零常返。等价判据:iii 常返 ⇔ ∑npii(n)=∞\sum_np_{ii}^{(n)}=\infty∑n​pii(n)​=∞。
  • 遍历态:非周期的正常返态。

几条常用结论:同一互通类的状态同为常返或同为非常返;有限状态链至少有一个常返态,且没有零常返态;有限不可约链的状态都是正常返的。

状态空间分解

一个状态集合 CCC 若从里面出发永远走不出去(对 i∈Ci\in Ci∈C、j∉Cj\notin Cj∈/C 都有 pij=0p_{ij}=0pij​=0),称为闭集;只含一个状态的闭集就是吸收态。状态空间可以唯一地分解为

S=N∪C1∪C2∪⋯S=N\cup C_1\cup C_2\cup\cdotsS=N∪C1​∪C2​∪⋯

NNN 是全部非常返态组成的集合,每个 CkC_kCk​ 是由常返态组成的、互通的闭集。链从非常返态出发,最终会进入某个常返闭集并停留在其中。做分解时,先画状态转移图,按箭头找出互通类,再看每一类是不是闭的:有限链中闭的互通类是常返类,不闭的类里都是非常返态。

遍历性与平稳分布

满足 π=πP\boldsymbol\pi=\boldsymbol\pi\mathbf Pπ=πP、∑jπj=1\sum_j\pi_j=1∑j​πj​=1、πj≥0\pi_j\ge 0πj​≥0 的分布叫平稳分布:以它为初始分布,以后每一时刻的分布都不变。

遍历定理:有限状态的马尔可夫链若不可约、非周期,则对一切 iii,lim⁡n→∞pij(n)=πj\lim\limits_{n\to\infty}p_{ij}^{(n)}=\pi_jn→∞lim​pij(n)​=πj​ 存在、与 iii 无关,π\boldsymbol\piπ 就是唯一的平稳分布,并且 πj=1μj\pi_j=\dfrac{1}{\mu_j}πj​=μj​1​。直观地说,长时间运行后,链落在 jjj 的时间比例约为 πj\pi_jπj​。

两状态链 P=[1−aab1−b]\mathbf P=\begin{bmatrix}1-a&a\\ b&1-b\end{bmatrix}P=[1−ab​a1−b​](0<a,b<10\lt a,b\lt 10<a,b<1)的平稳分布有现成的式子:π1=ba+b\pi_1=\dfrac{b}{a+b}π1​=a+bb​,π2=aa+b\pi_2=\dfrac{a}{a+b}π2​=a+ba​。状态多时,列 π=πP\boldsymbol\pi=\boldsymbol\pi\mathbf Pπ=πP 的方程组,去掉一个方程、加上归一化条件求解。

易错提醒

  • ❌ 转移矩阵每一列之和为 1。
    ✅ 按行看:第 iii 行是从状态 iii 出发去各状态的条件概率,行和为 1。

  • ❌ 有限状态的马尔可夫链里也常有零常返态。
    ✅ 有限状态链没有零常返态;零常返只出现在无限状态链中,例如直线上对称的简单随机游动(第 7 节)。

  • ❌ C-K 方程只对时齐链成立。
    ✅ 非时齐链同样满足 C-K 方程,只是要带上起点:P(m,m+n+l)=P(m,m+n)P(m+n,m+n+l)\mathbf P(m,m+n+l)=\mathbf P(m,m+n)\mathbf P(m+n,m+n+l)P(m,m+n+l)=P(m,m+n)P(m+n,m+n+l);时齐时才化成矩阵的幂。

例题精讲

例题 1(计算:两状态信道的两步转移与平稳分布)

信道每个时隙处于「好」(状态 1)或「坏」(状态 2),P=[0.90.10.30.7]\mathbf P=\begin{bmatrix}0.9&0.1\\0.3&0.7\end{bmatrix}P=[0.90.3​0.10.7​]。已知当前为好状态,求两个时隙后处于坏状态的概率,以及长期处于坏状态的时间比例。

解:两步转移,按中间状态分两条路:

p12(2)=0.9×0.1+0.1×0.7=0.16p_{12}^{(2)}=0.9\times 0.1+0.1\times 0.7=0.16p12(2)​=0.9×0.1+0.1×0.7=0.16

链不可约,又有自环、非周期,平稳分布 π2=0.10.1+0.3=0.25\pi_2=\dfrac{0.1}{0.1+0.3}=0.25π2​=0.1+0.30.1​=0.25。长期看约 25% 的时隙信道处于坏状态。

点评:两步概率 0.16 还没到 0.25,说明链还在向平稳分布靠近;步数越多越接近。

例题 2(判断:状态空间分解)

四状态链的一步转移概率为:p11=0.5p_{11}=0.5p11​=0.5,p12=0.5p_{12}=0.5p12​=0.5;p21=0.6p_{21}=0.6p21​=0.6,p22=0.4p_{22}=0.4p22​=0.4;p31=0.2p_{31}=0.2p31​=0.2,p33=0.5p_{33}=0.5p33​=0.5,p34=0.3p_{34}=0.3p34​=0.3;p44=1p_{44}=1p44​=1。做状态空间分解。

解:1、2 互通,从它们出发只能到 1、2,{1,2}\{1,2\}{1,2} 是闭的互通类,常返;4 是吸收态,{4}\{4\}{4} 是闭集,常返;3 能到 1 和 4,却不能从它们回到 3,是非常返态。所以 S={3}∪{1,2}∪{4}S=\{3\}\cup\{1,2\}\cup\{4\}S={3}∪{1,2}∪{4}。

点评:从 3 出发,最终会以一定概率被 {1,2}\{1,2\}{1,2} 吸收,其余概率被 4 吸收,不会永远停在 3。

本节小结

  • 时齐马尔可夫链由初始分布和一步转移矩阵确定;转移矩阵行和为 1。
  • C-K 方程:P(n)=Pn\mathbf P^{(n)}=\mathbf P^nP(n)=Pn,p(n)=p(0)Pn\mathbf p(n)=\mathbf p(0)\mathbf P^np(n)=p(0)Pn;两步概率要加遍所有中间状态。
  • 状态分类:可达、互通、周期、常返(fii=1f_{ii}=1fii​=1)与非常返、正常返与零常返、遍历态。
  • 状态空间分解:S=N∪C1∪C2∪⋯S=N\cup C_1\cup C_2\cup\cdotsS=N∪C1​∪C2​∪⋯,非常返集加若干闭的常返类。
  • 有限、不可约、非周期 ⇒ 极限分布存在且等于唯一的平稳分布,πj=1/μj\pi_j=1/\mu_jπj​=1/μj​。

学完练一练

按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。

本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。

我要提问免费报名咨询