随机变量前缀和的控制

我们知道, 在某些背包问题中, 我们需要解决一些零和问题, 也即: 物品有正有负且都不是特别大 ($|w_i| \leq W$), 我们需要找到一个具有某种性质的子集 $S$, 满足 $\sum_S w_i = 0$. 对容量这一维进行 DP 的话, 体积是有可能达到 $\pm nW$ 量级的, 但如果问题只需要和答案有关的某一个 instance 被 DP 过程命中的话 (更具体地说就是比如问存在性或者某种东西的最优性, 那我们只需要达到最优解的那个方案被统计到), 我们有这样一个想法: 在 DP 之前先把物品随机打乱, 那么我们所需的那个 instance 的前缀和就总是不会很大. 这样一来, 我们就可以将这一维背包的容量缩小. 所以, 我们关心的问题的一般形式是: > 有 $n$ 个有界的随机变量 $|X_i| \leq W$, 且 $\mathbb E[X_1 + \dots + X_n] = 0$, 那么设 $S_k = X_1 + \dots + X_k$, 此时 $\max |S_k|$ 的具有怎样的分布? 其实对于一些特殊 (比如 $X_i$ 都是独立随机的 $\pm 1$, 各一半概率), 我们可以先通过组合上精确的计数来得到一些估计, 但对于一般情况来说, 概率论的一些方法其实也是差不多优秀的. 由于我们知道, 一些期望为 $0$ 的独立随机变量之和基本上集中在 $O(W \sqrt n)$ 的级别, 我们对前面问题的结果肯定是希望得到 $O(W\sqrt n)$ 的结果. 此外, 我们知道有界随机变量的和不仅期望偏离的不是很大, 它的 concentration 应该也是很好的. 接下来我们严格地论证这一点. ## 工具 对于概率空间的一个 filtration $\mathcal F_1 \subset \cdots \mathcal \subset \mathcal F_n$, 我们称一族期望存在的随机变量 $X_i\in \mathcal F_i$ 满足 $X_i\leq \mathbb E[X_{i+1}\mid \mathcal F_i]$ 为下鞅 (submartingale), 取等时称为鞅 (martingale). 我们有 > **Doob 不等式.** 对于下鞅, > $$\Pr \left[\max_i X_i > C\right] \leq \frac{\mathbb E[\max(X_n, 0)]}{C}.$$ 证明: 记随机变量 $T$ 为第一个 $X_i >C$ 的位置 $i$, 我们有 $$ \Pr \left[\max_i X_i > C\right]\leq \frac{\mathbb E[X_T]}{C}. $$ 设事件 $E_i = \{T=i\}$, 反复使用下鞅的定义, 得到 $X_i \leq \mathbb E[X_n \mid \mathcal F_i]$. 注意到 $E_i$ 是一个 $\mathcal F_i$ 中的事件, 所以我们有 $$\int_{E_i} X_i \,\mathrm{d}P \leq \int_{E_i} X_n \,\mathrm{d}P. $$ 对全体 $i$ 求和, 得到 $$ \int X_T \,\mathrm{d}P \leq \int \max(X_n, 0) \,\mathrm{d}P. $$ 然后由 Markov 不等式得证. > **Azuma–Hoeffding 不等式.** 如果鞅总是满足 $|X_i - X_{i+1}|\leq 1$, 有 > $$\Pr [ X_0 - X_n > \lambda \sqrt n ] \leq e^{-\lambda^2 / 2}. $$ 证明: 不妨设 $X_0 = 0$. 取 $Y_i = e^{tX_i}$, Jenson 不等式表明 $Y_i$ 是下鞅, 并且由于 $$ \mathbb E[Y_{i+1} \mid \mathcal F_i] \leq Y_i \frac{e^{t}+e^{-t}}{2} \leq e^{t^2/2}, $$ 我们有 $$ \Pr\left[ X_n > \lambda \sqrt n \right] \leq \frac{e^{nt^2/2}}{e^{t\lambda \sqrt n}}. $$ 取 $t = \lambda/\sqrt n$, 有 $\leq e^{-\lambda^2/2}$. 这个不等式具有另一个面貌: > **McDiarmid 不等式.** 对于一个函数 $f\colon \Omega^n \to \mathbb R$ 满足 $|f(x) - f(y)|\leq \| x - y \|_0$, 对于独立随机变量 $X_1, \dots, X_n$, 有 > $$\Pr [ f - \mathbb E f > \lambda \sqrt n ] \leq e^{-\lambda^2/2}. $$ 只需注意到已经确定 $X_1,\dots, X_{i}$ 的时候, $f( X)$ 是满足 Azuma–Hoeffding 不等式条件的鞅, 则立刻得到上面的结论. ## 正文 现在我们有总和为 $0$ 的数列 $w_1, \dots, w_n \in [-1, 1]$, 然后令随机变量 $X_i$ 是它们的随机排列. 记 $Y_i = X_1+\cdots + X_i$. 它们并不独立, 所以我们分成两步进行控制. **第一步**: 考虑随机变量 $X_i'$ 是 $w_1, \dots, w_n$ 中均匀随机选取的一个数, $X_i'$ 独立随机. 我们控制对应的 $Y_i'$. **第二步**: 将这样的 $X_i'$ 转化为合法的 $X_i$, 并控制对 $Y_i$ 的影响. ### 第一步 根据 Doob 不等式以及类似 Azuma–Hoeffding 的缩放过程, 我们可得 $$ \Pr\left[\max_i Y_i' > \lambda \sqrt n\right] \leq e^{-\lambda^2/2}. $$ ### 第二步 我们这里假设 $w_1,\dots, w_n$ 互不相同, 这本质上对正确性没有影响, 只是说 $X'$ 在随机选取的时候能辨别同样值的 $w$ 选了哪个. 我们考虑如下简单的缩放: 如果 $X_i'$ 是全体 $X'$ 中第 $l\sim r$ 大的 (就是说有可能有和它相同的情况), 那么随机将 $X_i$ 设为 $w$ 中第 $l\sim r$ 大中均匀随机的一个. 根据对称性, 易见这样得到的 $X$ 就是 $w$ 均匀随机的全排列. 注意到我们总是有 $$ |Y_i - Y_i'|\leq \sum |X_i' - X_i|, $$ 所以只需要控制 $\sum |X_i' - X_i|$. 不妨设 $w_1 < w_2 < \cdots < w_n$, 我们有 $$ \begin{aligned} \mathbb E\left[\sum |X_i' - X_i|\right] &= \sum_i (w_{i+1} - w_i)\mathbb E [|i - \#\{X_i'\leq i\}|]\\ &\leq \sum_i (w_{i+1} - w_i)\left(\mathbb E [|i - \#\{X_i'\leq i\}|^2]\right)^{1/2}\\ &\leq \sum_i (w_{i+1} - w_i) \cdot \frac{\sqrt n}{2}\\ &\leq \sqrt n. \end{aligned} $$ 记 $$f(X') = \sum |X_i - X_i'|,$$ 容易发现 $f/2$ 满足 Azuma–Hoeffding 的条件, 因此 $$ \Pr [ (f/2) - \mathbb E (f/2) > \lambda \sqrt n ] \leq e^{-\lambda^2/2}. $$ 因此 $$ \Pr[ f > (1 + 2\lambda)\sqrt n ] \leq e^{-\lambda^2 / 2}. $$ 控制了每个 $|Y|$ 的变化量就控制了 $\max |Y|$ 的变化量, 因此我们有 $$ \Pr \left[\max_i Y_i > (1 + 3\lambda)\sqrt n \right] \leq 2e^{-\lambda^2/2}. $$ 因此, 我们有 $$ \Pr \left[\max_i |Y_i| > (1 + \lambda)\sqrt n \right] \leq 4e^{-\lambda^2/18}. $$