12/24/2017

[凸分析] 任意遞增函數為 quasiconcave 與 quasiconvex

=============
Theorem:
令 $f : \mathbb{R} \to \mathbb{R}$ 為遞增函數,則 $f$ 同時為 quasiconcave 與 quasiconvex。
=============

Proof:
考慮 $x,y \in \mathbb{R}$ 且 $\lambda \in (0,1)$,在不失一般性情況我們假設 $x>y$,則
\[
x > \lambda x + (1-\lambda)y > y
\]因為 $f$ 遞增,我們有
\[
f(x) > f( \lambda x + (1-\lambda)y) > f(y) \;\;\;\; (**)
\]由上述不等式,我們可寫
 $$
f(x) = \max\{f(x),f(y)\}
$$故由第一部分的不等式,我們有
\[
 \max\{f(x),f(y)\} > f( \lambda x + (1-\lambda)y)
\]此表明 $f$ 為 quasiconvex。

同理,由 $(**)$ 我們亦可寫下
\[
f(y) := \min\{f(x),f(y)\}
\]故由第二部分的不等式,我們有
\[
 f( \lambda x + (1-\lambda)y) >\min\{f(x),f(y)\}
\]此表明 $f$ 為 quasiconcave 至此證明完畢。$\square$

12/19/2017

[凸分析] 凸性 與 齊次性 的關聯 (2):一些常見的結果

此文接續前篇對於凸函數 與 齊次函數的討論,主要是給出一些常見的結果。閱讀此文之前,建議讀者先回憶 凸性 與 齊次函數的定義,關於齊次函數以及一些相關例子,讀者可參閱 [凸分析] 凸性 與 齊次性 的關聯 (1):一些常見例子

以下我們首先給出 一組齊次函數的 連乘  或 連加 仍保持為 齊次函數 的條件:

================================
Theorem: Homogeneous Functions Algebra
1. 令 $f_1,...,f_m$ 為一組 定義在 convex cone $C \subset \mathbb{R}^n$ 上的 homogeneous functions,且對於 $i=1,...,m$ 而言, $f_i$ 具有 homogeneous of degree $\alpha_i$。則
\[
z(x) :=  \prod_{i=1}^m f_i(x) = f_1(x) \cdot f_2(x) \cdots f_m(x)
\]為 homogenous of degree $(\alpha_1 + ... +\alpha_m)$

2. 令 $f_1,...,f_m$ 為一組 定義在 convex cone $C \subset \mathbb{R}^n$ 上的 homogeneous functions,且對於 $i=1,...,m$ 而言, $f_i$ 具有相同 homogeneous of degree $\alpha$。則
\[z(x): = {\left( {\sum\limits_{i = 1}^m {{f_i}(x)} } \right)^\beta }\]為 homogenous of degree $(\alpha \beta)$
================================

Proof 1: 令 $x \in C$ 觀察
\[
z(tx) = \prod_{i=1}^m f_i(tx)
\]由於 $f_i$ 為 homogeneous of degree $\alpha_i$,我們有 $$f_i(tx) = t^{\alpha_i} f(x)$$ 且 $\forall t>0, i=1,2,...,m$,因此

\begin{align*}
  z(tx) &= \prod\limits_{i = 1}^m {{f_i}} (tx) \hfill \\
   &= \prod\limits_{i = 1}^m {{t^{{\alpha _i}}}{f_i}(x)}  \hfill \\
   &= {t^{{\alpha _1}}}{f_1}(x){t^{{\alpha _2}}}{f_2}(x)...{t^{{\alpha _m}}}{f_m}(x) \hfill \\
   &= {t^{\sum\limits_{i = 1}^m {{\alpha _i}} }}\left( {{f_1}(x){f_2}(x)...{f_m}(x)} \right) \hfill \\
   &= {t^{\sum\limits_{i = 1}^m {{\alpha _i}} }}z\left( x \right)
\end{align*}
上式對任意 $t>0$ 成立,此表明 $z(x)$ 為 homogeneous of degree $(\alpha_1 + ... +\alpha_m)$,至此證畢。$\square$


Proof 2: 令 $x \in C$ 觀察
\[z(tx): = {\left( {\sum\limits_{i = 1}^m {{f_i}(tx)} } \right)^\beta }\]由於 $f_i$ 為 homogeneous of degree $\alpha$,我們有 $$f_i(tx) = t^{\alpha} f(x)$$ 且 $\forall t>0, i=1,2,...,m$,因此

