基本概念

简单回顾随机过程, 是一个随机变量集合 , 这 一般指时间, 因而是可列的, 以表明这是一序列. 我们关注离散时间离散空间随机过程 即 , 这里离散空间指的是对任意 , 仅从一有穷集 取值 ( 也可以是可列无穷集). 而 Markov 性质是所谓无后效性或者无记忆性: 仅依赖于 , 即 , 此时 称为有穷 Markov 链, 可简称为 Markov 链, 或者链.

鉴于 的有穷离散特点, 随 变化可看作是状态的不断转移, 这里状态指 中的元素, 为了方便, 我们用 表示从 到 的转移概率, 这里我们只关注时间其次的 Markov 链, 即认为 转移概率 与时间 无关. 将所有 写成矩阵的形式, 我们就得到了一个行随机矩阵 (若 有限), 因为它满足 , 这是所谓转移矩阵. 设 是 的分布, 根据全概率公式以及矩阵乘法, 很容易有 , 进而通过归纳有 , 是所谓 Chapman-Kolmogorov 方程. Chapman-Kolmogorov 方程指出我们可以通过链的初始状态 和转移矩阵计算出任意一时刻的状态. 这里可以看出 和 是一个 Markov 链的核心特征, 我们可以使用 表示一 Markov 链, 至于初始分布 , 我们在后面可以看到它并不重要.

由于时间其次性, 我们很容易用一个带边权的有向图 表示这个 Markov 链, 其中每个状态表示一个顶点, , 且 当且仅当 , 行随机矩阵的性质保证了每个顶点发出的边的边权和为 1. 这有向图 称为 的转移图, 事实上就是 的邻接矩阵, 当然是带权的.

状态分类

我们希望知道在一个长期的时间内, Markov 链的性质和状态会发生什么样的变化, 于是我们首先要对状态进行分类, 这等价于分析转移图 的连通结构.

对任意两个状态 , 如果存在 到 的有向路径, 则称状态 到状态 是可达的, 若 相互可达, 则称他们是互通的, 此时我们得到了一个等价关系. 强连通图的任意两点之间都存在有向路径, 因此若 的转移图 是强连通的, 则所有状态彼此互通, 此时我们称链 不可约 (irreducible).

状态 具有周期 , 如果转移图 中所有包含 的回路都能被 整除, 且 是满足该性质的最大整数, 记 . 周期为 的状态称为非周期 (aperiodic) 的. 若链 所有状态都非周期, 则称 非周期.

从 出发, 随着 的变化, 每个时刻取到的状态 (当取到状态 时, 我们称链 访问 ) 依然有可能是 , 我们称 是常返的, 若能以 的概率再次访问 , 否则称为非常返的或瞬时的. 若链 中每个状态都是常返的, 则称 是常返的. 那从 出发, 再次访问到 的事件是一个随机变量, 若这个随机变量的期望有穷, 称 是正常返的, 否则是零常返的. 若 非周期且正常返, 则称 是遍历的. 若链 所有的状态都是周期的, 则称链是遍历的.

Lemma 1 任一有穷的, 不可约的, 非周期的 Markov 链是遍历的.

我们没有给无穷的 Markov 链的遍历性一个保证, 对于无穷马尔可夫链而言，就连对于不可约的链, 常返性质都不再是天经地义的。例如一个有趣的现象：对于 维方格 上的均匀随机游走（每步等概率地走到一个随机相邻格点），当维度 时所有点都是常返的，维度 时所有点都不是常返的。这一现象也被形象地称为“醉汉易归家，醉鸟难返巢”（“Adrunk man will find his way home, but a drunk bird may get lost forever.”——Shizuo Kakutani 角谷静夫）

平稳分布

随着时间的推移, 会怎么变化呢? 我们希望探究分布的收敛性. 如果某个分布 满足 , 那意味着, 从 出发, 的分布将始终不变, 因此称这样的 为平稳分布. 什么样的 具有平稳分布呢? 根据 Perron-Frobenius 定理, 设 , 则一定有谱半径 是 的一个特征值, 并存在一个非负的左或右特征向量; 若 不可约, 则 的重数为 且存在一个正的左或右特征向量; 若 是行随机或列随机的, 则 . 当链 有穷时, 设 , 则 的谱半径 且存在关于 的非负左特征向量, 即存在 满足 , 那么可构造平稳分布为 . 这意味着任何有穷 Markov 链都存在平稳分布.

