工具：切尔诺夫不等式

Chernoff不等式（或称Chernoff界）是概率论中一个非常有力的工具，它描述了一个独立随机变量之和偏离其期望值的概率。相比于马尔可夫不等式或切比雪夫不等式，Chernoff界给出的概率上界通常是指数级的，因此在理论计算机和组合数学中应用极为广泛。

核心思想：大偏差是罕见的

Chernoff不等式的核心思想非常直观：一个随机过程的结果，离它的平均水平（期望）越远，这个结果出现的可能性就越小，而且是以指数方式变小的。

抛硬币场景中：

• 抛10次，期望是5次正面。出现6次正面很正常，但出现10次正面就相当罕见。
• 抛1000次，期望是500次正面。出现510次正面很正常，但出现600次正面（偏差20%）就几乎不可能了。

Chernoff界就是将这种直觉精确化的数学工具。

---

Chernoff不等式的形式与理解

Chernoff不等式有多种形式，但它们都围绕着同一个结构。设 $X_1, X_2, \dots, X_n$ 是一系列独立的伯努利随机变量（即取值为0或1），令 $P(X_i=1) = p_i$。
令它们的和为 $X = \sum_{i=1}^n X_i$，其期望值为 $\mu = E[X] = \sum_{i=1}^n p_i$。

1. 上尾界 (Upper Tail): 随机变量远大于期望

我们想知道 $X$ 比它的期望 $\mu$ 大很多的概率是多少。

乘法形式 (Multiplicative Form)
对于任意的 $\delta > 0$，我们有：

$$P(X \ge (1+\delta)\mu) \le \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^\mu$$

• 理解:
  • 偏差因子 $\delta$: 这个 $\delta$ 是关键。它衡量了你想观察的值相对于期望“超出”了多少个百分比。
    • $\delta = 0.1$ 表示超出期望10%。
    • $\delta = 1$ 表示达到了期望的2倍。
  • 概率上界: 这个上界是一个小于1的数（即 $\frac{e^\delta}{(1+\delta)^{1+\delta}}$）的 $\mu$ 次方。
  • 关系: 这清晰地表明，期望 $\mu$ 越大，或者偏差因子 $\delta$ 越大，概率上界就会指数级地减小。

一个更简单、更常用的版本
为了方便使用，上面的公式通常被放缩成更简洁的形式：

$$P(X \ge (1+\delta)\mu) \le e^{-\frac{\delta^2 \mu}{2+\delta}}$$

当 $0 < \delta \le 1$ 时，这个界可以进一步简化为：

$$P(X \ge (1+\delta)\mu) \le e^{-\frac{\delta^2 \mu}{3}} \quad (\text{常用版本1})$$

当 $\delta$ 很大时（例如 $\delta > 2e-1$），有：

$$P(X \ge (1+\delta)\mu) \le 2^{-(1+\delta)\mu} \quad (\text{常用版本2})$$

2. 下尾界 (Lower Tail): 随机变量远小于期望

我们想知道 $X$ 比它的期望 $\mu$ 小很多的概率是多少。对于 $0 < \delta < 1$:

$$P(X \le (1-\delta)\mu) \le \left( \frac{e^{-\delta}}{(1-\delta)^{1-\delta}} \right)^\mu$$

同样，它也有更简洁的常用版本：

$$P(X \le (1-\delta)\mu) \le e^{-\frac{\delta^2 \mu}{2}} \quad (\text{常用版本3})$$

总结

• 核心参数: 偏差因子 $\delta$ 和期望 $\mu$。
• 偏差大小与概率的关系:
  • 常数级偏差 ($\delta \ge \text{const} > 0$): 概率以 $e^{-\Omega(\mu)}$ 的速度指数衰减。这是最理想的情况，能得到非常强的结论。
  • 小偏差 ($\delta \to 0$): 概率衰减速度变慢，上界变弱。
• 当需要证明一个坏事件发生的概率极小，特别是当这个坏事件可以表示为一个大偏差事件，并且需要用联合界（Union Bound）来处理大量的潜在坏事件时，Chernoff不等式是首选工具。