集中不等式

  集中不等式描述一个随机变量是否集中在某个取值 (例如其期望) 附近, 它一般是关于 $\Pr(|X - \mathrm EX| \leq \varepsilon)$ 的一类不等式.

1 Chernoff 不等式

1.1 Chebyshev-Markov 不等式族

Markov 不等式 令 $X$ 是一个非负随机向量, $\forall \varepsilon > 0$,

$$\Pr(X \geq \varepsilon) \leq \frac{\mathrm EX}{\varepsilon} \quad \iff \quad \mathrm EX \geq \varepsilon \Pr(X \geq \varepsilon)$$

从正向看, 它给随机变量的尾部概率给定了一个上界 (即给随机变量集中于 $[0, \varepsilon)$ 区间的概率指定了下界). 从反向看, 它给随机变量的数学期望指定了一个下界, 这个下界与其尾部概率有关.

证明 证明是很直观的, 因为

$$\mathrm EX = \Bigg( \underbrace{\Pr(X < \varepsilon) \cdot \mathrm EX \Big|_{X < \varepsilon}}_{\geq 0} + \Pr(X \geq \varepsilon) \cdot \underbrace{\mathrm EX \Big|_{X \geq \varepsilon}}_{\geq \varepsilon} \Bigg) \geq \varepsilon \Pr(X \geq \varepsilon)$$

Chebyshev 不等式 考虑随机变量 $(X - \mathrm EX)^2$ 总是非负的. 可以应用 Markov 不等式, $\forall \varepsilon > 0$,

$$\Pr(|X - \mathrm EX| \geq \varepsilon) = \Pr((X - \mathrm EX)^2 \geq \varepsilon ^2) \leq \frac{\mathrm E(X - \mathrm EX)^2}{\varepsilon ^2} = \frac{\mathrm{Var}X}{\varepsilon ^2}$$

Chebyshev 大数定律 使用 Chebyshev 不等式可以证明 Chebyshev 大数定律. 令 $\{X_i\}$ 相互独立且有相同方差上界 $\mathop{\mathrm{Var}}X \leq c$, 则 $\forall \varepsilon > 0$,

$$\lim_{n \to \infty} \Pr\left( \frac{1}{n} \sum (X_i - \mathrm EX_i) \geq \varepsilon \right) = 0$$

证明 根据条件有 $\mathop{\mathrm{Var}}(\sum X_i / n) \leq c/n$. 对 $\sum X_i / n$ 应用 Chebyshev 不等式,

$$\Pr\left( \left| \frac{1}{n} \sum (X_i - \mathrm EX_i) \right| \geq \varepsilon \right) \leq \frac{\mathop{\mathrm{Var}}(\sum X_i / n)}{\varepsilon ^2} = \frac{c}{n\varepsilon ^2}$$

取 $n \to \infty$ 即得证.

例 假设在统计建模中有一种将向量 $\boldsymbol \theta = (\theta _1, \dots, \theta _n)$ 稀疏化的方法: 选定参数 $p_1, \dots, p_n$, 然后取

$$\hat \theta _i = \frac{\theta_i}{p_i} \cdot t_i, \qquad t_i \sim b(p_i)$$

试证: 在该方法下存在一组良好的参数, 使得对于任意单位圆内的向量 $\boldsymbol x$, 任取 $\varepsilon > 0$, 都存在 $\delta$ 使得

$$\Pr(|\boldsymbol \theta^T \boldsymbol x - \hat{\boldsymbol \theta}^T \boldsymbol x| \geq \varepsilon) \leq \delta$$

证明 注意到

$$\mathrm E\hat \theta _i = \frac{\theta_i}{p_i} \cdot 1 \cdot p_i + \frac{\theta_i}{p_i} \cdot 0 \cdot (1 - p_i) = \theta_i$$

所以 $\mathrm E\hat{\boldsymbol \theta}^T \boldsymbol x = \mathrm E\boldsymbol \theta^T \boldsymbol x$. 因此所证不等式左侧正是关于 $\hat{\boldsymbol \theta}^T \boldsymbol x$ Chebyshev 不等式的形式. 应用 Chebyshev 不等式有

$$\Pr(|\boldsymbol \theta^T \boldsymbol x - \hat{\boldsymbol \theta}^T \boldsymbol x| \geq \varepsilon) \leq \frac{\mathop{\mathrm{Var}}(\hat{\boldsymbol \theta}^T \boldsymbol x)}{\varepsilon ^2}$$

其中

