07-混合时间总结

回顾

假设转移矩阵 不可约，并具有平稳测度 。定义

今天的目标

总结关于混合时间的已有结果：

• 混合时间的上界与下界；
• 赌徒破产问题与优惠券收集问题；
• 超立方体上的随机游走；
• -循环上的随机游走；
• 顶牌随机插入洗牌。

上界

假设转移矩阵 不可约，并具有平稳分布 。

定理（两条马尔可夫链的耦合）. 设

是两条转移矩阵均为 的马尔可夫链的一个耦合，并且

定义它们的首次相遇时刻

则

从而

定理（强平稳时刻）. 设 是一条转移矩阵为 的马尔可夫链。若 是 的一个强平稳时刻，则

下界

假设转移矩阵 不可约，并具有平稳测度 。

定理（瓶颈比）. 定义

该链的瓶颈比定义为

则

定理（区分统计量）. 设 和 是状态空间 上的两个概率分布， 是 上的实值函数。若

其中

则

赌徒破产问题

考虑一个赌徒对一列独立且公平的抛硬币结果下注。

• 如果硬币正面朝上，他赢得 1 美元；
• 如果硬币反面朝上，他损失 1 美元；
• 如果他的财富达到 美元，他便停止；
• 如果他的钱包变空，他也停止。

赌徒的处境可以用状态空间

上的一条马尔可夫链来建模：

• ：钱包中的初始金额；
• ：赌徒在时刻 的财富；
• ：赌徒停止赌博的时刻。

定理. 假设

则

优惠券收集问题

一家公司发行 种不同的优惠券。一位收集者希望集齐一整套。收集者的情况可以用状态空间

上的一条马尔可夫链来建模：

而 表示收集者拿到的前 张优惠券中，不同种类的数目。

当 时，

令 表示收集者第一次集齐全部 种优惠券的时刻。

定理.

对任意 ，都有

超立方体上的随机游走

超立方体上的懒随机游走可以通过如下随机映射表示来构造：

从

中均匀选取一个元素 ，然后用 更新第 个坐标。

令

为独立同分布序列，每个 都服从 的上述均匀分布。在第 步，用 更新 的第 个坐标。定义

这是所有坐标都至少被选中并更新过一次的最早时刻。

定理. 存在常数

使得

证明思路：

• 上界：使用强平稳时刻；
• 下界：使用区分统计量。

-循环上的随机游走

考虑如下懒随机游走：

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

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

定理. 对 -循环上的懒随机游走，存在常数 ，使得

证明思路：

• 上界：使用两条马尔可夫链的耦合；
• 下界：使用相应的下界方法。

顶牌随机插入洗牌

考虑如下洗一副 张牌的方法：

取出最上面的一张牌，再将它等概率地随机插入整副牌的任一位置。

牌的连续排列

构成对称群 上的一条随机游走，初始状态为

均匀测度是该随机游走的平稳测度。

令 表示如下时刻：最初位于底部的牌第一次移动到牌堆顶部之后，再进行一次顶牌随机插入操作。在时刻 ，牌的排列在 上服从均匀分布。

定理. 存在常数

使得

证明思路：

• 上界： 是强平稳时刻；
• 下界：使用相应的下界方法。

麻省理工学院开放式课程