11/22/2017

[數理統計] 對平均值的信賴區間

考慮一組 i.i.d. random samples $X_1,X_2,...,$ 配備 期望平均 $m$ 與 變異數 (variance) $\sigma^2$,假設變異已知,但期望平均 $m$ 為未知。我們想對 $m$ 進行估計。一般的做法是採用 sample mean 估計量
\[
M_n := \frac{1}{n}\sum_{i = 1}^n X_i
\] 則我們知道 sample mean $M_n \to m$ 當 $n \to \infty$ in probability,此性質稱作 (weak) consistency estimator,但實際上,大多情況之下我們僅僅只能量測有限 $n$ (比如只能做有限次實驗),則我們想問該如何描述紹述 $M_n$ 有多接近 $m$ 呢?此想法為建構 信賴區間的動機:對某些 $\delta >0$ 而言,我們定義
\[
P(m \in [M_n -\delta, M_n + \delta] ) = 1-\alpha
\]其中 $[M_n -\delta, M_n + \delta] $ 稱作信賴區間(Confidence interval) 且 $1-\alpha$ 稱作 信心水準 (Confidence level),因此 Confidence interval 是一個隨機集合 而信心水準是 此隨機集合包含未知參數 $m$ 的機率。一般而言,在實務上多使用 $1-\alpha \in [0.9, 0.99]$。

Comments:
1. 上述 $M_n$ 不但為為 真實平均 (或者期望值) $m$  的 consistent estimator 且 亦為不偏 (unbiased)估計量。


問題:給定 $\alpha$,我們想問該如何選取參數 $\delta$ 使得 \[
P(m \in [M_n -\delta, M_n + \delta] ) = 1-\alpha
\]成立?

要回答此問題,我們首先觀察
\[m \in [{M_n} - \delta ,{M_n} + \delta ] \Leftrightarrow {M_n} - \delta  \leqslant m \leqslant {M_n} + \delta \]亦即 $- \delta  \leqslant m - {M_n} \leqslant \delta $ 此等價為
\[
|M_n - m| \leq \delta
\]故此
\[P(m \in [{M_n} - \delta ,{M_n} + \delta ]) = P\left( {\left| {{M_n} - m} \right| \leqslant \delta } \right)\]現在我們取
\[
\delta := \frac{\sigma y}{\sqrt{n}}
\] 上述 $\delta$ 的取法給了我們極大的方便,因為
\begin{align*}
  P\left( {\left| {{M_n} - m} \right| \leqslant \delta } \right) &= P\left( {\left| {{M_n} - m} \right| \leqslant \frac{{\sigma y}}{{\sqrt n }}} \right) \hfill \\
  & = P\left( {\left| {\frac{{{M_n} - m}}{{\sigma /\sqrt n }}} \right| \leqslant y} \right) \hfill \\
  & = P\left( { - y \leqslant \frac{{{M_n} - m}}{{\sigma /\sqrt n }} \leqslant y} \right) \hfill \\
   & = {F_{\frac{{{M_n} - m}}{{\sigma /\sqrt n }}}}\left( y \right) - {F_{\frac{{{M_n} - m}}{{\sigma /\sqrt n }}}}\left( { - y} \right) \hfill \\
\end{align*} 其中 $F_X(\cdot)$ 表示隨機變數 $X$的累積機率密度函數 (cdf)。由 中央極限定理(Central Limit Theorem, CLT) 我們可知 \[{F_{\frac{{{M_n} - m}}{{\sigma /\sqrt n }}}}\left( y \right) \to \Phi \left( y \right)\]其中 $\Phi(y)$ 為 標準常態分配的累積機率密度函數 (standard normal cdf) 滿足
\[
\Phi(y) := \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^y e^{-t^2/2} dt
\]故當 $n$ 足夠大的時候,
\[\begin{gathered}
  P\left( {\left| {{M_n} - m} \right| \leqslant \delta } \right) = {F_{\frac{{{M_n} - m}}{{\sigma /\sqrt n }}}}\left( y \right) - {F_{\frac{{{M_n} - m}}{{\sigma /\sqrt n }}}}\left( { - y} \right) \hfill \\
   \approx \Phi \left( y \right) - \Phi \left( { - y} \right) \hfill \\
\end{gathered} \]由於 $\Phi(y)$ 為 even density function,由附註的 FACT ,我們有 $\Phi(-y) =1 - \Phi(y)$ 故可推得
\[P\left( {\left| {{M_n} - m} \right| \leqslant \delta } \right) \approx \Phi \left( y \right) - \Phi \left( { - y} \right) = 2\Phi \left( y \right) - 1\]現在觀察上述結果,我們得到以下結論:若我們希望
\[P\left( {\left| {{M_n} - m} \right| \leqslant \delta } \right) = 1 - \alpha \]則等價求解 $2\Phi \left( y \right) - 1 = 1- \alpha$ 亦即
\[\Phi \left( y \right) = 1 - \frac{\alpha }{2}\]注意到上式與 $n$ 無關 且 也與 $X_i$ 的 pdf 無關!此式的解我們將其記作 $y_{\alpha/2}$ 在 MATLAB 我們可求解
\[
y_{\alpha/2} = \text{norminv(1-alpha/2)}
\]以下我們將上述討論記作以下結果。