$$\mathop{\mathrm{Var}}\hat{\boldsymbol \theta}^T \boldsymbol x = \boldsymbol x^T (\mathop{\mathrm{Cov}}\hat{\boldsymbol \theta}) \boldsymbol x = \sum \boldsymbol x_i^2 \mathop{\mathrm{Var}} \hat \theta _i$$

其中最后一个等号需要假设 $\theta _1, \dots, \theta _n$ 线性无关. 而

$$\mathop{\mathrm{Var}} \hat \theta _i = \mathop{\mathrm{Var}} \left(\frac{\theta_i}{p_i} \cdot t_i\right) = \frac{\theta_i^2}{p_i^2} \cdot p_i(1 - p_i) = \theta _i^2 \cdot \frac{1 - p_i}{p_i}$$

现在可以选定 $p_i$ 的数值了. 假设我们要证明关于给定 $(\varepsilon, \delta)$ 的不等式, 现在很聪明地选取 $p_i$

$$p_i := \frac{1}{1 + \delta \varepsilon ^2 / \theta _i ^2} \quad \iff \quad \theta _i^2 \cdot \frac{1-p_i}{p_i} = \delta \varepsilon ^2$$

这样的好处是 $\mathop{\mathrm{Var}} \hat \theta _i = \delta \varepsilon ^2$. 于是 $\mathop{\mathrm{Var}}\hat{\boldsymbol \theta}^T \boldsymbol x = \delta \varepsilon ^2 |\boldsymbol x|^2 \leq \delta \varepsilon ^2$, 从而命题得证.

Chebyshev-Markov 不等式族的一般形式 令 $X$ 是随机变量 (不必要非负), 给定变换函数 $g(\cdot) \geq 0$ 非降, 且 $g(\varepsilon) > 0$.

$$\Pr(X \geq \varepsilon) \leq \frac{\mathrm Eg(X)}{g(\varepsilon)} \quad \iff \quad \mathrm Eg(X) \geq g(\varepsilon) \Pr(X \geq \varepsilon)$$

证明方法与 Markov 不等式相同.

1.2 Chernoff 不等式

Chernoff 界 注意到包含参数 $t>0$ 的函数 $g(x; t) = e^{tx}$ 是正非降的. 令 $t$ 是随机变量 $X$ 的矩母函数, 则应用 Chebyshev-Markov 不等式族的一般形式,

$$\Pr(X \geq \varepsilon) \leq \frac{\mathrm Ee^{tX}}{e^{t\varepsilon}}, \qquad \forall t > 0$$

它的另一个方向是

$$\Pr(X \leq \varepsilon) \leq \frac{\mathrm Ee^{tX}}{e^{t\varepsilon}}, \qquad \forall t < 0$$

不等号右边是关于参数 $t$ 的函数, 找到其最小值, 可以进一步可以找到最小上界.

注 指数函数是一个下凸函数, 据 Jensen 不等式有 $\mathrm Ee^{tX} = \mathrm E e^{tX} \geq e^{t \mathrm EX}$. 所以若 $\varepsilon \leq \mathrm EX$ 时 Chernoff 界大于等于 $1$ 导致其不包含信息.

例 计算中心正态分布 $X \sim N(0, \sigma^2)$ 的 Chernoff 界. 我们知道它的矩母函数 $\mathrm Ee^{tX} = e^{t^2 \sigma^2 /2}$. 它的 Chernoff 界是

$$\Pr(X \geq \varepsilon) \leq \frac{e^{t^2 \sigma^2 /2}}{e^{t\varepsilon}} = e^{t^2 \sigma^2/2 - t\varepsilon}$$

找到右边二次式的最小值, 取 $t = \varepsilon / \sigma^2$, 得到

$$\Pr(X \geq \varepsilon) \leq e^{-\varepsilon^2/2\sigma^2}$$

例 计算二项分布 $X \sim B(n, p)$ 的 Chernoff 界. 我们知道它的矩母函数

$$\mathrm Ee^{tX} = (1 - p + pe^t)^n = (1 + p(e^t - 1))^n \leq (e^{p(e^t - 1)})^n = e^{\mu (e^t - 1)}$$

其中 $\mu := np$. 对 Chernoff 界做换元 $\delta := \varepsilon / \mu - 1$ 可以得到

$$\Pr(X \geq (1 + \delta) \mu) \leq \frac{\mathrm Ee^{tX}}{e^{t\varepsilon}} \leq \frac{e^{\mu (e^t - 1)}}{e^{t (1 + \delta) \mu}} = e^{\mu (e^t - 1 - (1 + \delta)t)}$$

