习题

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

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

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

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

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

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

图上随机游走

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

耦合

.

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

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

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

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

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

• 对任意 以及任意 ,

• 若 , 则

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