马尔可夫链混合时间理论

概述

马尔可夫链混合时间（Mixing Time）理论研究随机过程从任意初始分布收敛到平稳分布的速度¹²。这在蒙特卡洛方法、随机算法和统计物理中有重要应用。

核心问题：从初始分布 ${\pi }_0$ 开始，经过多少步后，分布 ${\pi }_t$ 接近平稳分布 $\pi$？

---

1. 混合时间定义

1.1 总变差距离

总变差距离（Total Variation Distance）：

$$d_{TV}(P,Q)=\frac{1}{2}\Vert P-Q{\Vert }_1=\frac{1}{2}\sum _x|P(x)-Q(x)|$$

等价于：

$$d_{TV}(P,Q)=\underset{A\subseteq \mathcal{X}}{\max }|P(A)-Q(A)|$$

1.2 ${\ell }_{\infty }$ 距离

${\ell }_{\infty }$ 距离：

$$d_{\infty }(P,Q)=\underset{x}{\max }|P(x)-Q(x)|$$

注意：$d_{\infty }\ge d_{TV}$，且 $d_{\infty }\le 1$。

1.3 混合时间定义

$ϵ$-混合时间：

$$t_{mix}(ϵ)=\min \{t:d_{TV}(P^t(\cdot ,x),\pi )\le ϵ,\forall x\}$$

简写为 $t_{mix}$ 表示 $t_{mix}(1/4)$。

1.4 收敛因子

几何收敛：

如果存在 $\rho <1$ 使得：

$$d_{TV}(P^t,\pi )\le C{\rho }^t$$

则混合时间为 $O(\log (1/ϵ))$。

---

2. 谱分析

2.1 转移矩阵的特征值

对于离散时间马尔可夫链，转移矩阵 $P$ 有以下性质：

1. ${\lambda }_1=1$ 是最大特征值
2. 其余特征值 $|{\lambda }_i|\le 1$
3. 特征向量与平稳分布正交

2.2 谱隙定义

谱隙（Spectral Gap）：

$$\gamma =1-{\lambda }_2$$

其中 ${\lambda }_2$ 是第二大的特征值（排除1）。

绝对谱隙：

$${\gamma }^{\ast }=1-\underset{i\ge 2}{\max }|{\lambda }_i|$$

2.3 谱隙与混合时间的关系

上界（由特征值分解）：

$$d_{TV}(P^t,\pi )\le \frac{1}{2}\Vert P^t(x,\cdot )-\pi {\Vert }_2\le \frac{1}{2}\sqrt{\frac{\pi (x)}{{\pi }_{\min }}}(1-\gamma {)}^t$$

下界：

$$d_{TV}(P^t,\pi )\ge \frac{1}{2}(1-{\lambda }_2{)}^t$$

2.4 典型收敛速率

谱隙	混合时间 $t_{mix}(ϵ)$
$\gamma =O(1)$	$O(\log (1/ϵ))$
$\gamma =O(1/n)$	$O(n\log (1/ϵ))$
$\gamma =O(1/n^2)$	$O(n^2\log (1/ϵ))$

---

3. 耦合方法

3.1 耦合的定义

耦合：在两个马尔可夫链上定义联合转移，使得边缘分布保持不变。

设 $(X_t,Y_t)$ 是耦合过程，满足：

• $X_t\sim P^t(x_0,\cdot )$（从 $x_0$ 开始的链）
• $Y_t\sim \pi (\cdot )$（平稳链）
• 如果 $X_t=Y_t$，则之后保持相等

3.2 混合时间的耦合界

关键不等式：

$$d_{TV}(P^t(x,\cdot ),\pi )\le P(X_t\ne Y_t)$$

因此，我们只需要估计相遇时间（meeting time）。

3.3 例子：随机游走

import numpy as np
 
