01-有限 Markov 链导论

本课程介绍：

• Markov 链；
• 随机游走；
• 鞅。

David A. Levin、Yuval Peres、Elizabeth L. Wilmer：

Markov Chains and Mixing Times（《Markov 链与混合时间》）。

• 2 月 23 日；
• 3 月 9 日；
• 4 月 6 日；
• 4 月 22 日；
• 5 月 4 日。

鼓励同学相互讨论作业，但每个人都必须独立撰写并提交自己的解答。

考试

本讲目标

1. 基本定义；
2. 赌徒破产问题；
3. 集齐优惠券问题；
4. 平稳分布。

设：

• ：有限状态空间；
• ：大小为 的转移矩阵。

定义　随机变量序列

称为状态空间为 、转移矩阵为 的 Markov 链，如果对所有 和所有状态序列

都有

也就是说，在已知当前状态以后，下一步的条件分布不再依赖更早的历史。

赌徒破产问题

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

• 如果出现正面，他赢得 1 美元；
• 如果出现反面，他损失 1 美元；
• 如果他的财富达到 美元，就停止赌博；
• 如果他的钱全部输光，也停止赌博。

问题：

1. 两种最终结果各自发生的概率是多少？
2. 赌徒到达这两个终止状态之一需要多长时间？

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

上的 Markov 链表示。

• ：赌徒的初始资金；
• ：赌徒在时刻 的财富；
• 对 ，

状态 和 都是吸收态。

令

表示赌徒停止的时刻。

定理　假设

则

并且

集齐优惠券问题

一家公司发行 种不同类型的优惠券。某位收集者希望集齐全部 种。

问题：收集者需要获得多少张优惠券，才能使自己的收藏中包含全部 种？

假设：每一张优惠券都以相同概率属于这 种类型中的任意一种。

收集者的情况可以用状态空间

上的 Markov 链表示。

• ；
• ：前 张优惠券中已经出现的不同类型数。

当 时，

因为下一张优惠券必须属于尚未收集的 种类型之一；同时

令

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

问题的答案

定理

更精确的答案

定理　对任意 ，

因此，集齐全部类型所需的优惠券数高度集中在 附近；再增加 张仍未集齐的概率至多为 。

记号

• ：状态空间；
• ： 上的测度；
• ：大小为 的转移矩阵；
• ： 上的函数。

定义：

• ： 上的测度，

• ：转移矩阵，

• ： 上的函数，

这些运算满足结合律：

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

回顾：

记：

• ： 的分布；
• ： 的分布。

则

从而

对于状态空间上的函数 ，

平稳分布

继续考虑状态空间为 、转移矩阵为 的 Markov 链。

记 和 分别为 与 的分布。

定义　若概率测度 满足

则称 是 的一个平稳分布。

如果 是平稳分布，并且初始分布

那么对所有 ，

图上的随机游走

定义　图

由顶点集 和边集 组成：

• ：顶点组成的集合；
• ：顶点对组成的集合。

当

时，记作

表示 与 之间有一条边。此时称 是 的邻居。

对 ，记

为 的邻居数，即 的度数。

定义　给定图 ，其上的简单随机游走是状态空间为 、转移矩阵为

的 Markov 链。

再次给出图 上简单随机游走的定义：

定义

定理　 是图 上简单随机游走的一个平稳分布。

事实上，