モーメント母関数を使わないChernoff boundの証明

Chernoff boundは, 独立な確率変数$X_1,\dots,X_n$の和$X_1+\dots+X_n$が期待値から外れる確率が$n$に関して指数的に小さくなることを主張する不等式です. Chernoff boundの証明はモーメント母関数$\mathbf{E}[\exp(\lambda X)]$の評価し, それとマルコフの不等式を組み合わせることで与えられます (例えばこのページ参照)

本記事ではImpagliazzoとKabanets(2010)によって与えられた面白い証明を紹介します.

定理.

$X_1,\dots,X_n$を$\{0,1\}$値をとる独立な確率変数で$\mathbf{E}[X_1]=p$とする. 任意の$c>0$に対して

$$\begin{align*} \Pr[X_1+\dots+X_n\geq cn] \leq \mathrm{e}^{-nD(c||p)}.\end{align*}$$

ここで, $D(c||p)=c\log\frac{c}{p} + (1-c)\log\frac{1-c}{1-p}\geq 2(c-p)^2$.

(証明)

パラメータ$q\in[0,1]$に対し, 各$i\in[n]$を独立に確率$q$で含むランダムな部分集合$S$を考え, 確率変数

$$\begin{align*}Z = \prod_{i\in S}X_i \end{align*}$$

とします ($S$と$X$のランダムネスを考える). 定義より

$$\begin{align*}\mathbf{E}[Z]&=\mathbf{E}_S\left[\mathbf{E}_X\left[\prod_{i\in S}X_i\right]\right] \\ &= \mathbf{E}_S\left[p^{|S|}\right] \\ &= (qp+1-q)^n.\end{align*}$$

$\mathcal{E}$を$X_1+\dots+X_n\geq cn$という事象とします. $\mathcal{E}$で条件づけたとき,

$$\begin{align*}\mathbf{E}[Z|\mathcal{E}] &= \mathbf{E}_X\left[\mathbf{E}_S\left[\prod_{i\in S}X_i\middle|\mathcal{E}\right]\middle|\right] \\ &=\mathbf{E}_X\left[\Pr_S[\overline{S}\text{ contains all }i\text{ satisfying }X_i=0|\mathcal{E}]\middle|\mathcal{E}\right] \\ &\geq (1-q)^{(1-c)n}.\end{align*}$$

最後の不等式は, $\mathcal{E}$で条件づけたときに$X_i=0$となる$i$は高々$(1-c)n$個あり, それら全てが$\overline{S}$に含まれる確率で下から抑えることで得ています.

条件付き期待値の性質から$\mathbf{E}[Z]\geq\mathbf{E}[Z|\mathcal{E}]\Pr[\mathcal{E}]$より

$$\begin{align*}\Pr[X_1+\dots+X_n\geq cn]\leq \frac{(pq+1-q)^n}{(1-q)^{(1-c)n}}\end{align*}$$

を得ます. 右辺は$q=\frac{c-p}{c(1-p)}$のとき最小となり, $\mathrm{e}^{-D(c||p)}$となる. (証明終)

参考文献

R. Impagliazzo and V. Kabanets, Constructive Proofs of Concentration Bounds, RANDOM2010.