====================
Theorem:
固定信心水準 $1-\alpha$ ,則其平均值 對應的 $(1-\alpha) \%$ 信賴區間 為
\[m \in \left[ {{M_n} - \frac{1}{{\sqrt n }}\sigma {y_{\alpha /2}},{M_n}  + \frac{1}{{\sqrt n }}\sigma {y_{\alpha /2}}} \right]\]
====================


接著我們看個例子:
====================
Example: 令 $X_1,X_2...$為 i.i.d. random samples 滿足 $\sigma = 2$。若我們已知 $M_{100} = 1 $ 試求出其真實平均 落在信心水準分別為 95% 與 99% 信賴區間:
====================

Proof: 對於 $95\%$ 信心水準,其 $\alpha = 1 - 0.95 = 0.05$。接著我們求解 $y_{\alpha/2}$,利用 MATLAB :
$$
y_{\alpha/2} = \text{norminv(1 - 0.05/2)} = 1.96
$$故其對應的 95% 信賴區間為
\begin{align*}
  m &\in \left[ {{M_n} - \frac{1}{{\sqrt n }}\sigma {y_{\alpha /2}},{M_n} + \frac{1}{{\sqrt n }}\sigma {y_{\alpha /2}}} \right] \\
&= \left[ {1 - \frac{1}{{\sqrt {100} }}2\left( {1.96} \right),1 + \frac{1}{{\sqrt {100} }}2\left( {1.96} \right)} \right] \hfill \\
  & = \left[ {0.608,1.392} \right] \hfill \\
\end{align*}

對於 99% 信心區間可用同樣方法,不難求得
\[
m \in [0.4848,  1.5152]
\]細節留給讀者自行練習。

由上述例子可看出當 信心水準越大,對應的信賴區間越大。另外注意到因為
\[m \in \left[ {{M_n} - \frac{1}{{\sqrt n }}\sigma {y_{\alpha /2}},{M_n}  + \frac{1}{{\sqrt n }}\sigma {y_{\alpha /2}}} \right]\]不難看出如果想要縮減信賴區間,另一種方法則是 增加 量測值,也就是把 $n$ 提高。


Comments:
注意到上述討論我們假設 random samples 已知變異數。若變異數未知,則我們使用變異數的不偏估計量 $S_n^2$ 取代,亦即使用
\[
S_n^2 = \frac{1}{N-1} \sum_{i=1}^n (X_i -m)^2
\]則前述的信賴區間變成
\[m \in \left[ {{M_n} - \frac{1}{{\sqrt n }}{S_n}{y_{\alpha /2}},{M_n} + \frac{1}{{\sqrt n }}{S_n}{y_{\alpha /2}}} \right]
\]證明我們暫且略過。