def random_walk_mixing(n_states=100, n_steps=1000, n_trials=1000):
    """
    随机游走的混合时间估计
    状态空间: {0, 1, ..., n_states-1}
    转移: 以概率1/2移动到相邻状态
    """
    # 构建转移矩阵
    P = np.zeros((n_states, n_states))
    for i in range(n_states):
        if i == 0:
            P[i, [0, 1]] = [0.5, 0.5]
        elif i == n_states - 1:
            P[i, [n_states-2, n_states-1]] = [0.5, 0.5]
        else:
            P[i, [i-1, i+1]] = [0.5, 0.5]
    
    # 平稳分布（均匀）
    pi = np.ones(n_states) / n_states
    
    # 从状态0开始
    initial_state = 0
    
    # 估计TV距离
    tv_distances = []
    for trial in range(n_trials):
        state = initial_state
        tv_trial = []
        
        for t in range(n_steps):
            # 计算当前分布
            # （简化：用频率近似）
            tv_trial.append(0.0)  # 简化
        
        tv_distances.append(tv_trial)
    
    return np.array(tv_distances)

3.4 Doeblin耦合

Doeblin条件（弱Doeblin条件）：

存在 $ϵ>0$ 和分布 $\nu$ 使得：

$$P(x,\cdot )\ge ϵ\nu (\cdot ),\forall x$$

混合时间界：

$$d_{TV}(P^t(x,\cdot ),\pi )\le (1-ϵ{)}^t$$

---

4. 路径耦合

4.1 基本思想

路径耦合通过考虑状态空间中”路径上”的相邻状态来简化分析。

设 $X_t$ 和 $Y_t$ 是两个链，定义耦合时间 $T=\min \{t:X_t=Y_t\}$。

4.2 收缩映射

如果存在 $\beta <1$ 使得：

$$\mathbb{E}[d(X_{t+1},Y_{t+1})|X_t,Y_t]\le \beta \cdot d(X_t,Y_t)$$

则：

$$\mathbb{E}[T]\le \frac{\log (d_{\max }/\delta )}{1-\beta }$$

其中 $d_{\max }$ 是最大距离，$\delta$ 是初始距离。

---

5. 典型例子分析

5.1 伯努利-卢球（Bernoulli-Laplace）模型

模型：$n$ 个球，$m$ 个盒子，每个盒子一个球。

转移：随机选择一个空盒和一个有球的盒，交换球。

谱隙：

$$\gamma =\frac{1}{n}+O\left(\frac{1}{n^2}\right)$$

混合时间：

$$t_{mix}=\Theta (n\log m)$$

5.2 伊辛模型（Ising Model）

模型：图上的自旋系统，每个节点 ${\sigma }_i\in \{-1,+1\}$。

能量函数：

$$H(\sigma )=-\sum _{(i,j)}{J}_{ij}{\sigma }_i{\sigma }_j-h\sum _i{\sigma }_i$$

转移：Metropolis-Hastings或Gibbs采样。

谱隙估计：

温度	谱隙	混合时间
高温 $T>T_c$	$\Theta (1)$	$O(\log n)$
临界温度 $T=T_c$	$\Theta (1/n)$	$O(n\log n)$
低温 $T<T_c$	指数小	指数时间

5.3 随机游走与-card距离

对于无向图上的简单随机游走：

Card距离（到最近邻居的比例）：

$$\gamma \ge \frac{1}{2d_{\max }}$$

其中 $d_{\max }$ 是最大度数。

---

6. 连续时间马尔可夫链

6.1 生成元算子

对于连续时间链，生成元（Generator）$Q$ 满足：

$$P(t)=e^{Qt}$$

6.2 谱隙

连续时间谱隙：

$$\gamma (Q)=-{\lambda }_{\min }(Q)$$

其中 ${\lambda }_{\min }$ 是 $Q$ 的最小非零特征值。

6.3 混合时间

$$t_{mix}^{CT}(ϵ)\le \frac{1}{\gamma }\log \left(\frac{1}{ϵ{\pi }_{\min }}\right)$$

---

7. 加速混合技术

7.1 状态空间膨胀

膨胀（Lumping）：合并等价状态类。

如果存在分区 $\mathcal{P}$ 满足：

• $x,y$ 同一类 $\Rightarrow P(x,C)=P(y,C),\forall C\in \mathcal{P}$

则膨胀后的链有更快的混合。

7.2 耦合来自过去（CPF）

CPF算法：

def coupling_from_the_past(P, n_states):
    """
    耦合来自过去算法
    检测链是否混合
    """
    # 初始化
    X = np.arange(n_states)  # 每行一个链
    time = 0
    
    while True:
        time += 1
        # 随机选择过去时间
        t = np.random.randint(1, time + 1)
        
        # 应用转移
        for i in range(n_states):
            X[i] = np.random.choice(n_states, p=P[X[i]])
        
        # 检查是否相遇
        if len(set(X)) == 1:
            return time  # 找到了混合时间

