Logo

在马尔科夫链中的应用

1. 马尔可夫链的基本概念与定义

马尔可夫链 (Markov chains) ~(\textbf{Markov chains})~是一种用于描述系统状态随时间演化的数学模型，其核心特点是无记忆性，即系统下一时刻的状态仅依赖于当前状态，而与过去的状态无关。例如，城市间人口流动可以使用马尔可夫链进行建模，用以分析人口迁移的动态变化。下面的热力图展示了一个简化后的模型，其中仅包含城市 A, B, C ~A,\,B,\,C~三地的人口流动情况：
这个热力图通过颜色深浅直观地展示了从当前城市的人口流动到其他城市的概率。例如，城市 A ~A~中的人口，在接下来的一年有 85% ~85\%~的概率仍然是留在城市 A ~A~，5% 5\%~的概率流动到城市 B ~B~，10% 10\%~的概率动到城市 C ~C~。这些概率值构成了一个概率向量 (probability vector) ~(\textbf{probability vector})~，即一个非负且元素之和为 1 ~1~的向量。上述例子中，城市 A ~A~对应的概率向量是[0.850.050.1]T\begin{bmatrix}0.85 & 0.05 & 0.1\end{bmatrix}^T。而这些概率向量则构成了一个随机矩阵 (stochastic matrix) ~(\textbf{stochastic matrix})~：
P=[0.850.10.040.050.80.060.10.10.9]\mathbf{P} = \begin{bmatrix} 0.85 & 0.1 & 0.04 \\ 0.05 & 0.8 & 0.06 \\ 0.1 & 0.1 & 0.9 \end{bmatrix}
马尔可夫链就是一系列概率向量 x0,x1,x2,⋯ ~\mathbf{x}_0,\mathbf{x}_1,\mathbf{x}_2,\cdots~组成的序列，它与随机矩阵 P ~\mathbf{P}~相关联，并满足递推关系：
x1=Px0,x2=Px1,x3=Px2,…\mathbf{x}_1 = \mathbf{P} \mathbf{x}_0, \quad \mathbf{x}_2 = \mathbf{P} \mathbf{x}_1, \quad \mathbf{x}_3 = \mathbf{P} \mathbf{x}_2, \dots
这和离散动力系统的迭代形式非常相似，只不过这里的状态转移是通过随机矩阵进行的。因此，我们可以用差分方程的方法来求解马尔可夫链在长期演化后的状态：
xk+1=Pxk ,k=0,1,2,…\mathbf{x}_{k+1} = \mathbf{P} \mathbf{x}_k\,, \quad k = 0,1,2,\dots
其中， xk ~\mathbf{x}_k~的每个分量代表系统在 n ~n~个可能状态之一的概率（通常会做归一化），因此， xk ~\mathbf{x}_k~也被称为状态向量 (state vector) ~\textbf{(state vector)}~。

2. 应用实例：城市人口迁移模型

现有 A,B,C ~A,B,C~三个城市，我们可以用一个随机矩阵 P ~\mathbf{P}~来描述不同城市之间的人口迁移情况：
P=[0.850.100.040.050.800.060.100.100.90]\mathbf{P} = \begin{bmatrix} 0.85 & 0.10 & 0.04 \\ 0.05 & 0.80 & 0.06 \\ 0.10 & 0.10 & 0.90 \end{bmatrix}
这个矩阵的每一列表示一个城市的人口分布概率，即该城市的人口在一年后留在原地或迁移到其他城市的比例。我们可以通过差分方程计算未来几年的人口分布：
xk+1=Pxk\mathbf{x}_{k+1} = \mathbf{P}\mathbf{x}_k
假设今年 (2025) ~(2025)~， A, B, C ~A,\,B,\,C~三个城市的人口分别为 x0=[503020]T~\mathbf{x}_0 = \begin{bmatrix}50 & 30 & 20\end{bmatrix}^T（单位万人），那么明年 (2026) ~(2026)~三个城市的人口预计为：
x1=Px0=[0.850.100.040.050.800.060.100.100.90][503020]=[46.327.726]\mathbf{x}_1 = \mathbf{P} \mathbf{x}_0 = \begin{bmatrix} 0.85 & 0.10 & 0.04 \\ 0.05 & 0.80 & 0.06 \\ 0.10 & 0.10 & 0.90 \end{bmatrix} \begin{bmatrix} 50 \\ 30 \\ 20 \end{bmatrix} = \begin{bmatrix}46.3 \\ 27.7 \\ 26\end{bmatrix}
同样的方法，可以计算后续年份的人口分布情况。不过，随着时间的推移，即使继续模拟人口流动，各城市的人口比例会逐渐稳定，最终不会发生显著变化。请观察下面的人口变化趋势图：