右侧的带参函数 $h(t; \delta) = e^t - 1 - (1+\delta) t$ 在 $t = \ln(1 + \delta)$ 处有全局最小值. 所以

$$\Pr(X \geq (1 + \delta) \mu) \leq \frac{e^{\delta \mu}}{(1 + \delta)^{(1 + \delta) \mu}} \leq e^{-\delta^2 \mu / 3}$$

其中最后一步使用了不等式 $\ln(1+\delta) \geq 2\delta / (2 + \delta)$, 需要条件 $0 < \delta < 1$. 另一个方向的不等式 $\Pr(X \geq (1 - \delta) \mu) \leq e^{-\delta^2 \mu / 2}$ 是类似的, 但是限定 $t < 0$.

  Chernoff 界使用矩母函数描述尾部概率. 矩母函数对独立随机变量的和有良好性质: 对于独立随机变量 $X$ 和 $Y$, 有 $\mathrm Ee^{t(X+Y)} = \mathrm Ee^{tX} \mathrm Ee^{tY}$. 于是可以得到多个随机变量和的 Chernoff 不等式.

Chernoff 不等式 对于 i.i.d 的随机变量列 $X_1, \dots, X_n$, 有

$$\Pr(X_1 + \cdots + X_n \geq \varepsilon) \leq \frac{\prod \mathrm Ee^{tX_i}}{e^{t\varepsilon}}$$

例 给定 $X_1, \dots, X_n \sim \mathrm{Std}N$ i.i.d, 计算其平方和的 Chernoff 界. 我们知道 $\mathrm{Std}N$ 的平方服从 $\chi^2(1)$ 分布, 它的矩母函数是 $\mathrm Ee^{tX_i^2} = (1 - 2t)^{-1/2}, t \leq 1/2$. 所以其平方和的 Chernoff 界是

$$\Pr(X_1^2 + \cdots + X_n^2 \geq \varepsilon) \leq \frac{\prod \mathrm Ee^{tX_i^2}}{e^{t\varepsilon}} = \frac{(1 - 2t)^{-n/2}}{e^{t\varepsilon}}, \quad \forall t \in (0, 1/2]$$

2 亚高斯分布和 Hoeffding 不等式

2.1 亚高斯分布

亚高斯分布 称一个概率分布 $X$ 服从亚高斯分布, 如果它的尾部概率被正态分布限制. 即存在常数 $\sigma^2$ (称为代理方差) 使得任取 $\varepsilon > 0$, 都有

$$\Pr(|X| \geq \varepsilon) \leq 2 e^{-\varepsilon ^2/2\sigma ^2}$$

使用矩母函数的等价定义是: 称一个概率分布 $X$ 服从代理方差为 $\sigma ^2$ 的亚高斯分布 $\mathrm{subG}(\sigma ^2)$, 如果其中心化矩母函数被方差为 $\sigma ^2$ 的高斯分布限制

$$\mathrm E e^{t(X - \mathrm EX)} \leq e^{t^2 \sigma^2/2}, \quad \forall t \in \mathbb R$$

由这个定义配合 Chernoff 不等式可以推出

$$\Pr(X \geq \varepsilon) \leq \frac{\mathrm E e^{t(X - \mathrm EX)}}{e^{t\varepsilon}} \leq \frac{e^{t^2 \sigma^2/2}}{e^{t\varepsilon}} = e^{t^2 \sigma^2/2 - t\varepsilon}$$

当 $t = \varepsilon / \sigma^2$ 时, 右侧取到最小值 $e^{-\varepsilon ^2 / 2\sigma ^2}$.

2.2 Hoeffding 不等式

Hoeffding 引理 假设一个随机变量 $X$ 取值于 $a < X < b$ a.s., 则它的中心化矩母函数

$$\mathrm E e^{t(X - \mathrm EX)} \leq e^{t^2 (b-a)^2/8}, \quad \forall t \in \mathbb R$$

证明 不失一般性, 假设 $\mathrm EX = 0$. 指数函数是一个下凸函数, 所以

$$e^{tx} \leq \frac{b-x}{b-a} e^{ta} + \frac{x-a}{b-a} e^{tb}$$

于是

$$\begin{aligned} \mathrm E e^{tX} &\leq \frac{b-\mathrm EX}{b-a} e^{ta} + \frac{\mathrm EX - a}{b-a} e^{tb} = \frac{b}{b-a} e^{ta} - \frac{a}{b-a} e^{tb} \\ &= \exp \left( ta + \ln \left(1 + \frac{a-e^{t(b-a)}a}{b-a}\right) \right) =: L(t(b-a)) \end{aligned}$$

