随机变量前缀和的控制

· · 个人记录

我们知道, 在某些背包问题中, 我们需要解决一些零和问题, 也即: 物品有正有负且都不是特别大 (|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, 我们有

\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}.