回顾电势 是 上的调和函数。与电势 相联系的电流 定义为 有效电阻定义为 与逃逸概率的关系 今天的目标 用于简化网络的三种操作； 有效电阻与流的能量； 纳什—威廉姆斯不等式。 简化网络的三种操作下面介绍三种简化网络、同时不改变

回顾：可逆 Markov 链如果存在概率测度 ，使得对所有 ， 则该 Markov 链可逆。 此时： 是平稳分布； 对任意 ， 本讲目标：电网络 网络、电导与电阻； 电压与电流； 有效电阻。 定义　网络是一个有限、无向、连通图

回顾假设转移矩阵 不可约，并具有平稳测度 。定义 今天的目标总结关于混合时间的已有结果： 混合时间的上界与下界； 赌徒破产问题与优惠券收集问题； 超立方体上的随机游走； -循环上的随机游走； 顶牌随机插入洗牌。 上界假设转移矩阵

回顾设 不可约，平稳测度为 。定义 本讲目标寻找混合时间的下界。主要方法与例子： 瓶颈比； 区分统计量； 超立方体上的随机游走。 设 是不可约转移矩阵，平稳测度为 。定义 表示初始分布为 时，链在一步内从集合 移动到集合

回顾假设转移矩阵 不可约，并具有平稳测度 。定义 今天的目标利用随机时刻给出混合时间 的上界。 顶牌随机插入洗牌； 停时与随机化停时； 平稳时刻与强平稳时刻。 顶牌随机插入洗牌考虑如下洗一副 张牌的方法： 取出最上面的一张牌，再

期中考试：4 月 6 日，上课时间进行； 考试均为闭卷，不得携带笔记，也不得使用计算器。 回顾若 是具有平稳分布 的不可约 Markov 链，则 几乎必然成立 本讲目标证明 在某种更强的意义下收敛到 ，并介绍： 全变差距离； 收

回顾考虑状态空间为 、转移矩阵为 的 Markov 链： 如果概率测度 满足 则称 是平稳分布。 如果 不可约，则存在唯一的平稳分布。 本讲目标 遍历定理； Markov 链的时间反演； 生灭链； 全变差距离。 定理　设 是

回顾考虑状态空间为 、转移矩阵为 的 Markov 链： 记： ： 的分布； ： 的分布。 如果概率测度 满足 则称 是平稳分布。 若 是平稳分布且 则对所有 ， 本讲目标 不可约性； 非周期性； 平稳分布的存在性与唯一

本课程介绍： Markov 链； 随机游走； 鞅。 David A. Levin、Yuval Peres、Elizabeth L. Wilmer： Markov Chains and Mixing Times（《Markov 链与混合时

关于 -代数的进一步思考 记 记 注意右连续性： 允许我们“无穷小地窥视一下未来”。 向前看 期望等价定理： 若 有界且可测，那么对所有 和 ，都有 其中 有界且可测。在这种情形下，结论几乎显然。然后使用与证明马