04-Markov 链混合导论

• 期中考试：4 月 6 日，上课时间进行；

考试均为闭卷，不得携带笔记，也不得使用计算器。

回顾

若 是具有平稳分布 的不可约 Markov 链，则

本讲目标

证明 在某种更强的意义下收敛到 ，并介绍：

• 全变差距离；
• 收敛定理；
• 混合时间。

全变差距离的三种刻画

设 是 上的概率测度。

引理

定义　若耦合 满足

则称其为最优耦合。

收敛定理

设 是转移矩阵为 的 Markov 链。若 不可约且非周期，则：

• 存在整数 ，使得对所有 ，

• 存在唯一的平稳分布 ，并且对所有 ，

定理　假设 不可约、非周期，平稳分布为 。则存在常数

使得对所有 ，

因此，链从任意初始状态出发，其第 步分布都以指数速度趋向平稳分布。

混合时间

定义

引理

引理

推论

混合时间

定义

引理

核心问题：Markov 链需要多长时间才能接近平稳测度？

• 第 5 讲： 的上界；
• 第 6 讲： 的下界；
• 第 7 讲：有趣的模型。

两条 Markov 链的耦合

定义　转移矩阵为 的两条 Markov 链的一个耦合，是过程

满足：

1. 与 都是转移矩阵为 的 Markov 链；
2. 两条链首次相遇以后，始终保持在一起。

记号　若 、 是耦合的 Markov 链，并且

则用

表示联合过程 的分布。

两条 Markov 链的耦合

定理　设 不可约，平稳分布为 。令

是转移矩阵为 的 Markov 链耦合，且

定义它们的首次相遇时刻

则

特别地，

因此，只要能构造两条链快速相遇的耦合，就能得到混合速度的上界。

阶环上随机游走的混合时间上界

考虑 阶环上的惰性随机游走：

• 以概率 停留在当前位置；
• 以概率 向左移动一步；
• 以概率 向右移动一步。

该链不可约，其平稳测度是顶点集上的均匀测度。

定理　对 阶环上的惰性随机游走，