回顾
假设转移矩阵 不可约，并具有平稳测度 。定义
今天的目标
利用随机时刻给出混合时间 的上界。
- 顶牌随机插入洗牌；
- 停时与随机化停时；
- 平稳时刻与强平稳时刻。
顶牌随机插入洗牌
考虑如下洗一副 张牌的方法：
取出最上面的一张牌，再将它等概率地随机插入整副牌的任一位置。
牌的连续排列
构成对称群 上的一个随机游走。 包含这 张牌的 种可能排列，初始状态为
均匀测度是该随机游走的平稳测度。
问题： 必须洗牌多长时间，牌的排列才会服从均匀分布？
一个更简单的问题是：必须洗牌多长时间，最初位于底部的那张牌在整副牌中的位置才会服从均匀分布？
答案： 令 表示如下时刻：最初位于底部的牌第一次移动到牌堆顶部之后，再进行一次顶牌随机插入操作。则在时刻 ，牌的排列在 上服从均匀分布。
顶牌随机插入洗牌
定理. 设
是 上与顶牌随机插入洗牌相对应的随机游走。已知在时刻 ，最初位于底部的牌下面还有 张牌，则这 张牌的 种可能排列具有相同的概率。因此，
在 上服从均匀分布。
注： 随机时刻 很有意义，因为 恰好具有该链的平稳测度。
停时
定义. 给定随机变量序列
若取值于
的随机数 满足：对每个 ，事件
关于 可测，则称 是序列 的一个停时。
等价地，示性函数
是向量 的函数。
例. 固定一个子集 ，定义 首次到达 的时刻为
则 是停时。回顾一下， 和 也都是停时；其中 表示时刻 之后首次到达 的时刻。
停时
引理. 设 是一个随机时刻，则下列四个条件等价：
- 关于 可测；
- 关于 可测；
- 关于 可测；
- 关于 可测。
引理. 若 和 都是停时，则
也都是停时。
随机映射表示
定义. 设 是状态空间 上的转移矩阵。 的一个随机映射表示，由一个函数
以及一个取值于 的随机变量 组成，并满足
问题： 随机映射表示与马尔可夫链有什么关系？
设
是一列独立同分布的随机变量，其共同分布与 相同。设
并对 定义
则 是一条初始分布为 、转移矩阵为 的马尔可夫链。
例：-循环上的简单随机游走。 令
并令 独立同分布，每个 以相同概率取 和 。定义
这就给出了 -循环上简单随机游走的随机映射表示。
随机映射表示
定义. 设 是状态空间 上的转移矩阵。 的一个随机映射表示，是一个函数
与一个取值于 的随机变量 ，它们满足
定理. 有限状态空间上的每一个转移矩阵都具有随机映射表示。
随机化停时
假设转移矩阵 具有一个随机映射表示：存在
和随机变量 ，使得
令 是一列与 同分布的独立同分布随机变量。对 ，定义
则 是一条转移矩阵为 的马尔可夫链。
定义. 如果随机时刻 是序列 的一个停时，则称 是一个随机化停时。
注. 序列 所含的信息多于序列 所含的信息。因此， 的每个停时都是随机化停时；反过来一般并不成立。
平稳时刻与强平稳时刻
定义. 设 是一条不可约马尔可夫链，其平稳测度为 。
若随机化停时 满足
即
则称 是 的一个平稳时刻。
若随机化停时 不仅满足
而且 与 相互独立，即
则称 是 的一个强平稳时刻。
例. 对顶牌随机插入洗牌而言，时刻 是一个强平稳时刻。
强平稳时刻
例. 设 是状态空间 上的一条不可约马尔可夫链，平稳测度为 ，且
令 是一个取值于 的随机变量，其分布为 ，并且与 独立。定义
那么：
- 不是序列 的停时；
- 是随机化停时；
- 是平稳时刻；
- 不是强平稳时刻。
强平稳时刻
定理. 设 是一条不可约马尔可夫链，平稳测度为 。若 是 的一个强平稳时刻，则
引理. 对所有 ，
引理. 定义从状态 出发的分离距离
则
引理. 对所有 与 ，
麻省理工学院开放式课程