\begin{align*}
  z(tx)&: = {\left( {\sum\limits_{i = 1}^m {{f_i}(tx)} } \right)^\beta } \hfill \\
   &= {\left( {\sum\limits_{i = 1}^m {{t^\alpha }{f_i}(x)} } \right)^\beta } \hfill \\
   &= {\left( {{t^\alpha }\sum\limits_{i = 1}^m {{f_i}(x)} } \right)^\beta } \hfill \\
   &= \left( {{t^{\alpha \beta }}} \right){\left( {\sum\limits_{i = 1}^m {{f_i}(x)} } \right)^\beta } \hfill \\
  & = \left( {{t^{\alpha \beta }}} \right)z\left( x \right) \hfill \\
\end{align*}
上式對任意 $t>0$ 成立,此表明 $z(x)$ 為 homogeneous of degree $(\alpha \beta)$,至此證畢。$\square$



下面這個結果表明 一次齊次函數 如果具有 次可加性(subadditivity) 則 此函數必定為 convex。

================================
Theorem: Linear Homogeneity With Subadditivity Produces Convexity
令 $f: C \subset \mathbb{R}^n \to \mathbb{R}$ 為 linearly homogeneous function; i.e., $(f(tx) = t f(x), \; \forall t>0)$ 則 $f$ 為 convex 若且唯若 $f$ 滿足 subadditivity,亦即,對任意 $x,y \in C$,$$
f(x+y) \leq f(x) + f(y)
$$================================


Proof: $(\Rightarrow)$ 給定 $f$ 為 convex 且 linearly homogeneous 要證明對任意 $x,y \in C$,$$
f(x+y) \leq f(x) + f(y)
$$故給定 $x,y \in C$ 並且觀察
\begin{align*}
  f\left( {x + y} \right) &= f\left( {2\left( {\frac{{x + y}}{2}} \right)} \right) \hfill \\
   &= 2f\left( {\frac{{x + y}}{2}} \right)\;\;\;\; (*) \hfill \\
\end{align*} 上述最後一條等式成立因為我們使用了 $f$ 為 linearly homogeneous。接著由於 $f$ 為 convex 且 $1/2 \in (0,1)$ 故我們有
\[f\left( {\frac{{x + y}}{2}} \right) \leqslant \frac{1}{2}f\left( x \right) + \frac{1}{2}f\left( y \right)\]故
\[2f\left( {\frac{{x + y}}{2}} \right) \leqslant 2\left( {\frac{1}{2}f\left( x \right) + \frac{1}{2}f\left( y \right)} \right) = f\left( x \right) + f\left( y \right) \;\;\; (**)\]由 $(*)$ 與 $(**)$ 我們有
\[f\left( {x + y} \right) \leqslant f\left( x \right) + f\left( y \right)\]

$(\Leftarrow)$ 接著我們令 $x,y \in C$ 滿足 subadditivity: $f(x+y) \leq f(x) + f(y)$,我們要證明 $f$ 是 convex。現在給定 $\lambda \in (0,1)$ ,注意到由於 $x,y \in C$ 且 $C$ 為 convex cone,故對任意 $\lambda \in (0,1)$,我們有 $\lambda x \in C$ 與 $(1-\lambda y) \in C$。現在利用 已知的 subadditivity,我們 觀察
\[
f(\lambda x + (1- \lambda) y)  \leq f(\lambda x) + f( (1-\lambda)y) \;\;\; (\star)
\]利用 $f$ 為 linearly homogeneous,$f(\lambda x)=\lambda f( x)$ 且 $f( (1-\lambda)y) = (1-\lambda)f( y)$亦即,
\[f(\lambda x) + f((1 - \lambda )y) = \lambda f\left( x \right) + \left( {1 - \lambda } \right)f\left( y \right) \;\;\;\; (\star \star)\]由 $(\star)$ 與 $(\star \star)$ 式,我們可得
\[f(\lambda x + (1 - \lambda )y) \leqslant \lambda f\left( x \right) + \left( {1 - \lambda } \right)f\left( y \right)\]此表明 $f$ 為 convex in $C$。$\square$

[凸分析] 凸性 與 齊次性 的關聯 (1):定義 與 一些常見例子


Definition:  Homogenous Function of Degree Alpha
令 $C \subset \mathbb{R}^n$ 為 convex cone。我們說函數 $f: C \to \mathbb{R}$ 為  $\alpha$ 次齊次函數 (homogeneous of degree $\alpha \in \mathbb{R}$) 若下列條件成立:
對任意 $x \in C$,
\[
f(t x) = t^\alpha f(x),\;\;\; \forall t >0
\]

