[機率論] 一些常用的機率上界估計-以 exponential 隨機變數為例

令 $X$ 為 exponential 隨機變數配備參數 $\lambda =1$，亦即 $X \sim exp(1)$。試求 $P(X\geq a)$ 並分別利用 Markov inequality, Chebyshev inequalty 與 Chernoff bound 估計此機率的上界。


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。