其中构造了辅助函数

$$L(h) = \frac{ha}{b-a} + \ln \left(1 + \frac{a-e^ha}{b-a}\right)$$

它在 $h=0$ 处的导数是

$$L(0) = L'(0) = 0, \quad L''(0) = \frac{b}{b - ae^h} \cdot \frac{-ae^h}{b - ae^h} \leq \frac 14, \quad \forall h$$

最后一步使用了均值不等式. 考虑带 Lagrange 型余项的 MacLaurin 展开

$$L(h) = L(0) + L'(0)h + \frac 12 L''(h\theta) h^2 \leq \frac 18 h^2, \quad \forall h, \exists \theta \in [0, 1]$$

回代即得证.

推论 $a \leq X \leq b$ a.s. 的随机变量服从代理方差为 $(b-a)^2/4$ 的亚高斯分布.

Hoeffding 不等式 给定随机变量列 $\{X_i\}_{i=1}^n$ 满足 $a_i \leq X_i \leq b_i$ a.s., 则

$$\Pr\left(\sum (X_i - \mathrm EX_i) \geq \varepsilon\right) \leq \exp\left(-\frac{2\varepsilon^2}{\sum (b_i-a_i)^2}\right)$$

证明 $\sum (X_i - \mathrm EX_i)$ 的 Chernoff 界是

$$\begin{aligned} \Pr\left(\sum (X_i - \mathrm EX_i) \geq \varepsilon\right) &\leq \frac{\prod \mathrm Ee^{t(X_i - \mathrm EX_i)}}{e^{t\varepsilon}} \leq \frac{\prod e^{t^2 (b_i-a_i)^2/8}}{e^{t\varepsilon}} \\ &= \exp \left( \frac 18 \sum t^2 (b_i-a_i)^2 - t\varepsilon \right) \end{aligned}$$

这是一个二次函数求最值问题. 取 $t = 4\varepsilon / \sum (b_i-a_i)^2$ 然后回代即得证.

  Hoeffding 不等式的两侧形式是

$$\Pr\left(\left| \sum (X_i - \mathrm EX_i) \right| \geq \varepsilon\right) \leq 2\exp\left(-\frac{2\varepsilon^2}{\sum (b_i-a_i)^2}\right)$$

直接取 $\varepsilon \gets n\varepsilon$, 可以得到关于均值的形式

$$\Pr\left(\bar X - \mathrm EX \geq \varepsilon\right) \leq \exp\left(-\frac{2n^2\varepsilon^2}{\sum (b_i-a_i)^2}\right)$$

以及

$$\Pr\left(|\bar X - \mathrm EX| \geq \varepsilon\right) \leq 2\exp\left(-\frac{2n^2\varepsilon^2}{\sum (b_i-a_i)^2}\right)$$

Hoeffding 不等式可以用于构造置信区间.

例 对两点分布 $X \sim b(p)$ 做 $n$ 次简单随机抽样 $X_1, \dots, X_n$. 希望计算尾部概率 $\Pr(\bar X \notin [p-\varepsilon, p+\varepsilon])$ 的上界. 注意到 $X \in [0, n]$, 直接使用 Hoeffding 不等式,

$$\Pr\left(|\bar X - p| \geq \varepsilon\right) \leq 2\exp\left(-\frac{2n^2\varepsilon^2}{\sum n^2}\right) = 2e^{-2\varepsilon^2/n}$$

即是所求的上界.

2.3 最大值的期望

最大值的期望 设 $X_i \sim \mathrm{subG}(\sigma^2)$ i.i.d, 则

$$\mathrm E \max _i (X_i - \mathrm EX_i) \leq \sqrt{2} \sigma \sqrt{\ln n}$$

证明 使用 Jensen 不等式、亚高斯分布的等价定义 (注意这里要避免循环论证) 和一些放缩,

$$\begin{aligned} \mathrm E \max (X_i - \mathrm EX_i) &= \frac 1t \mathrm E \ln e^{t\max (X_i - \mathrm EX_i)} \leq \frac 1t \ln \mathrm E e^{t\max (X_i - \mathrm EX_i)} \\ &= \frac 1t \ln \mathrm E \max e^{t (X_i - \mathrm EX_i)} \leq \frac 1t \ln \mathrm E \sum e^{t (X_i - \mathrm EX_i)} \\ &\leq \frac 1t \ln ne^{t^2 \sigma^2/2} = \frac{\ln n}{t} + \frac{\sigma^2 t}{2} \end{aligned}$$