Comments:
1.上述 齊次函數 定義可以推廣到不是在 convex cone上而是任意向量空間,但一般做 convex cone的假設是為了 其他在凸分析上的 用途。在比較深入的凸分析教材中,可能會探討所謂 廣義凸性(generalized convexity)比如 quasi-convexity, quasi-concavity, semi-strictly quasi-convexity 等等,則此時函數定義域 需要是凸集。

2. 注意到 degree of homogeneity $\alpha \in \mathbb{R}$,意指 此 $\alpha$ 為任意實數,正數,負數,零 或者其他都可以。

3. 我們說 $f$ 為 homogenous of degree $0$ 若對任意 $x \in C$,
\[
f(tx) = f(x), \forall t>0
\]若 $f$ 為 homogenous of degree $1$ 一般稱之為 linearly homogeneous ,亦即 對任意 $x \in C$
\[
f(tx) = t f(x), \forall t>0
\] 以下我們看幾個例子:

Example 1
考慮 需求函數 (Demand Function)
\[
D(p,R) := \frac{R}{p}
\]其中 $p > 0$ 為 price of a good 且 $R>0$ 為 income,試證此函數為 homogeneous of degree 0

Proof: 令 $C :=\{(p,r): p>0, R>0\}$,則此集合為一個 convex cone,現在觀察對任意 $(p,r) \in C$,
\[
D(tp, tR) = \frac{tR}{tp} = \frac{R}{p} = t^0 D(p,r)
\]上式對任意 $t>0$ 成立,故由定義可知 $D(p,r)$ 為 homogenous of degree zero,至此證畢。$\square$


Example 2:
考慮 生產函數 (Production Function)
\[
f(L,K) := L^{1/3} K^{2/3}
\]其中 $L>0$ 為投入的勞力 (labour) 且 $K>0$ 為 投入資本 capital,試證生產函數 $f$ 為 homogenous of degree $1$

Proof: 令 $C:= \{(L,K): L>0, K>0\}$ ,則可知 $C$ 為一個 convex cone。現在取任意 $(L,K) \in C$,我們有
\[f(tL,tK): = {\left( {tL} \right)^{1/3}}{\left( {tK} \right)^{2/3}} = t{\left( L \right)^{1/3}}{\left( K \right)^{2/3}} = t f(L,K)
\]上式對任意 $t>0$ 成立,故由定義可知 $D(p,r)$ 為 homogenous of degree zero,至此證畢。$\square$

Comments:
上述的生產函數 在經濟學中被稱為 Cobb-Douglas Function,在一般 計量經濟 中通常記作
\[
f(K,L) := A K^\alpha L^{1- \alpha}
\]此式子命名來自 兩位美國學者 C. W. Cobb 與 P. H. Douglas 於 1927 提出,此函數用以估計生產量,但事實上此式早在 1900之前就由 瑞士經濟學家 Knut Wicksell 已率先提出。此為軼事與本文無關只是單純提及。


接著我們看個上述生產函數的推廣,在(個體)經濟學中常見的 Cobb-Douglas Function:

===============
Theorem: Generalized Cobb-Douglas Function is Homogenous of Degree Alpha
令 $A>0, x_i>0, \alpha_i>0, i =1,2,...,n$,定義 Cobb-Douglas 函數
\[
f(x): = Ax_1^{{\alpha _1}}x_2^{{\alpha _2}} \cdots x_n^{{\alpha _n}}
\]則 $f$ 為 Homogeneous of degree $\alpha := \sum_{i=1}^n \alpha_i$
===============

Proof: 令 $C:=\{x=(x_1,x_2,...,x_n): x_i >0\}$ ,則不難發現 $C$ 為  convex cone,現在取任意 $x = (x_1,...,x_n) \in C$,我們觀察
\begin{align*}
  f(tx) &: = A\left( {t{x_1}} \right)_{}^{{\alpha _1}}\left( {t{x_2}} \right)_{}^{{\alpha _2}} \cdots \left( {t{x_n}} \right)_{}^{{\alpha _n}} \hfill \\
   &= A{t^{\sum\limits_{i = 1}^n {{\alpha _i}} }}\left( {{x_1}} \right)_{}^{{\alpha _1}}\left( {{x_2}} \right)_{}^{{\alpha _2}} \cdots \left( {{x_n}} \right)_{}^{{\alpha _n}} \hfill \\
   &= {t^{\sum\limits_{i = 1}^n {{\alpha _i}} }}\underbrace {A\left( {{x_1}} \right)_{}^{{\alpha _1}}\left( {{x_2}} \right)_{}^{{\alpha _2}} \cdots \left( {{x_n}} \right)_{}^{{\alpha _n}}}_{ = f\left( x \right)} \\
