03-Markov 链的时间反演

回顾

考虑状态空间为 、转移矩阵为 的 Markov 链：

如果概率测度 满足

则称 是平稳分布。

如果 不可约，则存在唯一的平稳分布。

本讲目标

• 遍历定理；
• Markov 链的时间反演；
• 生灭链；
• 全变差距离。

定理　设 是定义在 上的实值函数。如果

是具有平稳分布 的不可约 Markov 链，则对任意初始分布 ，

这里

特别地，取

得到

也就是说，链长期停留在状态 的时间比例等于其平稳概率 。

细致平衡方程

定义　假设 上的概率测度 满足

这些等式称为细致平衡方程。

引理　任何满足细致平衡方程的概率分布 都是 的平稳分布。

事实上，

定义　满足细致平衡方程的 Markov 链称为可逆链。

图上的简单随机游走

例　考虑连通图

上的简单随机游走。概率测度

满足细致平衡方程。

事实上，若 ，则

若 ，等式两边均为 0。因此，图上的简单随机游走是可逆的。

Markov 链的时间反演

定理　设 是转移矩阵为 、平稳分布为 的不可约 Markov 链。定义

则：

1. 是随机矩阵；
2. 若 是转移矩阵为 的 Markov 链，则 也是 的平稳分布；
3. 对任意 ，

称 是 的时间反演。

注　如果转移矩阵为 的链可逆，则

并且 与 具有相同的分布。

生灭链

生灭链的状态空间为

可以把当前状态理解为某个种群的规模。链每一步至多发生一次出生或一次死亡。

转移概率由

给出，并且对每个 ，

其中：

• 对 ， 是从 转移到 的概率，并规定

• 对 ， 是从 转移到 的概率，并规定

• 对 ， 是停留在状态 的概率。

定理　每条生灭链都是可逆的。

全变差距离

定义　 上两个概率测度 之间的全变差距离定义为

引理　全变差距离满足三角不等式：

全变差距离的三种刻画

引理

引理

这里

全变差距离的三种刻画

定义　概率测度 的一个耦合，是定义在同一概率空间上的一对随机变量 ，满足：

• 的边缘分布为 ；
• 的边缘分布为 。

引理

定义　如果耦合 满足

则称 是一个最优耦合。

第一次作业的截止日期为 2 月 23 日。