开通会员解锁全部动画

上面的人口变化趋势图表明，在经过若干年后，三个城市的人口会稳定在：城市 A ~A~约 28 ~28~万人，城市 B ~B~约 22 ~22~万人，城市 C ~C~约 50 ~50~万人。接下来我们会证明：无论初始人口如何分布，最终三个城市的人口占比都会稳定下来（即 28:22:50 ~28:22:50~的比例）。

3. 稳态向量与特征值理论

在人口迁移的过程中，每一年人口分布的变化都是由随机矩阵 P ~\mathbf{P}~决定的：
xk+1=Pxk\mathbf{x}_{k+1} = \mathbf{P}\mathbf{x}_k
如果经过无限次迭代后，系统达到了稳定状态，即：
x∞=Px∞\mathbf{x}_{\infty} = \mathbf{P}\mathbf{x}_{\infty}
这意味着最终的人口分布不会再发生变化，即：
Pq=q\mathbf{P} \mathbf{q} = \mathbf{q}
其中 q ~\mathbf{q}~就是稳态向量 (steady-state vector) ~(\textbf{steady-state vector})~。而 q ~\mathbf{q}~是矩阵 P ~\mathbf{P}~的一个特征向量，对应的特征值是 1 ~1~。下面给出一个关于随机矩阵 P ~\mathbf{P}~的重要定理：

  1. 随机矩阵的性质：每列的元素之和为 1 ~1~，即：
    P=[p11⋯p1j⋯p1n⋮⋱⋮⋱⋮pi1⋯pij⋯pin⋮⋱⋮⋱⋮pn1⋯pnj⋯pnn],∑i=1npij=1\mathbf{P} = \begin{bmatrix} p_{11} & \cdots & \textcolor{#ff8200}{p_{1j}} & \cdots & p_{1n} \\ \vdots & \ddots & \textcolor{#ff8200}{\vdots} & \ddots & \vdots \\ p_{i1} & \cdots & \textcolor{#ff8200}{p_{ij}} & \cdots & p_{in} \\ \vdots & \ddots & \textcolor{#ff8200}{\vdots} & \ddots & \vdots \\ p_{n1} & \cdots & \textcolor{#ff8200}{p_{nj}} & \cdots & p_{nn} \end{bmatrix},\quad \sum_{i=1}^{n} \textcolor{#ff8200}{p_{ij}} = 1
    。
  2. 构造特征向量：
    • 令 e ~\mathbf{e}~是一个所有分量都为 1 ~1~的向量：
      e=[11⋮1]\mathbf{e}=\begin{bmatrix}1 \\1 \\ \vdots \\1\end{bmatrix}
    • 计算PTe\mathbf{P}^T \mathbf{e}：
      PTe=[p11⋯pi1⋯pn1⋮⋱⋮⋱⋮p1j⋯pij⋯pnj⋮⋱⋮⋱⋮p1n⋯pin⋯pnn][1⋮1⋮1]=e\mathbf{P}^T \mathbf{e} = \begin{bmatrix} p_{11} & \cdots & p_{i1} & \cdots & p_{n1} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \textcolor{#ff8200}{p_{1j}} & \cdots & \textcolor{#ff8200}{p_{ij}} & \cdots & \textcolor{#ff8200}{p_{nj}} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ p_{1n} & \cdots & p_{in} & \cdots & p_{nn} \end{bmatrix}\begin{bmatrix}1 \\ \vdots \\ 1 \\ \vdots \\1\end{bmatrix}= \mathbf{e}
      这说明 e ~\mathbf{e}~是 PT ~\mathbf{P}^T~的特征向量，对应特征值 1 ~1~。
  3. 对偶性：由于 P ~\mathbf{P}~和 PT ~\mathbf{P}^T~具有相同的特征值。因此， P ~\mathbf{P}~的特征值也是 1 ~1~。

根据上一节的幂法可知，经过多次幂次运算后，系统最终趋于稳定，而这一稳定状态与矩阵的最大特征值有关。对于随机矩阵 P ~\mathbf{P}~，其最大特征值为 λ=1 ~\lambda = 1~。根据这一结论，我们通过计算随机矩阵 P ~\mathbf{P}~的稳态向量，就可以得到城市人口的长期分布情况。下面我们还是以上面的城市人口迁移模型中的矩阵 P ~\mathbf{P}~为例，来计算稳态向量：

我们要求解：
Pq=q\mathbf{P} \mathbf{q} = \mathbf{q}
即：
(P−I)q=0(\mathbf{P} - \mathbf{I})\mathbf{q} = 0
给定的矩阵：
P=[0.850.100.040.050.800.060.100.100.90]\mathbf{P} = \begin{bmatrix} 0.85 & 0.10 & 0.04 \\ 0.05 & 0.80 & 0.06 \\ 0.10 & 0.10 & 0.90 \end{bmatrix}
因此：
P−I=[0.850.100.040.050.800.060.100.100.90]−[100010001]\mathbf{P} - \mathbf{I} = \begin{bmatrix} 0.85 & 0.10 & 0.04 \\ 0.05 & 0.80 & 0.06 \\ 0.10 & 0.10 & 0.90 \end{bmatrix} - \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}
=[−0.150.100.040.05−0.200.060.100.10−0.10]= \begin{bmatrix} -0.15 & 0.10 & 0.04 \\ 0.05 & -0.20 & 0.06 \\ 0.10 & 0.10 & -0.10 \end{bmatrix}
下面我们加入概率向量的约束条件（这一步是为了确保稳态向量是一个唯一确定的概率分布。当然，这一步也可以在得到参数化解之后再进行概率归一化处理）：
x+y+z=1x + y + z = 1
增广矩阵为：
[−0.150.100.0400.05−0.200.0600.100.10−0.1001111]\left[ \begin{array}{ccc|c} -0.15 & 0.10 & 0.04 & 0 \\ 0.05 & -0.20 & 0.06 & 0 \\ 0.10 & 0.10 & -0.10 & 0 \\ 1 & 1 & 1 & 1 \end{array} \right]

通过初等行变换来化简增广矩阵。省去化简步骤，直接给出最终结果：
[1000.280100.220010.500000]\left[ \begin{array}{ccc|c} 1 & 0 & 0 & 0.28 \\ 0 & 1 & 0 & 0.22 \\ 0 & 0 & 1 & 0.50 \\ 0 & 0 & 0 & 0 \end{array} \right]
从化简后的矩阵可以看出：
x=0.28,y=0.22,z=0.50x=0.28,\quad y= 0.22,\quad z= 0.50
因此，稳态向量为：
q=[0.280.220.50]\mathbf{q} = \begin{bmatrix}0.28\\ 0.22 \\0.50\end{bmatrix}

计算得到的稳态向量 q=[0.280.220.50]T ~\mathbf{q} = \begin{bmatrix}0.28 & 0.22 & 0.50\end{bmatrix}^T~说明，最终城市 A,B,C ~A,B,C~的人口占比会稳定在 28%, 22%, 50% ~28\%,\,22\%,\,50\%~。该结果符合稳态分布的计算逻辑。

4. 正则随机矩阵与长期收敛性

我们这节研究的随机矩阵是马尔可夫链中的一类特殊的随机矩阵，称作正则随机矩阵(regular stochastic matrix)(\text{regular stochastic matrix})，它满足某个幂 Pk ~\mathbf{P}^k~的所有元素严格为正。正则随机矩阵保证了马尔可夫链无论初始状态如何，系统都会收敛 (converges) ~(\text{converges})~到一个唯一的稳态分布。这一性质可以通过以下定理来严格说明：
由于这些工具涉及更深入的线性代数和马尔可夫过程理论，定理 11 ~11~的完整证明并不是我们需要讨论的范围。

5.8 特征值的迭代估计

6.1 内积、长度和正交性

bei an浙ICP备2024102481号