一句話解釋

對獨立 0/1 隨機變數的和，給出比 Chebyshev 更緊的尾部機率上界。

直覺理解

直覺理解

Markov 和 Chebyshev 只用到期望值或變異數，丟掉了大量資訊。Chernoff 的想法是：對任意 $\lambda > 0$，把事件 ${X \geq t}$ 換成 ${e^{\lambda X} \geq e^{\lambda t}}$，再對 $e^{\lambda X}$ 用 Markov。

指數函數會把尾部「放大」，讓上界隨 $t$ 指數衰減，而不是像 Chebyshev 的多項式衰減。最後再對 $\lambda$ 取最優值，讓上界盡可能緊。

數學推導

數學推導

設定

令 $X_1, \dots, X_n$ 獨立，$X_i \in {0,1}$，$\Pr[X_i=1]=p_i$。令 $X = \sum X_i$，$\mu = \mathbb{E}[X]$。

推導步驟

1 $$\Pr[X \geq (1+\delta)\mu] = \Pr\!\left[e^{\lambda X} \geq e^{\lambda(1+\delta)\mu}\right]$$ 改寫事件
2 $$\leq \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda(1+\delta)\mu}}$$ Markov 不等式
3 $$= \frac{\prod_i \mathbb{E}[e^{\lambda X_i}]}{e^{\lambda(1+\delta)\mu}}$$ 獨立性 → MGF 可分解
4 $$\leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu$$ 取最優 λ，化簡

常用形式（$\delta \leq 1$）

上尾（Upper Tail）： $$\Pr[X \geq (1+\delta)\mu] \leq e^{-\mu\delta^2/3}$$ 下尾（Lower Tail）： $$\Pr[X \leq (1-\delta)\mu] \leq e^{-\mu\delta^2/2}$$

前提條件 / 適用範圍

前提條件 / 適用範圍
  • ✓ $X_i$ 彼此獨立
  • ✓ $X_i \in \{0,1\}$（或有界）
  • ✓ $\delta \in (0,1]$（常用形式）
  • ✗ $X_i$ 有相關性時不能直接套用
  • ✗ 無界的連續分佈需改用 Hoeffding 或 Bernstein

範例：硬幣投擲

問題

投擲 $n=1000$ 次公平硬幣，出現正面的次數 $X$ 超過 $600$ 次的機率上界？

解答

  • $\mu = np = 1000 \times 0.5 = 500$
  • 要求 $\Pr[X \geq 600] = \Pr[X \geq (1+0.2) \times 500]$
  • 這裡 $\delta = 0.2$

使用 Chernoff Bound（上尾）：

\[\Pr[X \geq 600] \leq e^{-500 \times (0.2)^2 / 3} = e^{-500 \times 0.04/3} \approx e^{-6.67} \approx 0.0013\]

結論：超過 600 次的機率小於 0.13%，非常不可能發生。

與 Chebyshev 比較

Chebyshev 給出：

\[\Pr[|X - 500| \geq 100] \leq \frac{\text{Var}(X)}{100^2} = \frac{250}{10000} = 0.025\]

Chernoff 的上界（$\approx 0.0013$）遠比 Chebyshev（$\approx 0.025$）緊！

與其他概念的關係

相關概念
Markov Inequality
推導基礎，第一步就用到
Chebyshev Inequality
Chernoff 更緊，條件也更多
MGF (Moment Generating Function)
核心工具，獨立性讓 MGF 可分解
Hoeffding Bound
有界但非 0/1 的推廣版本

參考資料