Revision | 随机算法
球和桶模型（Balls and Bins）
The Power of Two Choices
Remark. 本节将揭示往往只需要一些简单的随机选择便可能实现效果良好的负载均衡。为此，我们先分析最简单的随机方法下高概率的最大负载，然后分析每次选择两个桶，然后向较负载较小的桶中加一个球高概率的最大负载。
考虑如下情景：向 $n$ 个桶中随机投放 $m$ 个小球（每个小球的投放位置从 $n$ 个桶中均匀随机抽取）。我们现在想要分析诸桶的最大负载（i.e. 球最多的桶里面有多少球）。首先需要明确的是，球的状态服从多项分布，即
$$
\Pr[X_1 = k_1, …, X_n = k_n] = \frac{1}{n^m}\frac{m!}{k_1!…k_n!}
$$
其中 $\sum_{i=1}^n k_i = m$。因为 $X_i$ 之间并不独立，所以分析难以进行，但是注意到，令 $Y_1, …, Y_n$ 是 $n$ 个独立服从泊松分布 $\pi(m / n)$ 的随机变量，则不难验证
$$
\Pr[X_1 = k_1, …, X_n = k_n] = \Pr\left[Y_1 = k_1, …, Y_n = k_n \bigg | \sum_{i=1}^n Y_i = m\right]
$$
下面的定理揭示了多项分布下的事件发生的概率可以用泊松分布近似。
定理 1. 令 $\mathcal{E}$ 是一个仅基于桶的负载的事件，满足 $\Pr[\mathcal{E}]$ 关于 $m$ 单调递增（或递减），则
$$
\Pr_X[\mathcal{E}] \leq 4\Pr_Y[\mathcal{E}]
$$
其中 $\Pr_X$ 为将 $X$ 视作桶的负载时对应的概率，$\Pr_Y$ 类似；可以发现，后者取消了球的总数，并让每个桶中的球数独立。
证明. 这里只证明递增的情况，递减的情况时完全类似的。有
$$
\begin{aligned}
\Pr_Y[\mathcal{E}] &= \sum_{k=0}^\infty \Pr_Y\left[\mathcal{E} \bigg| \sum Y_i = k\right]\Pr_Y\left[\sum Y_i = k\right] \\
&\geq \Pr_Y\left[\mathcal{E} \bigg|\sum Y_i = m\right]\Pr_Y\left[\sum Y_i \geq m\right] \\
&\geq \frac 14\Pr_X[\mathcal{E}]
\end{aligned}
$$
此处的常数 $1/4$ 来源于关于泊松分布的简单事实 $\Pr[Y\geq \mathbb{E}[Y]] \geq 1/4$；至少在 $m = n$ 的时候这个是对的。
接下来我们形式化“最大负载”：
定理 2. 对于上述的球和桶模型，有高概率最大负载是 $\Theta(\ln n / \ln \ln n)$ 的。
证明. 令 $\varepsilon > 0$，定义 $c_1 = 1 + \varepsilon, c_2 = 1 - \varepsilon$。只需要证明：
- 小概率存在一个桶中球的数量 $> c_1\ln n / \ln \ln n$，记作事件 $\mathcal{E}_1$；
- 小概率所有桶中球的数量 $< c_2 \ln n / \ln \ln n$，记作事件 $\mathcal{E}_2$。
首先可以考察一下泊松分布 $\pi(1)$ 的尾部，令 $p_k = \sum_{j = k}^\infty \frac{e^{-1}}{j!}$，显然
$$
\frac{1}{ek!}\leq p_k \leq \frac{1}{k!}\cdot \frac 1e\left(1 + \sum_{i=1}^n \frac{1}{(k+1)^{\overline i}}\right) \leq \frac{1}{k!}
$$
接下来，注意上述事件都符合定理 $1$ 的要求。取 $k = (1 + \varepsilon)\ln n/\ln\ln n$，则证明第一个断言只需要应用一次 Union Bound：
$$
\begin{aligned}
\Pr[{\mathcal{E}_1}]
\leq n p_k
\leq n\exp(-\ln k!)
\approx n\exp(-k\ln k)
\approx n\exp(-(1 + \varepsilon)\ln n)
= o(1)
\end{aligned}
$$
且使用定理 $1$ 以后，我们取消了桶之间的非独立性，因此证明第二个断言时可以直接将概率拆成乘积：
$$
\Pr_Y[{\mathcal{E}_2}] = (1 - p_k)^n \leq \left(1 - \frac{1}{ek!}\right)^{n} \leq e^{-\frac{n}{ek!}} \approx \exp\left(-\frac{n}{e\exp((1-\varepsilon)n)}\right) = o(1)
$$
接下来考察另一种情形，每次选择两个桶，然后向较负载较小的桶中加一个球。我们将证明这样操作使得最大负载高概率是
$$
\frac{\ln \ln n}{\ln 2} + \Theta(1)
$$
和上方的结果做对比可以发现这样使得最大负载指数级地下降。这称为 The Power of Two Choices。
【FIXME】
随机图
随机图 $\mathcal{G}_{n, p}$ 是一个随机变量，它是一个 $n$ 个点的图，图中每条边出现的概率为 $p$。
大连通块（Giant Component）
本节重点证明随机图上，关于图中最大的连通块有如下的阈值：
定理 1. 考虑随机图 $G = \mathcal{G}_{n, p}$，其中 $p = \frac{c}{n}$，此处 $c$ 是常数。我们有：
- 若 $c < 1$，则 $G$ 中最大连通块大小为 $O(\log n)$，a.a.s.
- 若 $c > 1$，则 $G$ 中存在一个大小为 $\beta n(1 + o(1))$ 大的连通块，其中 $\beta$ 是 $\beta + e^{-\beta c} = 1$ 在 $(0, 1)$ 上的解；进一步，次大连通块大小为 $O(\log n)$，a.a.s.
上述表述中，「a.a.s」为 asymptotically almost surely 的缩写，系指当 $n\rightarrow \infty$ 时事件发生的概率趋近于 $1$。
首先，我们需要建立一些关于上述定理中所述的奇怪的方程 $\beta + e^{-\beta c} = 1$ 的直觉。这个方程源自 Galton-Watson 分支过程，其相关定义如下：
定义 1（Galton-Watson 分支过程）. 设 $X$ 是一非负整数随机变量，则由 $X$ 定义的分支过程起始于一个单独的节点；每个时间步，上一个时间步新产生的每个节点将产生 $X$ 个儿子。
用随机变量 $Z_i$ 刻画第 $i$ 个时间步时产生的节点数量，依定义有 $Z_0 = 1$。定义事件“灭绝（extinction）”为在该分支过程中，最终某一层不产生任何儿子，形式化地：
$$
\Pr[\text{extinction}] = \lim_{n\rightarrow \infty}\Pr[Z_n = 0]
$$
这个模型类似于传染病传染的过程。$X$ 的期望值 $\mathbb{E}[X]$ 正是传染病中的 $R_0$ 的一种更为通用的刻画。我们有：
定理 2. 对于一个由 $X$ 定义的分支过程，若 $\Pr[X = 0] > 0, \Pr[X = 1] < 1$，则
- 若 $\mathbb{E}[X]\leq 1$，则 $\lim_{n\rightarrow\infty} \Pr[Z_n = 0] = 1$，即该过程将灭绝，a.a.s.
- 若 $\mathbb{E}[X] > 1$，则 $\lim_{n\rightarrow \infty}\Pr[Z_n = 0] = p^* < 1$，其中 $p^*$ 时 $f(x) = x$ 在 $(0, 1)$ 之间的唯一解（$f(x)$ 为 $X$ 的概率生成函数）。
证明. 记 $f_n$ 为 $Z_n$ 的概率生成函数，即
$$
f_n(x) := \sum_{i\geq 0} \Pr[Z_n = i]x^i
$$
注意到 $f_n$ 满足如下递推关系：$f_n(x) = f(f_{n - 1}(x))$。现在要分析的是 $\Pr[Z_n = 0]$，即 $q_n := f_n(0)$。直接向上述递推关系中代入 $x = 0$ 得到 $q_n$ 满足如下递推关系：$q_n = f(q_{n - 1})$。不难收集如下关于 $f(x)$ 和 $q_n$ 的性质：
- $q_n$ 单调递增（因为如果前一时刻已经灭绝，那么以后必然也灭绝）且有界（概率不超过 $1$），因此必然收敛。
- $f(x)$ 为 $[0, 1]$ 上的连续单调递增下凸函数。
以上两条联合起来给出 $q$ 的极限是 $f(x)$ 在 $[0, 1]$ 上的不动点。注意 $f(1) = 1$，因此 $f(x) = x$ 在 $(0, 1)$ 有解当且仅当 $\mathbb{E}[X] = f’(1) > 1$。在证明过程中我们省略了一些琐碎的数学分析，然而可以参照下面的图像理解此证明：
在随机图上，我们可以通过 bfs 来遍历一个连通块，即每次揭示一排点的邻居。这和 Galton-Watson 分支过程如出一辙。注意，一个点的邻居数量几乎就是服从二项分布 $B(n, c/n)$。当 $n$ 趋向无穷大时，这个分布点点收敛于泊松分布 $\pi(c)$。而泊松分布的生成函数是
$$
f(x) = \sum_i\frac{c^ie^{-c}}{i!}x^i = e^{c(x - 1)}
$$
所以 bfs 停下的概率 $p^*$ 是方程
$$
e^{c(x - 1)} = x
$$
的整数解。$\beta = 1 - x$ 可以视为一个点在最大连通块中的概率，这样便得到了定理 1 中的方程 $\beta + e^{-\beta c} = 1$。
最后来严格证明一次本节定理 1。
第一部分（$c < 1$ 时最大连通块不大）. 考虑事件“一个点 $v$ 在一个大小为 $k$ 的连通块中”的概率。此事件发生仅当一个 bfs 状的分支过程至少产生了 $k$ 个节点，且所有节点产生的儿子总数超过 $k - 1$，即
$$
\sum_{i=1}^k X_i \geq k - 1, \text{where $X_i \sim B\left(n - \sum_{j = 1}^{i - 1}X_j, c/n\right)$}
$$
这个事件看起来难以分析，但是可以注意到将 $X_i$ 的分布宽限为 $B(n, c/n)$，得到的概率定不会变小。即
$$
\begin{aligned}
\Pr[\text{$v$ in a component of size $\geq k$}] &\leq \Pr\left[\sum_{i=1}^l X_i\geq k - 1\right] \text{where $X_i\sim B(n, c/n)$, i.i.d.} \\
&=\Pr\left[\sum_{i=1}^k X_i - ck \geq (1-c)k - 1\right] \\
&\leq \exp\left(-\frac{((1 - c)k - 1)^2}{ck^2(2 + ((1-c)k - 1)/ck)}ck\right) \\
&=\exp\left(-\frac{(1-c)^2 k}{2} + O(1)\right)
\end{aligned}
$$
Hint.
这里第三行是一个 Chernoff bound，回忆
$$
\Pr[X\geq (1 + \delta)\mu] \leq \exp\left(-\frac{\delta^2 \mu}{(2 + \delta)}\right)
$$
在本推导中 $\delta = \frac{(1 - c)k - 1}{ck}$，$\mu = ck$。
取 $k = \frac{3}{(1 - c)^2}\ln n$，上述概率不超过 $O(n^{-\frac{3}{2}})$，对所有点用 union bound 得到存在一个连通块大小超过 $3\ln n/(1-c)^2$ 的概率仅为 $o(1)$ 级别。
第二部分（$c > 1$ 时只有一个大连通块）. 【FIXME】
鞅
本节讲随机过程中的重要概念鞅，主要围绕其集中不等式和可选停时定理展开。
定义 1（鞅）. 给定一列非降 $\sigma$-代数 $\varnothing = \mathcal{F}_0 \subseteq \mathcal{F}_1 \subseteq \mathcal{F}_n$，称作滤子，以及一列随机变量 $X_1, …, X_n$。若对于任意的 $i$ 都有 $\mathbb{E}[X_i | \mathcal{F}_{i - 1}] = X_{i - 1}$，则 $(X_i)$ 称作关于 $(\mathcal{F}_i)$ 的鞅；$Y_i = X_i - X_{i - 1}$ 称作其差分序列，依定义有 $\mathbb{E}[Y_i | \mathcal{F}_i] = 0$
一个常举的例子是有一个点 $x$ 在数轴上随机游走，每时刻其坐标等概率地 $+1$ 或者 $-1$，$n$ 步之后停止。那么显然，该点最终位置的期望值是关于前 $i$ 次移动方向的鞅。当然在 CS 中，我们通常不需要用到非降 $\sigma$-代数这种抽象层级的概念，只需采纳一种形象的理解，即鞅是在一个逐渐发展的过程中，随着新信息被不断揭露，对结果的估计量。因此可将那一列非降 $\sigma$-代数替换做一列随机变量 $Z_1, …, Z_n$，并将定义对应修改为 $\mathbb{E}[X_i | Z_{1}…Z_{i - 1}] = X_{i - 1}$。
对于任意一个随机变量 $A$ 和一列随机变量 $Z_1, …, Z_n$，我们都可以构造一个鞅。
定理 2（Doob 鞅）. 令 $A$ 和 $Z_1, …, Z_n$ 为同一个概率空间上的随机变量。则 $X_i = \mathbb{E}[A | Z_1 … Z_i]$ 是一个鞅，称作 $A$ 的 Doob 鞅。
证明.
只需要验证即可，注意（第二行只需按定义计算即可）
$$
\begin{aligned}
\mathbb{E}[X_i | Z_1 … Z_{i - 1}] &= \mathbb{E}[\mathbb{E}[A | Z_1 … Z_i] | Z_1 … Z_{i - 1}] \\
&= \mathbb{E}[A | Z_1 … Z_{i - 1}]
\end{aligned}
$$