Chernoff Boundsで遊んでみよう！
Markov's Inequality
$X$を任意の確率変数とし、$a>0$とする。
\begin{equation} \text{Pr}(\left|X\right|\geq a) \leq \dfrac{\text{E}[X]}{a} \end{equation}
Chernoff Bounds
Markov's Inequalityより、Chernoff Boundsが得られる。
任意の$t>0$について、
\begin{equation} \text{Pr}(X\geq a) = \text{Pr}(e^{tX}\geq e^{ta})\leq \dfrac{\text{E}[e^{tX}]}{e^{ta}} \end{equation}
同様に、任意の$t<0$について、
\begin{equation}
\text{Pr}(X\leq a) = \text{Pr}(e^{tX}\geq e^{ta})\leq \dfrac{\text{E}[e^{tX}]}{e^{ta}}
\end{equation}
Chernoff Boundsの応用
$X_1,\cdots,X_n$を独立な確率変数とする。
$\text{Pr}(X_i=1)=\text{Pr}(X_i=-1)=1/2$とする。
このとき、$X=\sum_{i=1}^{n}X_i$とする。
任意の$a>0$について、
\begin{equation}
\text{Pr}(|X|\geq a)\leq 2e^{-a^2/2n}
\end{equation}
任意のt>0について、
\begin{equation}
\text{E}[e^{tX_i}]=\dfrac{1}{2}e^t+\dfrac{1}{2}e^{-t}
\end{equation}
$e^t$と$e^{-t}$をマクローリン展開をして、
\begin{equation} e^t = 1+t+t^2/2!+\cdots+t^i/i!+\cdots \end{equation}
\begin{equation} e^{-t} = 1-t+t^2/2!+\cdots+(-1)^it^i/i!+\cdots \end{equation}
$(2i)!=2i(2i-1)(2i-2)\cdots\geq2^ii(i-1)(i-2)\cdots=2^i(i)!$に注意して、
\begin{eqnarray} \text{E}[e^{tX_i}] &=& \dfrac{1}{2}e^t+\dfrac{1}{2}e^{-t}\\ &=& \sum_{i\geq 0}t^{2i}/(2i)!\\ &\leq& \sum_{i\geq 0}(t/2)^{i}/i!\\ &=& e^{t^2/2} \end{eqnarray}
$\text{E}[e^{tX}] =\text{E}[e^{t\sum_iX_i}] =\prod_{i=1}^{n}\text{E}[e^{tX_i}] \leq e^{nt^2/2} $
それゆえ、
$\text{Pr}(X\geq a)=\text{Pr}(e^{tX}\geq e^ta)\leq\text{E}[e^tX]/e^{ta}\leq e^{t^2n/2-ta}$
$t=a/n$とおけば、
\begin{equation}
\text{Pr}(X\geq a)\leq e^{-a^2/2n}
\end{equation}
同様にして、
\begin{equation}
\text{Pr}(X\leq -a)\leq e^{-a^2/2n}
\end{equation}
よって、任意の$a>0$について、
\begin{equation}
\text{Pr}(|X|\geq a)\leq 2e^{-a^2/2n}
\end{equation}