这是一个对勾函数, 取 $t = \sqrt{2\ln n}/\sigma$ 即得证.

3 亚指数分布和 Bernstein 不等式

3.1 亚指数分布

亚指数分布 亚高斯分布的限制太严格了. 我们可以放宽限制, 只要求

$$\mathrm Ee^{t(X - \mathrm EX)} \leq e^{t^2\nu^2/2}, \quad \forall |t| \leq \frac 1\alpha$$

此时称随机变量 $X$ 服从 $\mathrm{subE}(\nu^2, \alpha)$.

例 亚高斯分布都是亚指数分布. $X \sim \mathrm{subG}(\sigma^2) \implies X \sim \mathrm{subE}(\sigma^2, 0)$.

例 自由度为 $1$ 的卡方分布是亚指数分布, 但不是亚高斯分布. 令 $X \sim \chi^2(1)$, 则它有均值 $1$. 它的中心化矩母函数是

$$\mathrm E e^{t(X - \mathrm EX)} = \frac{\mathrm Ee^{tX}}{e^t} = \frac{1}{\sqrt{1-2t}e^t}, \quad t \leq \frac 12$$

可以证明

$$\frac{1}{\sqrt{1-2t}e^t} \leq e^{2t^2}, \quad |t| \leq \frac 14$$

证明细节见参考文献. 故 $X \sim \chi^2(1)$ 服从 $\mathrm{subE}(2^2, 4)$.

  在 $t$ 较小时, 亚指数分布呈现亚高斯行为; 在 $t$ 较大时, 它呈现亚指数型尾部概率:

$$\Pr(X - \mathrm EX \geq \varepsilon) \leq \begin{cases} e^{-\varepsilon^2 / 2\nu^2}, & \varepsilon \leq \nu^2 / \alpha \\ e^{-\varepsilon / 2\alpha}, & \varepsilon > \nu^2 / \alpha \end{cases}$$

证明 不失一般性, 假设 $\mathrm EX = 0$. 考虑 Chernoff 界

$$\Pr(X \geq \varepsilon) \leq \frac{\mathrm Ee^{tX}}{e^{t\varepsilon}} \leq e^{t^2 \nu^2/2 - t\varepsilon}, \quad \forall |t| \leq \frac 1\alpha$$

这是一个带限定条件的二次函数求最小值问题. 分类讨论即可得证.

3.2 Bernstein 不等式

Bernstein 条件 称一个随机变量 $X$ 满足 Bernstein 条件, 如果

$$\mathrm E(X - \mathrm EX)^k \leq \frac{k! b^{k-2}}{2} \mathop{\mathrm{Var}}X, \quad \exists b, \forall k \geq 2$$

例 任何 $|X - \mathrm EX| \leq c$ 的随机变量 $X$ 满足 $b = c/3$ 的 Bernstein 条件.

证明 注意到对于任意 $k\geq 2$ 有 $k!/2 \geq 3^{k-2}$, 故

$$\begin{aligned} \mathrm E(X - \mathrm EX)^k &= \mathrm E((X - \mathrm EX)^{k-2} (X - \mathrm EX)^2) \\ &\leq \mathrm E(|X - \mathrm EX|^{k-2}(X - \mathrm EX)^2) \\ &\leq \mathrm E(c^{k-2}(X - \mathrm EX)^2) = c^{k-2} \mathop{\mathrm{Var}}X \leq \frac{k!}{2} \left(\frac c3\right)^{k-2} \mathop{\mathrm{Var}}X \\ \end{aligned}$$

Bernstein 不等式 任何满足 Bernstein 条件的随机变量 $X$ 的中心化矩母函数都有上界

$$\mathrm Ee^{t(X - \mathrm EX)} \leq \exp \left( \frac{t^2 \mathop{\mathrm{Var}}X}{2(1-b|t|)} \right), \quad \forall |t| \leq \frac 1b$$

和集中不等式

$$\Pr(|X - \mathrm EX| \geq \varepsilon) \leq 2 \exp \left( -\frac{\varepsilon^2}{2(\mathop{\mathrm{Var}}X + b \varepsilon)} \right)$$

因此 $X \sim \mathrm{subE}((\sqrt{2\mathop{\mathrm{Var}}X})^2, 2b)$.

