Proof: 首先回憶 $X \sim exp(\lambda)$ 具有 機率密度
\[f_X\left( x \right): = \left\{ \begin{gathered}
\lambda {e^{ - \lambda x}}\begin{array}{*{20}{c}}
{}&{x \geqslant 0}
\end{array} \hfill \\
0\begin{array}{*{20}{c}}
{}&{x < 0}
\end{array} \hfill \\
\end{gathered} \right.\]故 $\lambda =1$ 我們有
\[f_X\left( x \right): = \left\{ \begin{gathered}
{e^{ - x}}\begin{array}{*{20}{c}}
{}&{x \geqslant 0}
\end{array} \hfill \\
0\begin{array}{*{20}{c}}
{}&{x < 0}
\end{array} \hfill \\
\end{gathered} \right.\] 現在我們計算
\[
P\left( {X \geqslant a} \right) = \int_a^\infty {{e^{ - x}}dx} = - \left( {0 - {e^{ - a}}} \right) = {e^{ - a}}
\]
接著我們用 Markov inequality 估計：令 $a>0$則
\begin{align*}
P\left( {X \geqslant a} \right) &\leqslant \frac{{E\left[ X \right]}}{a} \hfill \\
&= \frac{1}{a}\int_0^\infty {x{e^{ - x}}dx} \hfill \\
&= \frac{1}{a}
\end{align*}
再來是利用 Chebyshev inequalty 估計：
\begin{align*}
P\left( {X \geqslant a} \right)& \leqslant \frac{{E\left[ {{X^2}} \right]}}{{{a^2}}} \hfill \\
&= \frac{1}{{{a^2}}}\int_0^\infty {{x^2}{e^{ - x}}dx} \hfill \\
&= \frac{2}{a^2}
\end{align*}
最後用 Chernoff bounds
\[P\left( {X \geqslant a} \right) \leqslant \mathop {\min }\limits_{s \geqslant 0} {e^{ - sa}}{M_X}\left( s \right)\]其中$M_X(s)$ 為 moment generating function 滿足
\[{M_X}\left( s \right): = E\left[ {{e^{sX}}} \right] = \int_0^\infty {{e^{sx}}{e^{ - x}}dx} = \frac{1}{{1 - s}}\]故欲求 Chrnoff bound 我們需要求解下列最佳化問題
\[\begin{gathered}
\min {e^{ - sa}}{M_X}\left( s \right) \hfill \\
{\text{subject to }}s \geqslant 0 \hfill \\
\end{gathered} \]此問題等價於
\[\begin{gathered}
\min \frac{{{e^{ - sa}}}}{{1 - s}} \hfill \\
{\text{subject to }}s \geqslant 0 \hfill \\
\end{gathered} \]現在我們考慮當 $s \in (0,1)$ 時，我們可求對 $\frac{{{e^{ - sa}}}}{{1 - s}}$ 求一階導數並令其為零，來得到臨界點，亦即
\begin{align*}
& \frac{d}{{ds}} \left( \frac{1}{{1 - s}}{e^{ - sa}} \right)= 0 \hfill \\
&\Rightarrow \frac{{{e^{ - as}}}}{{{{(1 - s)}^2}}} - \frac{{a{e^{ - as}}}}{{1 - s}} = 0 \hfill \\
& \Rightarrow s = 1 - \frac{1}{a} \hfill \\
\end{align*} 注意到上式中我們要求 $a > 1$否則 $s<0$ 違反最佳化問題的 拘束條件。 再者我們驗證二階導數
\[{\left. {\frac{{{d^2}}}{{d{s^2}}}\left( {\frac{1}{{1 - s}}{e^{ - sa}}} \right)} \right|_{s = 1 - 1/a}} = {a^3}{e^{ - \left( {1 - \frac{1}{a}} \right)a}} > 0\]
故可知 $s=1-1/a$ 為 local minimum。我們將其記作
\[
s^* := 1 - \frac{1}{a}
\]現在將其帶回 Chernoff bound 並計算
\begin{align*}
P\left( {X \geqslant a} \right) &\leqslant \mathop {\min }\limits_{s \geqslant 0} {e^{ - sa}}{M_X}\left( s \right) \hfill \\
&= {e^{ - {s^*}a}}{M_X}\left( {{s^*}} \right) \hfill \\
&= {e^{1 - a}}a
\end{align*} 下圖顯示了當 $a \in [1,6]$ 時候，不同上界估計的圖形
上圖顯示在 $a in [1,6]$ 之間，各類機率上界估計互有輸贏。
現在我們考慮 $a \in [6,20]$ 並繪製 log-plot 可得下圖
上圖可發現當 $a$ 夠大，則 Chernoff bound 展現壓倒性的優勢。一般而言，當 $a$ 夠大的時候$P(X \geq a)$ 的上界估計採用 Chernoff bound 大多優於 Markov inequality 或者 Chebyshev inequality 是非常不錯的選擇。
附註：關於 Chernoff bound 可以非常容易地從 Markov inequality 推得：令 $s \geq 0$ 現在觀察以下事件
\[
\{X \geq a\} = \{s X \geq sa\} = \{e^{sX} \geq e^{sa}\}
\]故若對上述事件取機率可得
\[
P(X \geq a) = P(e^{sX} \geq e^{sa})
\]由於$s \geq 0$我們有 $e^{sX} \geq 0$ 且 $e^{sa} >0$ 對任意 $a$，故利用 Markov inequality可推得
\[
P(e^{sX} \geq e^{sa}) \leq \frac{E[e^{sX}]}{e^{sa}}
\]亦即
\[
P(X \geq a) \leq \frac{E[e^{sX}]}{e^{sa}} , \;\; \forall s \geq 0
\]由於上述不等式對任意 $s\geq 0$成立，且不等式左方與 $s$ 無關，故可知
\[
P(X \geq a) \leq \min_{s \geq 0 }\frac{E[e^{sX}]}{e^{sa}}
\]也就是 Chernoff bound。
沒有留言:
張貼留言