[機率論] 一些常用的機率上界估計-以 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。

[機率論] Exponential Random Variables

Definition: Exponential Random Variable
令 $\tau$ 為 隨機變數 且其 機率密度(probability density) 滿足
\[f_\tau\left( t \right): = \left\{ \begin{array}{l}
\lambda {e^{ - \lambda t}},\begin{array}{*{20}{c}}
{}&{}
\end{array}t \ge 0\\
0,\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array}t < 0
\end{array} \right.\]其中 $\lambda >0$ 為常數。則我們說 $\tau$ 為 exponential distribution 或者說 $\tau$ 為 Exponential 隨機變數


Example:
令 $\tau$ 為 Exponential 隨機變數，試計算 $E [\tau ]=?$ (hint: 利用 integration by part)

Solution:
由期望值定義，\[\begin{array}{l}
E[\tau]  = \int_0^\infty  {tf\left( t \right)dt}  = \lambda \int_0^\infty  {t{e^{ - \lambda t}}dt} \\
\begin{array}{*{20}{c}}
{}&{}\;
\end{array} = \lambda \left[ {\left. {t\frac{{ - 1}}{\lambda }{e^{ - \lambda t}}} \right|_0^\infty  - \left( {\int_0^\infty  {\frac{{ - 1}}{\lambda }{e^{ - \lambda t}}dt} } \right)} \right]\\
\begin{array}{*{20}{c}}
{}&{}\;
\end{array} = \left. { - t{e^{ - \lambda t}}} \right|_0^\infty  + \frac{1}{{ - \lambda }}\left. {{e^{ - \lambda t}}} \right|_0^\infty  = \frac{1}{\lambda }

\end{array}\]

Example
令 $\tau$ 為 Exponential 隨機變數，
(a) 試計算 累積機率分布函數 (Cumulative Distribution Function, CDF) $F_\tau(t) = P(\tau \le t)$
(b) 試計算 $P(\tau > t)$
Solution
(a) 由CDF定義：\[{F_\tau }(t) = P(\tau  \le t) = \int_0^t {f\left( t \right)dt}  = \int_0^t {\lambda {e^{ - \lambda \tau }}d\tau }  = 1 - {e^{ - \lambda t}},\begin{array}{*{20}{c}}
{}&{}

\end{array}t \ge 0\]
(b) 由於 $P(\tau > t) = 1 - P(\tau \le t)$ 由  (a) 可知 $P(\tau > t) = e^{-\lambda t}$, $t \ge 0$ $\square$


Memoryless property
考慮等待某事件發生 (比如某債卷即將違約)，且已知 此事件發生時間 $\tau$ 的 機率分布 服從 exponential 分布且 mean 為 $1/ \lambda$ (亦即 $\tau $ 為參數 $ \lambda$ 的 Exponential 隨機變數 ) 假設我們已經等了 $s$ 個單位時間，想問我們再等額外多少個 $t$ 單位時間 才會發生此事件的機率為何?

 此債卷違約機率可計算如下
\begin{align*}
P\left( {\tau  > t + s|\tau  > s} \right) &= \frac{{P\left( {\tau  > t + s,\tau  > s} \right)}}{{P\left( {\tau  > s} \right)}}\\
&= \frac{{P\left( {\tau  > t + s} \right)}}{{P\left( {\tau  > s} \right)}} \\
&= \frac{{{e^{ - \lambda \left( {t + s} \right)}}}}{{{e^{ - \lambda s}}}} = \underbrace {{e^{ - \lambda t}}}_{ = P\left( {\tau  > t} \right)}
\end{align*}上述結果顯示了 在等待 $s$ 單位時間後，再等額外多少個 $t$ 單位時間 才會發生此事件的機率 與 直接 從 時間 $0$ 開始 等到  $t$ 單位時間後 的機率相等。且分布仍為 exponential 分布，我們稱此性質為 Exponential 隨機變數的 失憶性 (memorylessness )