&= {t^\alpha }f\left( x \right)
\end{align*} 其中 $\alpha:= \sum_{i=1}^n \alpha_i$,上述等式對任意 $t>0$ 成立,故 $f$ 為 Homogeneous of degree $\alpha := \sum_{i=1}^n \alpha_i$,至此證畢。$\square$


Comments:
上述 Cobb-Douglas function $f$ 亦俱備 log-linear 性質,亦即對 $f$ 取 $\log (.)$ 之後為線性函數:觀察
\begin{align*}
 \log \left( {f\left( x \right)} \right) &= \log \left( {Ax_1^{{\alpha _1}}x_2^{{\alpha _2}} \cdots x_n^{{\alpha _n}}} \right) \hfill \\
   &= \log \left( A \right) + {\alpha _1}\log \left( {x_1^{}} \right) + {\alpha _2}\log \left( {x_2^{}} \right) + ... + {\alpha _n}\log \left( {x_n^{}} \right) \hfill \\
\end{align*} 由上述結果不難看出 $\log(f)$ 為 linear functions of $\log(x_1), \log(x_2),...,\log(x_n)$




[訊號處理] 離散時間 的 Parserval's Theorem

Discrete-Time Parserval's Theorem:
令 $x[n]$ 為 取實數值的離散時間訊號; i.e., 對任意整數 $n$ 而言,
 $x[n] \in \mathbb{R}$ 且令 $X(\omega) := DTFT(x[n])$,則下列等式成立  \[\sum\limits_{n =  - \infty }^\infty  {{{\left| {x\left[ n \right]} \right|}^2} = \frac{1}{{2\pi }}\int_0^{2\pi } {{{\left| {X\left( \omega  \right)} \right|}^2}d\omega } } \]其中 $DTFT(x[n])$ 表示 對 $x[n] $ 取 離散時間傅立葉轉換 (Discrete Time Fourier Transform, DTFT),亦即
\[
X(\omega) := \sum_{n = -\infty}^\infty x[n] e^{-j \omega n}
\]

Comments:
1. 在訊號處理或者訊號分析的領域,上述定理有可被賦予的物理意義:一般我們把 Parserval's theorem 等式左方 稱為 訊號 $x[n]$ 的 總能量 (total energy),現在觀察右式表示對 $|X(\omega)|$ 做 $2 \pi$ 週期積分,因為 DTFT 為 $2\pi$ 週期,故右式 事實上是對所有的頻率積分等於 總能量,那麼被積分項 $|X(\omega)|$ 很自然的被稱作 頻譜密度 spectral (power) density
2. 考慮 $x(t)$ 為訊號,則 $\sum\limits_{n =  - \infty }^\infty  {{{\left| {x\left[ n \right]} \right|}^2}} $ 稱作此訊號的 total energy
3. 數學上的觀點,上述提及的 總能量  = 自己與自己在 函數空間做 內積 。
4. 另一種數學上的觀點:若 $x[n]$ 想成向量空間的一個向量,則總能量 $$\sum\limits_{n =  - \infty }^\infty  {{{\left| {x\left[ n \right]} \right|}^2}} $$ 可想成 $x[n]$ "長度" 的平方 ($l_2$-norm 平方)。
5. Fourier 轉換 是保持長度(norm preserving)的一種 線性轉換。
6. 上述 定理中我們雖僅考慮任意 實數值訊號 $x[n] \in \mathbb{R}, \;\;\; \forall \; n$ ,但事實上此定理對 $x[n] \in \mathbb{C}$ 亦成立。
7. 當然,有 離散時間傅立葉轉換,亦有 反轉換,稱作 Inverse Discrete Time Fourier Transform, IDTFT。


以下我們給出上述定理的證明