证明 不失一般性, 假设 $\mathrm EX = 0$. 考虑矩母函数的 Taylor 展式

$$\begin{aligned} \mathrm Ee^{tX} &= 1 + \frac{t^2}{2} \mathop{\mathrm{Var}}X + \sum _{k=3}^\infty \frac{t^k}{k!} \mathrm EX^k \\ &\leq 1 + \frac{t^2}{2} \mathop{\mathrm{Var}}X + \sum_{k=3}^\infty \frac{t^k b^{k-2}}{2} \mathop{\mathrm{Var}}X \\ &= 1 + \frac{t^2}{2} \mathop{\mathrm{Var}}X + \frac{t^2}{2} \mathop{\mathrm{Var}}X \sum_{k=3}^\infty (tb)^{k-2} \\ &= 1 + \frac{t^2}{2} \mathop{\mathrm{Var}}X + \frac{t^2}{2} \mathop{\mathrm{Var}}X \sum_{k=3}^\infty (|t|b)^{k-2} \\ &= 1 + \frac{t^2}{2} \mathop{\mathrm{Var}}X \cdot \frac{1}{1 - |t|b} \leq \exp \left( \frac{t^2 \mathop{\mathrm{Var}}X}{2(1-|t|b)} \right), \quad \forall |t| \leq \frac 1b \end{aligned}$$

考虑 Chernoff 界可以得到对应的集中不等式.

与 Hoeffding 不等式的比较 对于 i.i.d 的随机变量 $X_i$ 满足 $|X_i| \leq c$, Hoeffding 不等式指出

$$\Pr(|\bar X - \mathrm EX| \geq \varepsilon) \leq \exp \left( - \frac{n\varepsilon ^2}{2c^2} \right)$$

Bernstein 不等式指出

$$\Pr(|\bar X - \mathrm EX| \geq \varepsilon) \leq \exp \left( - \frac{n\varepsilon ^2}{2(c\varepsilon / 3 + \mathop{\mathrm{Var}}X)} \right)$$

可以看出, 若随机变量方差较小, Bernstein 不等式能给出更低的上界.

4 鞅、Azuma 不等式和 McDiarmid 不等式

4.1 鞅

鞅 假设 $\{X_n\}$ 是一个随机变量族. 在时刻 $n$, 新的随机变量 $Y_n = f(X_n, \dots, X_1)$ 由原随机变量生成. 称 $\{Y_n\}$ 是关于 $\{X_n\}$ 的鞅, 如果

$$\mathrm E(Y_n \mid \mathcal F_{n-1}) = Y_{n-1}$$

其中 $\sigma$-代数 $\mathcal F_{n-1}$ 表示 $X_{n-1}, \dots, X_1$ 包含的所有“信息” (非正式). 一族“信息”越来越多的 $\sigma$-代数 (例如 $\{\mathcal F_i\}$ 满足 $\mathcal F_{i-1} \subseteq \mathcal F_i$) 称为滤子 (filtration).

  鞅描述了“公平的赌博”: 就算赌徒获得了所有历史信息, 收益的期望也不会改变. 历史数据 $\mathcal F_{n-1}$ 对预测 $Y_n$ 没有贡献, 预测 $Y_n$ 的最佳方式仍是使用上一时刻的值 $Y_{n-1}$.

例 考虑随机游走. 令增量序列 $X_n = \pm 1$ 等概率, 则前缀和序列 $Y_n = \sum X_i$ 是增量序列的鞅. 这是因为

$$\mathrm E(Y_n \mid \mathcal F_{n-1}) = \mathrm E(Y_{n-1} \mid \mathcal F_{n-1}) + \mathrm E(X_n \mid \mathcal F_{n-1}) = 0 + Y_{n-1} = Y_{n-1}$$

  更进一步, 有

$$\mathrm E(Y_{n+k} \mid \mathcal F_{n-1}) = Y_{n-1}, \quad \forall k \geq 0$$

证明 全期望公式是

$$\mathrm EU = \mathrm E(\mathrm E(U\mid V))$$

将所有期望改为条件期望仍然成立

$$\mathrm E(U \mid W) = \mathrm E(\mathrm E(U\mid V, W)\mid W)$$

如果取 $U = Y_{n+1}$, $V = \mathcal F_n$, $W = \mathcal F_{n-1}$, 则

$$\mathrm E(Y_{n+1} \mid \mathcal F_{n-1}) = \mathrm E(\mathrm E(Y_{n+1} \mid \mathcal F_n)\mid \mathcal F_{n-1}) = \mathrm E(Y_n \mid \mathcal F_{n-1}) = Y_{n-1}$$

