切诺夫界 · 概率论、数理统计与信息论 02

关键字概率论数理统计信息论马尔可夫不等式Markov’s Inequality切比雪夫不等式Chebyshev’s Inequality切尔诺夫界Chernoff Bounds算法基础

摘要 —— 本文将回答概率论中的一个重要问题:对于给定的随机变量,和期望值相差给定距离的取值发生的概率是多少?对此,我们有三个结论,分别是马尔可夫不等式、切比雪夫不等式和切诺夫界。随着对随机变量的独立性的要求提高,这三个结论对于这个概率的估计也愈加准确。

对于给定的随机变量,和期望值相差给定距离的取值发生的概率是多少?为了回答这个问题,本文将依次介绍马尔可夫不等式、切比雪夫不等式和切诺夫界。

1 马尔可夫不等式

1.1 结论

令 $Z$ 是非负的、整数随机变量,则

$$ \forall a \in \mathbb{R}^+: \Pr [Z \geq a] \leq \frac{\mathbb{E}[Z]}{a} $$

Proof #1:如图 1 所示,显然有 $z \cdot \Pr [Z \geq z] \leq \mathbb{E} [Z]$,变形可得结论。


图 1 马尔可夫不等式的一种简易证明。

Proof #2:因为 $\Pr [Z \geq a] = \int_a^\infty f(z) dz$ 且当 $z \geq a$ 时显然有 $\frac{z}{a} \geq 1$,故

$$ \Pr [Z \geq a] = \int_a^\infty f(z) dz \leq \int_a^\infty \frac{z}{a} f(z) dz $$ 此外,

$$ \frac{\mathbb{E}[Z]}{a} = \mathbb{E}\bigg[\frac{Z}{a}\bigg] = \int_0^\infty \frac{z}{a} f(z) dz = \int_0^a \frac{z}{a} f(z) dz + \int_a^\infty \frac{z}{a} f(z) dz \geq \int_a^\infty \frac{z}{a} f(z) dz $$ 联立两式可得结论。

1.2 推论

基于马尔科夫不等式,可以得到和期望相差一定距离的随机变量的取值发生的概率的上限:

$$ \Pr \Big[Z \geq (1 + \delta) \mathbb{E}[Z] \Big] \leq \frac{1}{1 + \delta} $$

2 切比雪夫不等式

2.1 形式 1

对于一组指示(随机)变量 $X_1, X_2, ..., X_n \in \{0,1\}$,令 $p_i = \mathbb{E} [X_i] = \Pr [X_i = 1]$。定义 $X = \sum_i X_i$,定义 $\mu = \mathbb{E}[X] = \sum_i p_i$。如果 $X_1, X_2, ..., X_n$ 成对独立,则

$$ \Pr \Big[(X - \mu)^2 \geq z\Big] < \frac{\mu}{z} $$

Proof:$\forall i$,定义 $Y_i = X_i - p_i$,定义 $Y = \sum_i Y_i = X - \mu$。则

\begin{aligned} \mathbb{E} [Y^2] = \mathbb{E} \Big[\sum_{i,j} Y_i \cdot Y_j \Big] = \sum_{i} \mathbb{E} [Y_i^2] + \sum_{i \neq j} \mathbb{E} [Y_i \cdot Y_j] \\ = \sum_{i} \mathbb{E} [Y_i^2] + \sum_{i \neq j} \mathbb{E} [Y_i] \cdot \mathbb{E} [Y_j] \qquad \triangleright \textrm{成对独立} \\ = \sum_{i} \mathbb{E} [Y_i^2] \qquad \triangleright \forall i, \mathbb{E} [Y_i] = 0 \end{aligned}

对 $\sum_{i} \mathbb{E} [Y_i^2]$ 展开可得:$\sum_i \mathbb{E} [Y_i^2] = \sum_{i} (1 - p_i)^2 \cdot p_i + (- p_i)^2 \cdot (1 - p_i) = \sum_i p_i (1 - p_i) < \sum_i p_i = \mu$。因此,可得 $\mathbb{E}[Y^2] < \mu$。

带入马尔可夫不等式可得

$$ \Pr [Y^2 \geq z] \leq \frac{\mathbb{E} [Y^2]}{z} < \frac{\mu}{z} $$ 证毕。

2.2 推论 1

$\forall \Delta, \delta \in \mathbb{R}^+$,有

\begin{aligned} \Pr \big[X \geq \mu + \Delta \big] < \frac{\mu}{\Delta^2} \qquad \Pr \big[X \geq (1 + \delta) \mu \big] < \frac{1}{\delta^2 \mu} \\ \Pr \big[X \leq \mu - \Delta \big] < \frac{\mu}{\Delta^2} \qquad \Pr \big[X \leq (1 - \delta) \mu \big] < \frac{1}{\delta^2 \mu} \end{aligned}

以上结论通过带入 $z = \Delta^2$、$\Delta = \delta \mu$ 到切比雪夫不等式来证明。

2.3 推论 2