Proof: 給定 $x[n]$ 與其對應的 DTFT $X(\omega)$,我們要證明 Parserval's theorem 等式成立。故首先定義一個 輔助函數
\[
y\left[ m \right]: = \sum\limits_{n =  - \infty }^\infty  {x\left[ n \right]x\left[ {n - m} \right]}  \;\;\; (\star)
\] 上述 $y$ 一般稱作是 $x$ 的 自相關函數 (auto-correlation function) 。定義此函數的好處是我們可以利用 DTFT的各種性質來求證 Parserval's theorem。現在觀察 \[
 y\left[ 0 \right] = \sum\limits_{n = - \infty }^\infty {x\left[ 0 \right]x\left[ {n - 0} \right]} = \sum\limits_{n = - \infty }^\infty {{x^2}\left[ n \right]}
 \]此為要證明的 Parserval's 等式左方。

接著我們觀察 auto-correlation function $y[n]$ 為時域訊號,可透過 IDTFT 來表示 (why?),亦即
\[y[n] = \frac{1}{{2\pi }}\int_0^{2\pi } Y (\omega ){e^{j\omega n}}d\omega \]注意到當 $n=0$,我們有
\[y[0] = {\left. {\left( {\frac{1}{{2\pi }}\int_0^{2\pi } Y (\omega ){e^{j\omega n}}d\omega } \right)} \right|_{n = 0}} = \frac{1}{{2\pi }}\int_0^{2\pi } Y (\omega )d\omega \]至此不難發現若 $Y(\omega) = |X(\omega)|^2$ 則 Parseval's theorem得證。要達成此目標,我們觀察上述  $(\star)$式 事實上等價為
\[ y[n] = x[n] * x[-n]
\]其中 $*$ 表示 convolution。 (讀者應回憶 convolution 定義並自行驗證。) 回憶 DTFT 的 convolution 性質:亦即 時域 convolution 等價為 頻域做 multiplication。 故我們對 $(\star)$式 兩邊同取 DTFT 可得
\[y\left[ m \right] = x\left[ m \right]*x\left[ { - m} \right] \Rightarrow Y\left( \omega  \right) = X\left( \omega  \right){X^*}\left( \omega  \right) = |X(\omega)|^2\]
注意到在此我們使用了另一個 FACT: 若 $X(\omega) := DTFT(x[n])$,則 $DTFT(x[-n]) = X^*(\omega)$。

