线性代数 · 马尔可夫链

马尔可夫链

马尔可夫链在几个状态之间随机地走,下一步到哪个状态的概率只取决于现在的状态。把这些概率写成转移矩阵P,明天的分布就是今天的分布乘P;反复乘下去,常常落到一个稳态π:πP = π,是特征值1的特征向量。

马尔可夫链与本页画面

马尔可夫链在几个状态之间随机地走,下一步到哪个状态的概率只取决于现在的状态。本页的状态是晴、阴、雨。转移矩阵PP的第ii行写的是今天处在状态ii时明天各状态的概率,所以每一行都是概率向量。今天的分布是行向量pp,明天就是pPpP,nn天后是pn=p0Pnp_n = p_0 P^n。只有三个状态时,每个分布都是三角形里的一个点:三个角各是“确定是这个状态”,三个概率就是这个点在三个角上的权重。图中墨色点是PP的三行,蓝点是起点,红色路径连起p0,p1,p2,…p_0, p_1, p_2, \dots

一步做了什么

一步把每个角送到它那一行:确定晴的一天,第二天的分布就是第一行。别的分布pp是三个角的加权平均,所以pPpP是三行的同样加权平均。于是整个三角形落进三行围成的小三角形,两步落进P2P^2的三行围成的更小的三角形,依此类推。当PP的某个幂所有元素都为正时,这些套在一起的三角形收向一个点:稳态π\pi。

π为什么是特征向量,p_n收得多快

不动的那个点满足πP=π\pi P = \pi:π\pi是特征值1的特征向量(左特征向量;写成列向量就是PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T})。差p0−πp_0 - \pi的各分量加起来是0,PP在这样的向量上通过另外两个特征值λ2,λ3\lambda_2, \lambda_3起作用:每走一步,沿特征向量方向的向量会乘上对应的特征值。所以两者的模都小于1时,pnp_n趋向π\pi,较大的模∣λ2∣|\lambda_2|决定快慢。天气链∣λ2∣≈0.462|\lambda_2| \approx 0.462,nn大了以后每走一步距离剩下不到一半(起点含λ2\lambda_2方向的分量时);两个特征值是复数时,路径边缩边转。

落不到稳态的时候

循环链里晴必转阴、阴必转雨、雨必转晴。另两个特征值的模是1,pnp_n永远转圈,除非起点就是π\pi。两个吸收态时,晴和雨一旦出现就不再变:特征值1出现两次,晴和雨的任何混合都不动,所以pnp_n仍会稳定下来,但落在哪里取决于起点。对有限个状态的链,pnp_n从任何起点都趋向同一个π\pi,恰好当链只有一个闭类(一组能互相到达、而且走不出去的状态),并且这个闭类不是周期的。常用的判据是某个幂PmP^m所有元素都为正。

值得注意

  • 对天气链,不论从哪里出发,稳态都是很久以后某一天各种天气的概率;天气本身照样每天在变。
  • 状态多于三个时,分布占满更高维的“三角形”(单纯形),道理相同。

操作

  • 拖墨色点改转移矩阵的一行,拖蓝点改起点;选中一个点后方向键每次移动百分之一。

相关概念