06-混合时间的下界

回顾

设 不可约，平稳测度为 。定义

本讲目标

寻找混合时间的下界。主要方法与例子：

• 瓶颈比；
• 区分统计量；
• 超立方体上的随机游走。

设 是不可约转移矩阵，平稳测度为 。定义

表示初始分布为 时，链在一步内从集合 移动到集合 的概率。

定义　对 ， 的瓶颈比定义为

整条链的瓶颈比定义为

如果 很小，说明存在一个平稳质量不超过一半的集合，链从中逃出的概率很低，因此混合不可能太快。

瓶颈比

考虑图

上的简单随机游走。其转移概率和平稳分布为

设 表示一端位于 、另一端位于 的边集。则

并且

因此，图上的瓶颈比比较了集合边界的大小与集合内部总体积的大小。

瓶颈比

定理　设 是链的瓶颈比，则

引理　对任意 ，令 为 在 上的条件分布：

则

也就是说，从 内的平稳条件分布出发，一步后分布发生的全变差变化正好等于 的瓶颈比。

区分统计量

目标：寻找统计量 ，即 上的实值函数，使 在两个分布下的差异能够给出全变差距离的下界。

回顾：

引理　设 是 上的两个概率分布， 是 上的实值函数。如果

其中

则

因此，若某个统计量在两个分布下的均值差远大于其标准差，就能证明两个分布在全变差意义下仍相距较远。

超立方体上的随机游走

维超立方体是顶点集

上的图。当两个顶点恰好有一个坐标不同时，在它们之间连接一条边。

超立方体上的简单随机游走从顶点

出发，均匀选取一个坐标

并把新状态设为

惰性随机游走以概率 停留在当前位置，以概率 按上述规则移动。

它也可以用随机映射表示来构造：

1. 从

中均匀选取 ；
2. 把第 个坐标更新为 。

令

是与 同分布的独立同分布序列。每一步把 的第 个坐标更新为 。

超立方体上的随机游走

定理　对超立方体上的惰性随机游走，存在常数 ，使得

证明思路　假设惰性随机游走从

出发。定义统计量

利用上一页的区分统计量引理：若

其中

则

在时间显著小于 时，仍有许多坐标保留初始值 1，使 的均值与平稳分布下的均值保持可检测的差距。因此，链尚未混合，从而得到所述下界。