将随机变量 $X_1, X_2, ..., X_n \in \{0,1\}$ 解读为 $n$ 次重复独立试验,即 $\Pr [X_i = 1] = p$,此时 $\mu = n p$。令 $\bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i$ 为前 $n$ 次重复独立试验的样本均值,则可以得到弱大数定理:

$$ \lim_{n \to \infty} \Pr \Big[|\bar{X}_n - p| \geq \epsilon \Big] = 0 $$

2.4 形式 2

对于随机变量 $X$,定义 $\mu = \mathbb{E} [X]$,$\sigma = \sqrt{\textrm{Var}(X)}$,则

$$ \Pr \Big[|X - \mu| \geq k \sigma \Big] \leq \frac{1}{k^2}, \quad k > 0 $$

Proof:定义 $Y = |X - \mu| > 0$,则由马尔可夫不等式可得 $\Pr [|X - \mu| \geq a] < \frac{\mathbb{E} [|X - \mu|]}{a}$,两边同时平方可得

$$ \Pr \Big[|X - \mu| \geq a \Big] \cdot \Pr \Big[|X - \mu| \geq a \Big] < \frac{\mathbb{E} \big[|X - \mu| \big] \cdot \mathbb{E} \big[|X - \mu| \big]}{a^2} $$

$X - \mu$ 的本质是样本的测量误差,每次测量都服从独立同分布(其实是正态分布),又因为对于给定的 $f(⋅)=|⋅|$ 仍然有 $|X-\mu|$ 服从独立同分布,所以 $\mathbb{E} \big[|X - \mu| \big] \cdot \mathbb{E} \big[ |X - \mu| \big] = \mathbb{E} \big[(X - \mu)^2 \big] = \sigma^2$(这里运用了随机变量的独立性)。

对于前后两次测量,事件 $\{\omega \in \Omega \mid |X(\omega) - \mu| \geq a \}$ 和 $\{ \omega \in \Omega \mid |X(\omega) - \mu| \geq a \}$ 独立,所以 $\Pr \big[|X - \mu| \geq a \big] \cdot \Pr \big[ |X - \mu| \geq a \big] = \Pr \big[ |X - \mu| \geq a \wedge |X - \mu| \geq a \big] = \Pr \big[| X - \mu| \geq a \big]$。所以

$$ \Pr \Big[|X - \mu| \geq a \Big] < \frac{\sigma^2}{a^2} $$

令 $a = \frac{k}{\sigma}$ 即可得到结论。证毕。

可以发现,切比雪夫不等式比马尔科夫不等式更加精确。

3 Higher Moment Inequalities

结论 :切比雪夫不等式成立的条件是要求 $X_1,X_2,...,X_n$ 成对独立,即 2$k$-wise independent 且 $k=1$。如果 $X_1,X_2,...,X_n$ 满足 $2k$-wise independent,则

$$ \Pr \Big[(X - \mu)^k \geq z\Big] \leq \mathcal{O} \bigg(\frac{\mu^k}{z}\bigg) $$

其中 $\mathcal{O} (\cdot)$ 中的隐藏参数与 $k$ 有关。

推论 :$\forall \Delta, \delta \in \mathbb{R}^+$,有

\begin{aligned} \Pr \big[X \geq \mu + \Delta \big] = \mathcal{O} \Bigg( \bigg(\frac{\mu}{\Delta^2} \bigg)^k \Bigg) \qquad \Pr \big[X \geq (1 + \delta) \mu \big] = \mathcal{O} \Bigg( \bigg( \frac{1}{\delta^2 \mu} \bigg)^k \Bigg) \\ \Pr \big[X \leq \mu - \Delta \big] = \mathcal{O} \Bigg( \bigg(\frac{\mu}{\Delta^2} \bigg)^k \Bigg) \qquad \Pr \big[X \leq (1 - \delta) \mu \big] = \mathcal{O} \Bigg( \bigg( \frac{1}{\delta^2 \mu} \bigg)^k \Bigg) \end{aligned}

这个推论通过将 $z = \Delta^2$、$\Delta = \delta \mu$ 带入上面的结论得到。

4 切诺夫界

4.1 引理

如果一组随机指示变量 $X_1,X_2,...,X_n$ 相互独立,令 $X = \sum_i X_i$,$\mu = \mathbb{E} [X] = \sum_i p_i$,则

$$ \forall \alpha \geq 1, \quad \mathbb{E} [\alpha^X] \leq e^{(\alpha - 1) \mu} $$

Proof:显然 $\mathbb{E} [\alpha^{X_i}] = p_i \alpha + (1 - p_i) = (\alpha - 1) p_i + 1$,因为 $1 + t \leq e^t$ 恒成立,所以 $\mathbb{E} [\alpha^{X_i}] \leq e^{(\alpha - 1) p_i}$。根据随机变量 $X_1,X_2,...,X_n$ 相互独立的性质可以得到

$$ \mathbb{E} [\alpha^X] = \mathbb{E} \Big[\alpha^{\sum_i X_i} \Big] =\prod_i \mathbb{E} \big[\alpha^{X_i} \big] \leq e^{(\alpha - 1)\mu} $$

4.2 切尔诺夫界 - upper tail

如果随机变量 $X_1,X_2,...,X_n$ 相互独立,则

