第2章：概率论与随机过程基础

2.2 马尔可夫链与随机游走

2.2.1 马尔可夫性质与定义

马尔可夫链是一种具有马尔可夫性质的离散时间随机过程，其未来状态仅依赖于当前状态，而与过去状态无关。数学定义如下：

对于离散状态空间 ( \mathcal{X} ) 和时间索引 ( t )，满足： [ P(X_{t+1} = x | X_t = x_t, X_{t-1} = x_{t-1}, ..., X_0 = x_0) = P(X_{t+1} = x | X_t = x_t) ]

转移矩阵 ( P ) 是马尔可夫链的核心，其中元素 ( P_{ij} ) 表示从状态 ( i ) 转移到状态 ( j ) 的概率： [ P_{ij} = P(X_{t+1} = j | X_t = i) \quad \text{且} \quad \sum_j P_{ij} = 1 ]

2.2.2 随机游走模型

随机游走是马尔可夫链的经典实例，分为以下两类：

  1. 简单随机游走：在整数轴上，每一步以概率 ( p ) 向右移动，以概率 ( 1-p ) 向左移动。
    • 转移概率：( P_{i,i+1} = p ), ( P_{i,i-1} = 1-p )
  2. 高维随机游走：在网格或多维空间中扩展，例如2D网格中的四方向移动。

性质分析：

  • 常返性：在无限时间内返回起始点的概率。
  • 吸收状态：一旦进入则无法离开的状态（如赌博破产问题）。

2.2.3 马尔可夫链的稳态分布

若马尔可夫链满足不可约性和非周期性，则存在唯一的稳态分布 ( \pi )： [ \pi P = \pi ] 其中 ( \pi ) 是方程的解且 ( \sum_i \pi_i = 1 )。

示例：两状态天气模型（晴/雨）的稳态分布计算： [ P = \begin{bmatrix} 0.9 & 0.1 \ 0.5 & 0.5 \end{bmatrix} ] 解得 ( \pi = [\frac{5}{6}, \frac{1}{6}] )。

2.2.4 扩散模型中的马尔可夫性

在扩散模型中，正向噪声化过程被设计为马尔可夫链： [ q(x_t | x_{t-1}) = \mathcal{N}(x_t; \sqrt{1-\beta_t}x_{t-1}, \beta_t I) ] 其中 ( \beta_t ) 是噪声调度参数。这一性质使得逆向过程可通过逐步去噪实现。

图表辅助

graph LR
    A[状态i] -- P_ij --> B[状态j]
    B -- P_jk --> C[状态k]
    style A fill:#f9f,stroke:#333
    style B fill:#bbf,stroke:#333

代码示例：简单随机游走模拟（Python）

import numpy as np
import matplotlib.pyplot as plt

def random_walk(steps=1000, p=0.5):
    positions = [0]
    for _ in range(steps):
        step = 1 if np.random.rand() < p else -1
        positions.append(positions[-1] + step)
    return positions

plt.plot(random_walk())
plt.xlabel("Time Step")
plt.ylabel("Position")
plt.title("1D Random Walk")
plt.show()

案例研究：PageRank算法

Google的PageRank算法本质上是马尔可夫链的稳态分布计算，将网页链接视为状态转移。扩散模型中的类似思想体现在噪声逐步扩散的路径设计上。

关键公式总结

  1. Chapman-Kolmogorov方程： [ P^{(n+m)}{ij} = \sum_k P^{(n)}{ik} P^{(m)}_{kj} ]
  2. 细致平衡条件（稳态充分条件）： [ \pi_i P_{ij} = \pi_j P_{ji} ]
Last Updated::