附註
=================
FACT:
令 $X$ 為配備 even density function $f$ 的隨機變數。若 $F$ 為任意 even density function $f$ 的 cdf函數,則
$$
F(-x) = 1 - F(x)
$$=================
Proof:
令 $f$ even density function ,則由 cdf 定義可知
\[F\left( { - x} \right): = P(X \leq -x) = \int_{ - \infty }^{ - x} {f\left( t \right)dt} \]現在引入變數變換,令 $t := -y$則
\[\int_{ - \infty }^{ - x} {f\left( t \right)dt}  =  - \int_\infty ^x {f\left( { - y} \right)dy} \]由於 $f$ 為 even function 故 $f(-y) = f(y) \;\; \forall y $,所以
\begin{align*}
  \int_{ - \infty }^{ - x} {f\left( t \right)dt}  &=  - \int_\infty ^x {f\left( { - y} \right)dy}  \hfill \\
  & =  - \int_\infty ^x {f\left( y \right)dy}  \hfill \\
  & = \int_x^\infty  {f\left( y \right)dy}  = 1 - F\left( x \right) \hfill \\
\end{align*} 換言之,我們得到
\[
F(-x) = 1 - F(x)
\]至此得證。$\square$

上述 FACT 亦可用反證法求證,在此不贅述。

11/06/2017

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

[機率論] 關於配備 Pareto Density 隨機變數 的一個簡單例子

令 $X$ 為隨機變數配備標準 Pareto density,亦即其機率密度函數 $f_X$ 滿足
\[f_X\left( x \right): = \left\{ \begin{gathered}
  \frac{2}{{{x^3}}}\begin{array}{*{20}{c}}
  {}&{x \geqslant 1}
\end{array} \hfill \\
  0\begin{array}{*{20}{c}}
  {}&{o.w.}
\end{array} \hfill \\
\end{gathered}  \right.\]
(a) 對任意 $a \geq 1$ 試求 $P(X \geq a)$
(b) 延續 (a),利用 Markov inequality 求其上界。

Proof (a)
\begin{align*}
  P(X \geqslant a) &= 1 - P\left( {X < a} \right) \hfill \\
   &= 1 - \int_1^a {\frac{2}{{{x^3}}}dx}  \hfill \\
   &= 1 - 2\left( {\left. {\frac{{{x^{ - 2}}}}{{ - 2}}} \right|_1^a} \right) \hfill \\
   &= \frac{1}{{{a^2}}} \hfill \\
\end{align*}

Comments: 讀者可注意到上述結果亦可 透過直接計算
\[P\left( {X \geqslant a} \right) = \int_a^\infty  {\frac{2}{{{x^3}}}dx}  = 2\left( {\frac{1}{{ - 2}}\left. {{x^{ - 2}}} \right|_a^\infty } \right) = {a^{ - 2}}\]


Proof (b):
注意到 $X$ 為取值非負隨機變數,故對任意 $a \geq 1$,利用 Markov inequality, 我們有
\begin{align*}
  P(X \geqslant a) &\leqslant \frac{{E\left[ X \right]}}{a} \hfill \\
   &= \frac{1}{a}\int_{ - \infty }^\infty  {x{f_X}\left( x \right)dx}  \hfill \\
   &= \frac{1}{a}\int_1^\infty  {x\frac{2}{{{x^3}}}dx}  \hfill \\
   &= \frac{2}{a}\int_1^\infty  {\frac{1}{{{x^2}}}dx}  \hfill \\
   &=  - \frac{2}{a}\left( {\left. {{x^{ - 1}}} \right|_1^\infty } \right) =  - \frac{2}{a}\left( {0 - 1} \right) = \frac{2}{a} \hfill \\
\end{align*}

Comments:
1. 注意到上述 (b) 部分透過 Markov inequality 所得到的上界只有在 $a \geq 2$ 才有效力,因為當 $a \in [1,2]$ 之間時,我們得到 $2/a >1$。但由於機率測度不能超過 $1$,上述 $2/a$ 上界在 $a \in [1,2]$ 之間對我們的 $P(X \geq a)$ 的估計並無任何幫助。


2. 注意到 $a \geq 1$ 故不難得證
\[\frac{1}{{{a^2}}} \leqslant \frac{2}{a} \] 此說明了在此分佈之下,利用 Markov inequality 所得到的機率上界過鬆。下圖顯示了 $a \in [1,5]$ 的機率 與 Markov inequality所得的上界



[最佳化] C^2 函數一階逼近的餘項積分表示

令 $f: \mathbb{R}^m \to \mathbb{R}$ 為 $C^2$-函數。對 $f$ 在 $y$ 附近使用一階泰勒展開: \[ T_y(x) := f(y) + \nabla f(y)^\top (x - y) \] 則其餘項 $R(x,y)$ 訂為 $$R(...