$$ \forall x \geq \mu, \quad \Pr [X \geq x] \leq e^{x - \mu} \bigg( \frac{\mu}{x} \bigg)^x $$

Proof:当固定住 $x$ 且满足 $\frac{x}{\mu} \geq 1$,函数 $f: t \to \big( \frac{x}{\mu} \big)^t$,所以 $\Pr [X \geq x] = \Pr [(\frac{x}{\mu})^X \geq (\frac{x}{\mu})^x]$。根据马尔可夫不等式有

$$ \Pr \bigg[(\frac{x}{\mu})^X \geq (\frac{x}{\mu})^x \bigg] \leq \frac{\mathbb{E} \big[(\frac{x}{\mu})^X \big]}{(\frac{x}{\mu})^x} $$

根据引理可得 $\mathbb{E} \big[(\frac{x}{\mu})^X \big] \leq e^{x - \mu}$,所以可得 $\Pr [X \geq x] \leq e^{x - \mu} \big( \frac{\mu}{x} \big)^x$。

4.3 切尔诺夫界 - lower tail

如果随机变量 $X_1,X_2,...,X_n$ 相互独立,则

$$ \forall x \leq \mu, \quad \Pr \big[ X \leq x \big] \leq e^{x - \mu} \bigg( \frac{\mu}{x} \bigg)^x $$

Proof:固定住 $x$ 且满足 $\frac{x}{\mu} \leq 1$,则 $\Pr [X \leq x] = \Pr \Big[(\frac{x}{\mu})^X \geq (\frac{x}{\mu})^x \Big]$。剩余部分的证明和上面一样。

4.4 推论 1

将 $\frac{\mu}{x}$ 替换为 $\alpha$ 则有

\begin{aligned} \forall \alpha > 1: \quad \Pr \big[X \geq x \big] \leq \frac{e^{(\alpha - 1) \mu}}{\alpha^x} \\ \forall \alpha < 1: \quad \Pr \big[X \leq x \big] \leq \frac{e^{(\alpha - 1) \mu}}{\alpha^x} \end{aligned}

可验证上述二式在 $\alpha = \frac{\mu}{x}$ 时取等。

4.5 推论 2

$\forall \Delta, \delta \in \mathbb{R}^+$,有

\begin{aligned} \Pr \big[X \geq \mu + \Delta \big] \leq e^\Delta \bigg( \frac{\mu}{\mu + \Delta} \bigg)^{\mu + \Delta} \qquad \Pr \big[X \geq (1 + \delta) \mu \big] \leq \bigg( \frac{e^\delta}{(1 + \delta)^{1 + \delta}} \bigg)^\mu \\ \Pr \big[X \leq \mu - \Delta \big] \leq e^{-\Delta} \bigg( \frac{\mu}{\mu - \Delta} \bigg)^{\mu - \Delta} \qquad \Pr \big[X \leq (1 - \delta) \mu \big] \leq \bigg( \frac{e^{-\delta}}{(1 - \delta)^{1 - \delta}} \bigg)^\mu \end{aligned}

分别令 $x = \mu + \Delta$、$x = \mu - \Delta$、$\Delta = \delta \mu$,带入推论 1 可得。

4.6 推论 3

进一步地,还有更为松散的上界:

\begin{aligned} \Pr [X \geq (1 + \delta) \mu] \leq \exp \bigg(- \frac{\delta^2 \mu}{3} \bigg) \\ \Pr [X \leq (1 - \delta) \mu] \leq \exp \bigg(- \frac{\delta^2 \mu}{2} \bigg) \end{aligned}

Proof:将函数 $f(x) = \ln (x + 1)$,$x \geq -1$,在 $x = 0$ 处展开,得到

$$ f(x) \geq f(0) + f'(0) (x - 0) + \frac{f''(0)}{2} (x - 0)^2 $$

带入可得 $\ln (x + 1) \geq x - \frac{1}{2} x^2$。将 $x$ 替换为 $-\delta$ 并限定 $\delta \in [0,1]$ 得到 $\ln (1 - \delta) \geq - \delta + \frac{\delta^2}{2}$。代回推论 2 中右下方公式即可得本推论的公式 2。

此外,又因为 $\frac{1}{\ln (1 + x)} \leq \frac{1}{x (1 - \frac{1}{2} x)} = \frac{1}{x} + \frac{1}{2- x}$,将 $x$ 替换为 $\delta$ 并限定 $\delta \in [0,1]$ 可得 $\frac{1}{\delta} + \frac{1}{2 - \delta} \leq \frac{1}{\delta} + \frac{1}{2}$,所以可得 $\frac{1}{\ln (1 + \delta)} \leq \frac{1}{2} + \frac{1}{\delta}$。代回推论 2 中右上方公式即可得本推论的公式 1。

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可, 转载时请注明原文链接。您必须给出适当的署名,并标明是否对本文作了修改。

您也可以通过下方按钮直接分享本页面:


发表评论

登录以发表评论

最新评论


Designed & written by Hailiang Zhao.
hliangzhao.cn. Copyright © 2021 - 2022 | 浙ICP备2021026965号-1
Manage