类似地

$$\mathrm E(Y_{n+2} \mid \mathcal F_{n-1}) = \mathrm E(\mathrm E(Y_{n+2} \mid \mathcal F_{n+1})\mid \mathcal F_{n-1}) = \mathrm E(Y_{n+1} \mid \mathcal F_{n-1}) = Y_{n-1}$$

以此类推可以归纳证明.

鞅差分 若 $\{Y_n\}$ 是 $\{X_n\}$ 的鞅, 则 $\{D_n = Y_n - Y_{n-1}\}$ 是 $\{X_n\}$ 的鞅差分. 它有一个等价定义, 即

$$\mathrm E(D_n \mid \mathcal F_{n-1}) = 0$$

反之, 若已知鞅差分 $\{D_n\}$, 可以还原鞅

$$Y_n = \sum _{i=1}^n D_i$$

4.2 Azuma 不等式

  假设给定一个鞅差分序列 $\{D_n\}$, 希望计算对应鞅 $Y_n = \sum_{i=1}^n D_i$ 的集中不等式. 考虑它的 Chernoff 界:

$$\begin{aligned} \Pr\left(\sum _{i=1}^n D_i \geq \varepsilon\right) &\leq e^{-t\varepsilon} \mathrm E\left(\exp t\sum _{i=1}^n D_i\right) \\ &= e^{-t\varepsilon} \mathrm E\left(\exp t\sum _{i=1}^{n-1} D_i \cdot e^{tD_n}\right) \\ &= e^{-t\varepsilon} \mathrm E\left(\mathrm E\left(\exp t\sum _{i=1}^{n-1} D_i \cdot e^{tD_n}\ \middle| \ \mathcal F_{n-1}\right) \right) \\ &= e^{-t\varepsilon} \mathrm E\left(\exp t\sum _{i=1}^{n-1} D_i \cdot \mathrm E\left(e^{tD_n}\ \middle| \ \mathcal F_{n-1}\right) \right) \\ \end{aligned}$$

Azuma 不等式 若 $\{D_i\}$ 是一个鞅差分满足 $a_i \leq D_i \leq b_i$, 则

$$\Pr\left(\sum _{i=1}^n D_i \geq \varepsilon\right) \leq \exp \left(-\frac{2\varepsilon ^2}{\sum_{i=1}^n (b_i - a_i)^2}\right)$$

证明 使用 Hoeffding 引理, 迭代展开得到

$$\begin{aligned} \Pr\left(\sum _{i=1}^n D_i \geq \varepsilon\right) &\leq e^{-t\varepsilon} \mathrm E\left(\exp t\sum _{i=1}^n D_i\right) \\ &\leq e^{-t\varepsilon} \mathrm E\left(\exp t\sum _{i=1}^{n-1} D_i \cdot \mathrm E\left(e^{tD_n}\ \middle| \ \mathcal F_{n-1}\right) \right) \\ &\leq e^{-t\varepsilon} \mathrm E\left(\exp t\sum _{i=1}^{n-1} D_i\right) \exp \frac{t^2(b_i-a_i)^2}{8} \\ &\leq \cdots \leq \exp \left(-t\varepsilon + \frac{t^2}{8} \sum_{i=1}^n (b_i-a_i)^2\right) \end{aligned}$$

这是一个二次函数求最小值问题. 取 $t = 4\varepsilon / \sum_{i=1}^n (b_i-a_i)^2$ 即得证.

例 考虑随机游走. 令 $X_i = \pm 1$ 等概率. 则 $Y_n = \sum X_i$ 是一个鞅. 它的鞅差分 $D_n = Y_n - Y_{n-1} = X_n$ 满足 $D_n \in [-1, 1]$. 因此

$$\Pr(Y_n \geq \varepsilon) \leq e^{-\varepsilon^2 / 2n}$$

进一步地, 取 $\varepsilon = \sqrt{2n\ln n}$, 可以得到

$$\Pr(Y_n \geq \sqrt{2n\ln n}) \leq \frac 1n \to 0, \quad n \to \infty$$

4.3 McDiarmid 不等式

有界差性质 称多元函数 $f(x_1, \dots, x_n)$ 满足有界差性质, 如果存在一组界 $\{c_i\}$, 使得任取 $x_i$ 和 $x_i'$ 在定义域内, 都有

