随机算法基础

这是NJU的计算理论之美的第一堂讲的，感觉讲的老师很强，讲的挺好的，所以简单写了一下。

概率方法基础

• 大家应该都会这个才对。

Lovász Local Lemma

• Lovász Local Lemma（LLL）直观上说的事情是：我有一些坏事件，如果这些坏事件每一个发生的概率都不大，而且它们相关性不大，那么这些坏事就有概率都不会发生。¹

Dependency Graph

• 要描述 LLL ，我们先定义依赖图。对于概率空间 上的一系列（坏）事件 ，其依赖图定义为 ，记 为事件 在 中的全体邻居，则 与 中的事件相互独立。

  一个问题是依赖图显然不是唯一的，“最小的”依赖图也时常没法定义。但是如果 被一系列独立随机变量完全刻画，那么最小依赖图是可以定义的。此时两个事件之间有边当且仅当刻画它们的随机变量有交。

Symmetric Version

• 对称版本的 LLL 即：

  • 若依赖图 上的每个点的度不超过 ，并且所有坏事件发生的概率一致不超过 ，那么若： 则：

• 我们已经介绍过 LLL 的直观，至于证明，会在下面一并给出。值得一提的是很多时候对称版本的 LLL 就已经足够使用了。

Asymmetric Version

• 非对称版本的 LLL 即：

  • 若存在一列数 ，使得对于每个坏事件有：² 则：

• 首先容易看出对称版本的 LLL 是非对称版本的推论。在对称版本的假设成立时，取 ，则： 这就说明对称版本是成立的。那么我们现在考虑证明非对称版本，我们就直接使用归纳了。考虑： 从而只需： 现在对 归纳。对事件标号得到 ，使得条件中前 个事件是 上 的邻居。从而： 对于分子，有： 对于分母： 从而 成立。则非对称版 LLL 成立。

Moser-Tardos Algorithm

• 通过 LLL 我们可以证明规避所有坏事件的样本必然是存在的，一个自然的问题是如何找出这样的样本，这就是 Algorithmic LLL 。这里我们将介绍著名的 Moser-Tardos 算法，其主要用于构造满足一定要求的 LLL 的好样本。

问题形式化

• 我们先把问题形式化一下。对于概率空间 的一系列坏事件 ，存在一列数 ，使得： 现在我们希望找到一个样本 使得 。特别的，现在我们要求所有坏事件可以被有限个独立随机变量 完全描述。

  定义记号 代表描述 的随机变量集合。那么显然：

算法描述

• 这个算法看起来非常简单且符合直观。即：

  1. 对 中的变量取样。
  2. 如果存在一个发生的坏事件 ，则对 中的所有变量重新取样。

• 为了详细描述该算法的执行和结果，我们要引入一个概念，即执行日志。考虑该算法第二步中按时间顺序重新取样的事件序列，其为 。那么该算法第二步的执行次数恰为执行日志的长度。将 在 中的出现次数记为 ，我们宣称： 这就保证了在 小时该算法有很好的期望运行时间。

期望取样次数分析

• 现在我们要证明以上的宣称。lecture 里面定义了一个概念，叫做 resampling table ，但是我觉得这个也不必要。总之，对于 中的每一事件，我们考虑它们的依赖关系，称作 witness tree 。现在我们考察 的情况，即从 开始向 移动，并一并构造 witness tree ，记作 。一开始 以 为根，若 直接或间接的影响 ，即 是当前 上某些节点在 上的邻居（或自身），我们就把 追加为这些节点中最深者的儿子，若有多个则选择最靠左者。

  这样做的好处是，现在 上的每一 都是唯一确定且互不相同的。从而： 其中 为全体以 为根的 witness tree 。那么： 注意此处的期望是对 求的。我们再宣称：³ 这看起来其实挺显然的，因为前者似乎包含事件“至少做 的事件的采样”，但笔者觉得这不够严格，所以我们要给出一个严谨的叙述。首先容易看出任何一个 witness tree 可以确定其中事件重采样的顺序，因为对于任何 依赖于 ，必然有 的深度大于 。假设在算法中我们按照某一顺序考虑事件，再考虑到映射 已知，我们就可以确定事件的采样顺序。那么确切的概率可以表述为：依照 给定的顺序对事件采样，再乘上 的事件序列中间若干不影响相关性的事件采样概率贡献的因子。而由于右式只考虑了对 中事件采样，“不超过”就自然成立。

• 那么由以上宣称，我们就有：⁴ 最后我们再宣称： 这个式子看起来很复杂，但可以用分支过程来比较简单的描述。考虑这样一个随机过程：我们从根开始生成一棵随机树， 的儿子只能在 （包含 本身）中产生，并且产生某一儿子 的概率为 。简单计算即可验证以上结果。这样我们就立刻有： 这个分析过程还是相当有趣的，特别是引入 witness tree 的部分，看起来复杂的结构却为我们的推理提供了方向。

Moser's Algorithm

• 这个部分我看的比较摆啊，可能也不会写的，但是先挂着。

---

1. 这套理论在交大的 CS0901 很靠后才讲，而且之前讲了很多很杂比较难的东西，把我讲麻了，所以当时对 LLL 的理解不太好。这次再来听感觉好了很多啊。↩︎

2. 我不确定 有什么好的直观。↩︎

3. lecture 里面这个好像是拿耦合证的，但是我可能不太擅长这个。↩︎

4. 看起来就是个级数求和，反正 witness tree 显然是可数的。↩︎