混合时间 (Mixing Time) 与耦合 (Coupling)

Mixing Time 是为了研究 Markov 链的收敛速率提出的概念. 令 表示初始状态为 在 时刻为 的概率, 表示初始状态为 在 时刻的分布与平稳分布之间的 total variance distance, 定义为 , 用来衡量两个分布的距离. 那么定义 实际上就是在初始条件为 时刻 时的分布与平稳分布的距离不超过 的 的最小值, 在 取遍 时的最大值(从最坏的初始状态出发). 或 , 只需要是一个小于 的数即可. 当 时, 称链快速混合.

上的联合分布 被称为 和 的耦合, 如果 是 的边缘分布, 即 , 以及 . 两个分布的耦合不唯一.

耦合引理: 设 是 上的两个分布, 则

1. 对任意 的耦合 ,
2. 存在一个 的耦合 使得 . 即上述不等式是紧的.

Markov 链 的一个耦合是一个状态空间为 的 Markov 链, 满足

• 对任意 以及任意 ,

• 若 , 则

在上述定义的基础上, 若对 有 对任意 都成立, 则 的混合时间有上界 .

例题

考虑下述的 上的 Markov 链: 在每一轮, 根据下面的规则更新 :

• 选择 .
• 对每个 , 更新 . 实际上是以 的概率对 取反.

证明该链不可约, 具有非周期性和平稳分布, 且快速混合.

Proof. 不可约性的证明:上述规则实际上是以大于 的概率对 任选 位取反. 因此对任意 , 设 有 位不同, 则至少 次取反操作即轮数就可以将 变成 . 因此任意两个状态之间都是互通的, 这就证得了不可约性.

非周期的证明: 对任意 , 注意到 即 有 的概率保持不变, 这说明对所有 都有 , 也就证得了非周期性.

平稳分布: 注意到 和 可以通过完全相同的操作变成对方, 因此 , 因此转移矩阵 是对称阵, 因此也是列随机矩阵, 于是 , 这意味着 上的均匀分布是该 Markov 链的平稳分布.

快速混合: 从任意状态 出发, 若在 时刻 相比 的每一个比特都被更新过以及 相比 的每一个比特都被更新过, 则一定存在 , 使得 . 将每轮抽 个比特等价表述为每次抽 个比特, 抽 次, 设 表示轮数, 表示次数, 显然 . 这样就是先在 上均匀采样 , 以 的概率更新 . 设 表示有 个比特被更新后开始, 到第 个比特被更新时需要抽取的比特的次数, 则 . 注意到 服从几何分布 , 且 即剩余 个比特中, 任意一个被更新的概率, 因此 , 于是 其中 是调和级数的前 项和. 由 Markov 不等式得

因此对 , 有 则混合时间有上界 , 于是 .

习题

1: 使用 Perron-Frobenius 定理验证任何有穷马尔可夫链都存在平稳分布.

Proof. 平稳分布的定义是 上的概率分布 满足 , 其中 为行随机矩阵. 当马尔可夫链有穷时, 设 , 则 的谱半径 且存在关于 的非负左特征向量, 即存在 满足 , 那么可构造平稳分布为 .

2: 如果状态 和 是互通的, 则 .

Proof. 互通, 则 互相可达即互相存在一条到对方的有向路径, 这意味着存在一个回路 , 包含 , 这意味着所有包含 的回路都包含 , 也就是 .

3: 对于一个可逆的马尔可夫链 , 如果初始状态 的分布 满足细致平稳方程, 则对任意 , 随机向量 与 同分布.

Proof. 的分布为 , 满足细致平稳方程意味着 是 的平稳分布, 则 的分布都为 .

图上随机游走

马尔可夫链就是随机游走.