混合时间

形式陈述 ​

设 $P$ 是有限状态 Markov 链的转移矩阵，$\pi$ 是一个指定的平稳分布。从状态 $x$ 出发，$t$ 步后的分布为 $P^t(x,\cdot )$。定义相对于 $\pi$ 的最坏初态总变差距离

$$d(t)=\underset{x}{max}{\Vert P^t(x,\cdot )-\pi \Vert }_{\mathrm{TV}},$$

以及精度 $\epsilon \in (0,1)$ 下的混合时间

$$t_{\mathrm{mix}}(\epsilon )=min\{t\ge 0:d(t)\le \epsilon \}.$$

若集合为空，就约定 $t_{\mathrm{mix}}(\epsilon )=\mathrm{\infty }$。不可约且非周期的有限链具有唯一平稳分布，并从任意初态收敛到它，因此这是保证混合时间有限的标准条件；不满足这些条件的链仍可代入定义，但结果可能为无穷。本文把

$$t_{\mathrm{mix}}=t_{\mathrm{mix}}(1/4)$$

作为默认约定。对标准遍历链，任何固定 $\epsilon \in (0,1/2)$ 得到的时间尺度仅相差由阈值决定的常数或对数因子，但具体数值仍依赖约定。若从初始分布 $\mu$ 出发，则相应距离是 $\Vert \mu P^t-\pi {\Vert }_{\mathrm{TV}}$；最坏初态定义保证对所有 $\mu$ 同时成立。

直觉 ​

混合不是链在某一刻“到达”平稳分布。有限步后，$P^t(x,\cdot )$ 往往仍与 $\pi$ 不完全相等；混合时间问的是它们何时已经近到任何事件测试都难以区分，而且这个保证必须覆盖最不利的起点。

转移每执行一步都会遗忘一部分初态信息。若不同起点产生的分布逐渐靠拢，平稳分布便成为共同参照。障碍也由此清楚：多个闭沟通类会永久保留“起点在哪一类”的信息；周期链会保留时间相位；很窄的瓶颈则让概率质量跨区域移动得很慢。

例子与边界 ​

二状态链

$$P=\left(\begin{array}{cc}1-a& a\\ b& 1-b\end{array}\right),0<a,b<1,$$

具有平稳分布 $\pi =(b/(a+b),a/(a+b))$。其非平凡特征值为 $1-a-b$，从任一初态到平稳分布的差按 $|1-a-b{|}^t$ 衰减；当 $a+b$ 很小时，链长时间停留原状态，混合变慢。

确定交替的两状态链具有平稳分布 $(1/2,1/2)$，却从状态 $0$ 出发在奇偶时刻来回跳动，总变差距离不趋于零。加入以 $1/2$ 概率原地停留的 lazy 版本可消除周期，但这产生新转移矩阵，混合步数也应按新链计算。时间平均趋向平稳分布并不能替代逐时刻边缘分布的混合。

推论与应用 ​

总变差距离公理库总变差距离Total variation distance · TV distance两个概率分布对最优可测事件所赋概率之差的最大值。固定了“接近”的意义；不可约性公理库沟通类与不可约性Communication classes · Irreducible Markov chain按正概率多步可达性分解 Markov 链状态空间，并刻画整个链是否互相可达。与非周期性公理库常返、暂留与周期性Recurrence and transience · Periodicity of Markov chains用返回概率、返回时间与可返回步数刻画 Markov 链状态的长期类型。排除结构性障碍。可逆链公理库可逆链与细致平衡Reversible Markov chain · Detailed balance由相反方向概率流逐边平衡所刻画的 Markov 链时间反演对称性。还能借助谱隙、conductance 等工具给出混合上界，而耦合法公理库耦合法Coupling method · Probability coupling在共同概率空间中构造具有指定边缘的随机变量，并用它们相遇的概率比较分布。通过两条链的相遇概率直接控制 $d(t)$。

在 MCMC 中，混合时间决定需要丢弃多少初始步骤以及有限运行带来多大偏差。它是最坏情形分布保证，不等同于某个观测量看似稳定，也不能由一条模拟轨迹的视觉平稳性替代。

参考资料

• David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov Chains and Mixing Times, 2nd ed., American Mathematical Society, 2017，Ch. 4, total variation and mixing time。
• J. R. Norris, Markov Chains, Cambridge University Press, 1997，convergence to equilibrium for discrete-time chains。