$$|f(x_1, \dots, x_i, \dots, x_n) - f(x_1, \dots, x_i', \dots, x_n)| \leq c_i$$

Doob 鞅 令 $Y$ 是一个随机变量, $\{\mathcal F_i\}$ 是滤子, 定义

$$Z_i = \mathrm E(Y \mid \mathcal F_i)$$

则 $\{Z_i\}$ 也是鞅, 称为 Doob 鞅.

证明 只需使用全期望公式

$$\mathrm E(Z_i \mid \mathcal F_{i-1}) = \mathrm E(\mathrm E(Y \mid \mathcal F_i)\mid \mathcal F_{i-1}) = \mathrm E(Y \mid \mathcal F_{i-1}) = Z_{i-1}$$

McDiarmid 不等式 若 $\{X_i\}$ 相互独立, $f(x_1, \dots, x_n)$ 满足界为 $\{c_i\}$ 有界差性质, 则

$$\Pr(|f(X_1, \dots, X_n) - \mathrm Ef(X_1, \dots, X_n)| \geq \varepsilon) \leq 2 \exp \left(-\frac{2\varepsilon^2}{\sum c_i^2}\right)$$

证明 定义

$$Y_i = \mathrm E(f(X_1, \dots, X_n) \mid \mathcal F_i)$$

自然地, $Y_n = f(X_1, \dots, X_n)$, $Y_0 = \mathrm Ef(X_1, \dots, X_n)$. $\{Y_i\}$ 是一个 Doob 鞅. 进一步, $D_i = Y_i - Y_{i-1}$ 是一个鞅差分, 并且根据有界差性质的条件有 $(\max - \min) D_i \leq c_i$. 应用 Azuma 不等式, 有

$$\begin{aligned} & \Pr(|f(X_1, \dots, X_n) - \mathrm Ef(X_1, \dots, X_n)| \geq \varepsilon) \\ & \qquad = \Pr(|Y_n - Y_0| \geq \varepsilon) = \Pr\left(\left|\sum D_i\right| \geq \varepsilon\right) \leq 2 \exp \left(-\frac{2\varepsilon^2}{\sum c_i^2}\right) \end{aligned}$$

例 给定随机变量列 $\{X_i\}_{i=1}^n$ 满足 $a_i \leq X_i \leq b_i$, 给定函数 $f(X_1, \dots, X_n) = \sum X_i / n$, 计算它的 McDiarmid 不等式. 注意到 $|X_i - X_i'| \leq b_i - a_i$. 于是

$$|f(x_1, \dots, x_i, \dots, x_n) - f(x_1, \dots, x_i', \dots, x_n)| \leq \frac{b_i - a_i}{n}$$

即 $\{X_i\}$ 满足有界差性质, 且界为 $(b_i-a_i)/n$. 应用 McDiarmid 不等式,

$$\begin{aligned} & \Pr(|f(X_1, \dots, X_n) - \mathrm Ef(X_1, \dots, X_n)| \geq \varepsilon) = \Pr(|\bar X - \mathrm EX| \geq \varepsilon) \\ & \qquad \leq 2 \exp \left(-\frac{2\varepsilon^2}{\sum ((b_i-a_i)/n)^2}\right) = 2 \exp \left(-\frac{2n\varepsilon^2}{\sum (b_i-a_i)^2}\right) \end{aligned}$$

这正是 Hoeffding 不等式.

参考文献

• Lin, Zhengyan (2010). Probability inequalities. Springer.
• CSDN: 一碗姜汤. 【数理统计03】集中不等式. https://blog.csdn.net/weixin_55252589/article/details/139245289.
• Wikipedia. Markov's inequality. https://en.wikipedia.org/wiki/Markov%27s_inequality.
• 哔哩哔哩: jamesyu420. 高维统计：集中不等式—Concentration inequality. https://www.bilibili.com/video/BV17D4y1z7Me.
• University of Washington: Alex Tsun. The Cherno Bound. https://courses.cs.washington.edu/courses/cse312/20su/files/student_drive/6.2.pdf.
• 知乎: 徐亦达教授. 通俗易懂的机器学习数学. https://www.zhihu.com/column/c_1762978335020597248.
• StackExchange. How to verify chi-square random variables are sub-exponential variables? https://math.stackexchange.com/questions/4325061/how-to-verify-chi-square-random-variables-are-sub-exponential-variables.
• University of Oxford: Patrick Rebeschini. Bernsteins Concentration Inequalities. https://www.stats.ox.ac.uk/~rebeschi/teaching/AFoL/22/material/lecture07.pdf.