Chernoff Bound

2018-10-10 本文已影响0人 Corn_48ad

若 $X_i$ 是相互独立的Bernoulli变量， $E(X_i) = p_i$ ，记 $X=\sum X_i$ ， $\mu = E(X)$ 那么，我们有concentration表达式：

$P(X > (1+\delta)\mu) <= e^{-\frac{\delta^2}{3}}$ .

证明方法：

$P(X > (1+\delta)\mu) = P(e^{tX} > e^{(1+\delta)t\mu}) <\frac{E(e^{tX})}{e^{(1+\delta)t\mu}}$

而求解 $E(e^{tX})$ 需要 $X_i$ 的独立性，变成乘积形式。

$E(e^{tX}) = E(e^{t\sum_{i=1}^n X_i}) = \prod E(e^{tX_i})$

$E(e^{tX_i}) = p_ie^t+1-p_i = 1+p_i(e^t-1) \leq e^{p_i(e^t-1)}$

$E(e^{tX}) \leq e^{\mu(e^t-1)}$

$P(X > (1-\delta)\mu) < (\frac{e^{e^t-1}}{e^{(1+\delta)t}})^\mu$ 。求导可知当 $t = \log(1+\delta)$ 时，取最大值 $(\frac{e^{-\delta}}{(1+\delta)^{(1+\delta)}})^{\mu}$ 。

Chernoff Bound

猜你喜欢

热点阅读