現在比較 $y[0]$ 可得\[\left\{ \begin{gathered} y\left[ 0 \right] = \sum\limits_{n = - \infty }^\infty {{x^2}\left[ n \right]} \hfill \\ y[0] = \frac{1}{{2\pi }}\int_0^{2\pi } {{{\left| {X\left( \omega \right)} \right|}^2}} d\omega \hfill \\ \end{gathered} \right. \Rightarrow \frac{1}{{2\pi }}\int_0^{2\pi } {{{\left| {X\left( \omega \right)} \right|}^2}} d\omega = \sum\limits_{n = - \infty }^\infty {{x^2}\left[ n \right]} \]至此證明完畢。$\square$

12/06/2017

[機率論] 關於含有 Factorial 函數的求導的注意事項 - Erlang 分佈為例

在某些情況,我們可能會希望對含有 Factorial (比如說 $k!$, $k \in \mathbb{N}$) 的函數 取導數,但在求導 的過程中有些細微的部分需要多加留意。以下我們用一個例子來體現。

令 $m \in \mathbb{N}$,考慮隨機變數 $X$ 配備 Erlang 分佈
$$
F_X(x) := 1 - \sum_{k=0}^{m-1} \frac{(\lambda x)^k}{k!} e^{-\lambda x}, x>0
$$ 試證 其 機率密度函數 (Probability Density Function, pdf) $f_X$ 滿足
\[{f_X}\left( x \right) = \frac{{{{(\lambda x)}^{\left( {m - 1} \right)}}}}{{\left( {m - 1} \right)!}}\lambda {e^{ - \lambda x}}\]

(FALSE) Proof:
首先注意到分佈函數可導,故我們可利用 分佈函數的導數 為 密度函數 的性質 ($F'(x) = f(x)$),來求得 $f_X$。現在對 $F_X$ 求導
\[\frac{d}{{dx}}{F_X}(x) =  - \sum\limits_{k = 0}^{m - 1} {\left( {\underbrace {\frac{{k{{(\lambda x)}^{k - 1}}\lambda }}{{k!}}{e^{ - \lambda x}}}_{**} + \frac{{{{(\lambda x)}^k}}}{{k!}}\left( { - \lambda } \right){e^{ - \lambda x}}} \right)} \]注意到summation的第一項 $(**)$,讀者可能會很自然地認為 $**$ 可寫成
\[\frac{{k{{(\lambda x)}^{k - 1}}\lambda }}{{k!}}{e^{ - \lambda x}} = \frac{{k{{(\lambda x)}^{k - 1}}\lambda }}{{k\left( {k - 1} \right)!}}{e^{ - \lambda x}}\]
然後試圖對 分子分母的 $k$對消。但注意到此項 是在 summation內部,若對 分子 與 分母 進行 對消將產生問題,因為當 $k=0$ 時候會出現 難以處理未定義的 $-1!$ 。到此我們無法繼續進行,該怎麼避免這種問題呢?我們必須將可能出問題的 $k=0$ 項次分開討論。

Proof:
首先改寫

\[{F_X}(x): = 1 - \sum\limits_{k = 0}^{m - 1} {\frac{{{{(\lambda x)}^k}}}{{k!}}} {e^{ - \lambda x}} = 1 - (\lambda x){e^{ - \lambda x}} - \sum\limits_{k = 1}^{m - 1} {\frac{{{{(\lambda x)}^k}}}{{k!}}} {e^{ - \lambda x}}\]再取導數
\[\small
 \begin{align*}
  \frac{d}{{dx}}{F_X}(x) &= 0 - \left[ {\left( { - \lambda } \right){e^{ - \lambda x}} + \sum\limits_{k = 1}^{m - 1} {\left( {\frac{{k{{(\lambda x)}^{k - 1}}\lambda }}{{k!}}{e^{ - \lambda x}} + \frac{{{{(\lambda x)}^k}}}{{k!}}\left( { - \lambda } \right){e^{ - \lambda x}}} \right)} } \right] \hfill \\
   & =   - \left[ {\left( { - \lambda } \right){e^{ - \lambda x}} + \left( {\left( {\frac{{{{(\lambda x)}^0}}}{{1!}} - \frac{{{{(\lambda x)}^1}}}{{1!}}} \right) + \left( {\frac{{2{{(\lambda x)}^1}}}{{2!}} - \frac{{{{(\lambda x)}^2}}}{{2!}}} \right) + ... + \left( {\frac{{\left( {m - 1} \right){{(\lambda x)}^{\left( {m - 1} \right) - 1}}}}{{\left( {m - 1} \right)!}} - \frac{{{{(\lambda x)}^{\left( {m - 1} \right)}}}}{{\left( {m - 1} \right)!}}} \right)} \right)\lambda {e^{ - \lambda x}}} \right]\hfill \\
  & = \lambda {e^{ - \lambda x}} - \left( {\frac{{{{(\lambda x)}^0}}}{{1!}}\underbrace { - \frac{{{{(\lambda x)}^1}}}{{1!}} + \frac{{2{{(\lambda x)}^1}}}{{2!}}}_{ = 0}\underbrace { - \frac{{{{(\lambda x)}^2}}}{{2!}} + \frac{{3{{(\lambda x)}^2}}}{{3!}}}_{ = 0}\underbrace { - \frac{{{{(\lambda x)}^3}}}{{3!}} + }_{ = 0}...\underbrace { + \frac{{\left( {m - 1} \right){{(\lambda x)}^{\left( {m - 1} \right) - 1}}}}{{\left( {m - 1} \right)!}}}_{ = 0} - \frac{{{{(\lambda x)}^{\left( {m - 1} \right)}}}}{{\left( {m - 1} \right)!}}} \right)\lambda {e^{ - \lambda x}} \hfill \\
  & = \lambda {e^{ - \lambda x}} - \left( {1 - \frac{{{{(\lambda x)}^{\left( {m - 1} \right)}}}}{{\left( {m - 1} \right)!}}} \right)\lambda {e^{ - \lambda x}} \hfill \\
   &= \frac{{{{(\lambda x)}^{\left( {m - 1} \right)}}}}{{\left( {m - 1} \right)!}}\lambda {e^{ - \lambda x}} \hfill \\
\end{align*} \]上述第三行等式為 telescoping sum,中間各項等於 $0$。至此證畢。$\square$

12/02/2017

[機率論] 一類條件機率取極限的問題

Theorem: 令 $X,Y$ 為 jointly continuous,
\[
\lim_{h \to 0} P((X,Y) \in A| x < X \leq x +h) = \int_{-\infty}^\infty 1_A(x,y) f_{Y|X}(y|x)dy
\]其中 $1_A(\cdot)$ 為 indicator function

Proof: 首先觀察
\begin{align*}
  P((X,Y) \in A|x < X \leqslant x + h) &= \frac{{P(\left\{ {(X,Y) \in A} \right\},\left\{ {x < X \leqslant x + h} \right\})}}{{P(x < X \leqslant x + h)}} \hfill \\
   &= \frac{{P(\left\{ {\left( {X,Y} \right) \in A} \right\} \cap \left\{ {X \in \left( {x,x + h} \right]} \right\})}}{{P(x < X \leqslant x + h)}} \hfill \\
   &= \frac{{P(\left\{ {\left( {X,Y} \right) \in A} \right\} \cap \left\{ {\left( {X,Y} \right) \in \left( {x,x + h} \right] \times \mathbb{R}} \right\})}}{{P(x < X \leqslant x + h)}} \hfill \\
   &= \frac{{P(\left( {X,Y} \right) \in A \cap \left\{ {\left( {x,x + h} \right] \times \mathbb{R}} \right\})}}{{P(x < X \leqslant x + h)}} \hfill \\
   &= \frac{{\iint\limits_{A \cap \left\{ {\left( {x,x + h} \right] \times \mathbb{R}} \right\}} {{f_{XY}}\left( {t,s} \right)dtds}}}{{\int_x^{x + h} {{f_X}\left( t \right)dt} }}
\end{align*} 由於 $1_{A \cap B} = 1_A \cdot 1_B$ 我們有
\begin{align*}
  P((X,Y) \in A|x < X \leqslant x + h) &= \frac{{\iint\limits_{} {{1_A}\left( {t,s} \right){1_{\left( {x,x + h} \right] \times \mathbb{R}}}\left( {t,s} \right){f_{XY}}\left( {t,s} \right)dtds}}}{{\int_x^{x + h} {{f_X}\left( t \right)dt} }} \hfill \\
   &= \frac{{\int_{ - \infty }^\infty  {\int_x^{x + h} {{1_A}\left( {t,s} \right){f_{XY}}\left( {t,s} \right)dtds} } }}{{\int_x^{x + h} {{f_X}\left( t \right)dt} }} \hfill \\
   &= \frac{{\int_x^{x + h} {\int_{ - \infty }^\infty  {{1_A}\left( {t,s} \right){f_{XY}}\left( {t,s} \right)dsdt} } }}{{\int_x^{x + h} {{f_X}\left( t \right)dt} }} \hfill \\
\end{align*} 上下同乘 $1/h$ 我們得到
\[P((X,Y) \in A|x < X \leqslant x + h) = \frac{{\frac{1}{h}\int_x^{x + h} {\int_{ - \infty }^\infty  {{1_A}\left( {t,s} \right){f_{XY}}\left( {t,s} \right)dsdt} } }}{{\frac{1}{h}\int_x^{x + h} {{f_X}\left( t \right)dt} }}\]讓 $h \to 0$ 我們有
\begin{align*}
  P((X,Y) \in A|x < X \leqslant x + h) &= \frac{{\frac{1}{h}\int_x^{x + h} {\int_{ - \infty }^\infty  {{1_A}\left( {t,s} \right){f_{XY}}\left( {t,s} \right)dsdt} } }}{{\frac{1}{h}\int_x^{x + h} {{f_X}\left( t \right)dt} }} \hfill \\
   &= \frac{{\int_{ - \infty }^\infty  {{1_A}\left( {x,s} \right){f_{XY}}\left( {x,s} \right)ds} }}{{{f_X}\left( x \right)}} \hfill \\
   &= \int_{ - \infty }^\infty  {{1_A}\left( {x,s} \right)\frac{{{f_{XY}}\left( {x,s} \right)}}{{{f_X}\left( x \right)}}ds}  \hfill \\
   &= \int_{ - \infty }^\infty  {{1_A}\left( {x,s} \right){f_{Y|X}}\left( {s|x} \right)ds} 
\end{align*} 上述等式即為所求,至此證畢。 $\square$

[機率論] 連續隨機變數條件機率的定義

若 $X$ 是連續隨機變數,則其累積機率分配(cumulative distribution function, cdf)
\[
F_X(x) := P(X \leq x) = \int_{-\infty}^x f_X(t) dt
\]為 (對 $x$ ) 連續函數,故單點機率測度 $P(X=x) =0$。但若我們考慮條件機率的情況事情會變得稍微有點棘手,因為假設我們引入第二個連續隨機變數 $Y$且假設 $X,Y$ 為 jointly continuous,現在我們想計算 $P(Y \in C| X=x)$,由條件機率定義可知
\[
P(Y \in C| X=x) = \frac{P(X=x,Y=c)}{P(X=x)}
\]但此時我們發現因為 $P(X=x) =0$,分母是$ 0$。對於這種情況我們該怎麼對 連續隨機機變數定義其條件機率?或者更簡單的說,該怎麼計算(或者定義)$P(Y \in C| X=x)$?


要計算 $P(Y \in C| X=x)$,我們首先考慮
\[
\lim_{h \to 0} P(Y \in C| x<X\leq x + h)
\]對任意 $h>0$而言,上述條件機率可寫成
\[P(Y \in C|x < X \leqslant x + h) = \frac{{P(Y \in C,x < X \leqslant x + h)}}{{P(x < X \leqslant x + h)}}\]注意到分子部分等價為
\[P(Y \in C,x < X \leqslant x + h) = P\left( {\left( {X,Y} \right) \in \left( {x,x + h} \right] \times C} \right)\]若 $X,Y$ 為 jointly continuous,則
\begin{align*}
  P(Y \in C|x < X \leqslant x + h) &= \frac{{P(Y \in C,x < X \leqslant x + h)}}{{P(x < X \leqslant x + h)}} \hfill \\
   &= \frac{{\int_x^{x + h} {\int_C^{} {{f_{XY}}\left( {t,s} \right)dsdt} } }}{{\int_x^{x + h} {{f_X}\left( t \right)dt} }} \hfill \\
\end{align*} 對上式分子分母同除 $1/h$ 並且讓 $h \to 0$ ,利用下文中的 FACT可得
\begin{align*}
  \mathop {\lim }\limits_{h \to 0} P(Y \in C|x < X \leqslant x + h) &= \mathop {\lim }\limits_{h \to 0} \frac{{\frac{1}{h}\int_x^{x + h} {\int_C^{} {{f_{XY}}\left( {t,s} \right)dsdt} } }}{{\frac{1}{h}\int_x^{x + h} {{f_X}\left( t \right)dt} }} \hfill \\
   &= \frac{{\int_C^{} {{f_{XY}}\left( {x,s} \right)ds} }}{{{f_X}\left( x \right)dt}} \hfill \\
\end{align*} 由上述 極限,我們可定義 在給定 $X$ 條件之下 ,$Y$的條件機率密度函數,記作 $f_{Y|X}$ 如下:
================

Definition: Conditional Probability and Conditional Density: 對任意 $x$ 滿足 $f_X(x) >0$,給定 $X$ 條件之下 ,$Y$的條件機率密度函數定義為
\[
f_{Y|X}(y|x) := \frac{f_{XY}(x,y)}{f_X(x)}
\]由 $f_{Y|X} $,我們可定義 給定條件 $X=x$ 之下,事件 $Y \in C$ 的條件機率為
\[
P(Y \in C|X=x):= \int_C f_{Y|X}(y|x)dy
\]================

Comments: 1. 同理,我們可定義 Conditional CDF 記作 $F_{Y|X}$ 滿足
\[
F_{Y|X}(y|x) := P(Y \leq y| X = x) = \int_{-\infty}^y f_{Y|X}(t|x) dt
\]2. 讀者應不難驗證 $\int_{-\infty}^{\infty} f_{Y|X}(y|x)dy = 1$。

================
FACT: 令 $X$ 為隨機變數配備 機率密度函數(probability density function, pdf) $f_X$,則
\[\lim_{h \to 0}\frac{1}{h}\int_x^{x + h} {{f_X}\left( t \right)dt}  = F_X'(x) =f_X(x)\]其中 $F_X$ 為 $X$ 累積分配函數(cdf)。
================

Proof: 首先觀察
\[\frac{1}{h}\int_x^{x + h} {{f_X}\left( t \right)dt}  = \frac{1}{h}\left( {{F_X}\left( {x + h} \right) - {F_X}\left( x \right)} \right)\]現在讓 $h\to 0$我們有
\[\mathop {\lim }\limits_{h \to 0} \frac{1}{h}\int_x^{x + h} {{f_X}\left( t \right)dt}  = \mathop {\lim }\limits_{h \to 0} \frac{1}{h}\left( {{F_X}\left( {x + h} \right) - {F_X}\left( x \right)} \right) = F'(x)\]若 density 存在,則利用 pdf 是 cdf的微分的事實,
\[
F_X'(x) = f_X(x)
\] 至此證明完畢。$\square$

[最佳化] 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(...