7.3 平稳分布交换

平稳交换（Stationary Exchange）：

利用结构化状态空间设计更好的耦合。

---

8. 数值计算

8.1 特征值计算

import numpy as np
 
def compute_mixing_time(P, pi, epsilon=0.01):
    """
    计算马尔可夫链的混合时间
    
    参数:
        P: 转移矩阵 [n, n]
        pi: 平稳分布 [n]
        epsilon: 目标误差
    
    返回:
        t_mix: 混合时间
    """
    n = P.shape[0]
    
    # 计算特征值
    eigenvalues, eigenvectors = np.linalg.eig(P.T)  # 转置因为我们想要行随机
    
    # 排序特征值
    idx = np.argsort(np.abs(eigenvalues))[::-1]
    eigenvalues = eigenvalues[idx]
    
    # 谱隙
    gamma = 1 - np.abs(eigenvalues[1])
    
    # 估计混合时间
    C = np.max(np.sqrt(pi / np.min(pi[np.abs(pi) > 1e-10])))
    t_mix = np.log(2 * C / epsilon) / (1 - np.abs(eigenvalues[1]))
    
    return t_mix, eigenvalues[:5]

8.2 蒙特卡洛估计

def monte_carlo_mixing_time(P, initial_state, pi_true, n_steps=10000, n_trials=100):
    """
    蒙特卡洛估计混合时间
    """
    n_states = P.shape[0]
    
    # TV距离估计
    tv_estimates = []
    
    for trial in range(n_trials):
        # 从初始状态开始
        state = initial_state
        state_counts = np.zeros(n_states)
        
        for t in range(n_steps):
            state = np.random.choice(n_states, p=P[state])
            state_counts[state] += 1
        
        # 估计分布
        p_estimate = state_counts / n_steps
        
        # TV距离
        tv = 0.5 * np.sum(np.abs(p_estimate - pi_true))
        tv_estimates.append(tv)
    
    return np.mean(tv_estimates), np.std(tv_estimates)

---

9. 与其他收敛度量的关系

9.1 自适应与均匀

度量	定义	关系
均匀混合	$\Delta (t)={\max }_x{d}_{TV}(P^t(x),\pi )$	最强
自适应混合	$\delta (t)={\max }_x{d}_{TV}(P^t(x),\pi )$	等价
局部混合	$\ell (t)={\max }_{(x,y)}{d}_{TV}(P^t(x),P^t(y))$	$\le 2\Delta (t)$

9.2 ${\chi }^2$ 距离

$${\chi }^2(P,\pi )=\sum _x\frac{(P(x)-\pi (x){)}^2}{\pi (x)}$$

关系：

$$d_{TV}(P,\pi )\le \frac{1}{2}\sqrt{{\chi }^2(P,\pi )}$$

---

10. 总结

核心概念

1. 总变差距离：度量分布差异的标准工具
2. 谱隙：决定几何收敛速率
3. 耦合：证明收敛界的构造性方法
4. Doeblin条件：保证快速混合的充分条件

实用指南

问题类型	推荐方法
对称链	谱分析
一般链	耦合方法
高温系统	Doeblin条件
复杂结构	路径耦合

与MCMC的关系

• 混合时间 $\approx$ 有效样本量
• 谱隙小 $\Rightarrow$ 样本自相关时间长
• 加速混合 $\iff$ 提高MCMC效率

---

参考资料

---

相关主题

• markov-chain — 马尔可夫链基础
• mcmc-methods — 马尔可夫链蒙特卡洛方法
• continuous-time-markov-processes — 连续时间马尔可夫过程
• hamiltonian-monte-carlo-geometric-theory — HMC几何理论

Footnotes

1. Levin, D. A., Peres, Y., & Wilmer, E. L. (2008). “Markov Chains and Mixing Times.” American Mathematical Society. ↩

2. Montenegro, R., & Tetali, P. (2006). “Mathematical Aspects of Mixing Times in Markov Chains.” Foundations and Trends in Theoretical Computer Science. ↩