2014年12月20日 星期六

[Python] 簡單的互動猜數字遊戲

這是要介紹利用 Python 3.4 (Python 官方載點) 來撰寫一個簡單的猜數字遊戲
(NOTE: 一定要使用 python 3.x 避免錯誤的訊息)

想法:
首先Python會詢問玩家姓名,然後玩家輸入完畢之後,我們接著讓 python 產生 1~20 個的隨機整數,並邀請玩家在 有限猜測次數內猜對電腦產生的隨機整數(下面程式碼為1次)。我們首先會引入 random 函式庫來幫助我們建構隨機數 再透過 while /if 判斷式來提示玩家所猜的數字是太高或者太低。


以下我們用 python idle 介面撰寫程式碼如下:


用到的函數功能:

  1. random.randint(1,20) := 表示利用 random 函式庫產生 1~20 隨機整數
  2. print('...'):= 在螢幕上顯示 '字串' (利用 ' ')
  3. input():=會要求玩家輸入值
  4. str():= 將資料轉換回字串
  5. int():= 將資料轉換回整數
  6. while := 無窮迴圈 
  7. if:= 判斷


程式執行結果為

ref: Al Sweigart, Invent Your Own Computer Games with Python, 2nd Edition

2014年12月17日 星期三

2014/12/24 板橋長老教會燭光平安夜

歡迎一同前往 :)
願神的平安常常與我們同在

==========================

相關連結
主日禮拜時間:
《台語禮拜》週日上午09:30~11:00
《國語禮拜》週日上午11:05~12:30
教會地址:台北縣板橋市明德街1巷3號
連絡電話:02-29687749
駐堂牧者:洪英俊 牧師

[數學分析] Inverse Function Theorem

想法:
這次要介紹數學分析理論中一個重要的定理,稱作 反函數定理 (Inverse Function Theorem),簡而言之,反函數定理指出 一個 連續可微函數 $f$,若我們考慮點 $x$ 可使其 Linear transformation $f'$ 為 invertibale,則該點 $x$ 附近的 $f'$ 都為 invertible。

Comments:
1. 上述我們所提及的 invertible 我們指 一個 Linear transformation 為 invertible,嚴格來說定義如下:若  linear transformation $A: X \to Y$ 為 invertible,若下列條件滿足:
    (a.) $A$ 為 one-to-one: (i.e., $A x = Ay \Rightarrow x =y$)
    (b.) $A(X) = Y$ (i.e., $A$ maps $X$ onto $Y$ or 對任意 $y \in Y$, 存在 $x \in X$ 使得 $Ax = y$ )

2. 以下討論我們皆以 多變數向量函數 為主,亦即
若 $A \subset \mathbb{R}^n$ 且 $B \subset \mathbb{R}^m$,$n,m \in \mathbb{N}$ 則我們稱 $\bf f$ $: A \to B$ 為多變項量函數 (vector function of several variables.)


接著我們介紹何謂 $C^1$ 函數:
================
Definition: $C^1$ Continuously differentiable
我們稱一個可導的 mapping ${\bf f}: E \subset \mathbb{R}^n \to \mathbb{R}^m$ 為 continuously differentiable in $E$ (記做 ${\bf f} \in C^1(E)$) 若下列條件成立:
${\bf f}':E \to L(\mathbb{R}^n, \mathbb{R}^m)$ 為 continuous mapping ;亦即 對任意 ${\bf x} \in E$ 且 任意 $\varepsilon >0$,存在 $\delta >0$ 使得 對任意 ${\bf y} \in E$,
\[||{\bf{x}} - {\bf{y}}|| < \delta  \Rightarrow ||{\bf{f}}'\left( {\bf{x}} \right) - {\bf{f}}'\left( {\bf{y}} \right)|| < \varepsilon \]================


現在我們可以介紹 反函數定理:
Inverse Function Theorem 的基本想法:
考慮 連續函數 $f: \mathbb{R} \to \mathbb{R}$ 若 $f'>0$ 則我們知道 $f$ 為 monotonic (嚴格來說 $f$ 為 strictly increasing)。我們可推知 $f$ 必為 one-to-one 與 onto (讀者可自行驗證);故 $f$ 為 invertible。

故如果我們觀察以上結果,可發現若 $f' \neq 0$ 且 連續,則 $f$ 必為 invertible。那麼將此結果推廣到多變數向量函數的情況便會得到 Inverse Function Theorem。


======================
Theorem: Inverse Function Theorem
令 ${\bf f} \in C^1(E)$,$E $ 為 open set 且 ${\bf f}: E \subset \mathbb{R}^n \to \mathbb{R}^n$;
假設存在 點 ${\bf a} \in E$ 使得  ${\bf f}'({\bf a})$ 為 invertible linear operator 且 ${\bf{b}} = {\bf{f}}\left( {\bf{a}} \right)$ 則
  1. 存在兩 open sets $U,V \subset \mathbb{R}^n$ 使得 ${\bf{a}} \in U$, ${\bf b} \in V$; 且 $\bf f$ 為 one-to-one on $U$ 且 ${\bf f}(U) = V$。
  2. 若 $\bf g$ 為 inverse of $\bf f$ (定義在 $V$ 上) 且滿足對任意 ${\bf x} \in U$ 我們有 ${\bf{g}}\left( {{\bf{f}}\left( {\bf{x}} \right)} \right) = {\bf{x}}$  則 ${\bf g} \in C^1(V)$
======================

Comment:
Inverse Function Theorem 要求 $\bf f'$$({\bf a})$ 需要為連續 (因為 $C^1$)。此假設是必要的! (若無此假設,反函數不存在。) 我們看下面的例子:

Example
考慮 $n=1$,且考慮
\[f\left( t \right): = \left\{ \begin{array}{l}
t + 2{t^2}\sin \left( {1/t} \right),\begin{array}{*{20}{c}}
{}&{}
\end{array}t \ne 0\\
0\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array},\begin{array}{*{20}{c}}
{}&{}
\end{array}t = 0
\end{array} \right.\]則 $f'(0) =1$,$f'$ 在 $(-1,1)$ 上有界,但在 $0$ 點附近任意鄰域 $f$ 並非 one-to-one 。

Proof:
我們首先證明 $f'(0) =1$,由導數定義可知
\[\small
f'\left( 0 \right): = \mathop {\lim }\limits_{h \to 0} \frac{{f\left( {0 + h} \right) - f\left( 0 \right)}}{h} = \mathop {\lim }\limits_{h \to 0} \frac{{h + 2{h^2}\sin \left( {1/h} \right) - 0}}{h} = 1 + 2\mathop {\lim }\limits_{h \to 0} \sin \left( {1/h} \right)h = 1
\]接著我們證明 $f'$ 在 $(-1,1)$ 上有界;亦即 對任意 $x \in (-1,1)$ 要證明 存在 $M$ 使得 $|f'(t)| \le M$。觀察
\[\left| {f'\left( x \right)} \right| = \left| {1 + 4t\sin \left( {1/t} \right) - 2\cos \left( {1/t} \right)} \right| \le 1 + 4 + 2 = 7\]此處暗示了 $f'(0)$ 不為連續函數。 因為
\[\begin{array}{l}
|f'\left( t \right) - f'\left( 0 \right)| = |\left[ {1 + 4t\sin \left( {1/t} \right) - 2\cos \left( {1/t} \right)} \right] - 1|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = |4t\sin \left( {1/t} \right) - 2\cos \left( {1/t} \right)| \le 4|t| + 2 < 4\delta  + 2
\end{array}\]故不管 $\varepsilon$ 選多小都沒辦法使上述誤差項 $|f(t) - f(0)|$ 逼近任意小。

最後我們證明 $0$ 點附近任意鄰域 $f$ 並非 one-to-one:故給定任意 $r>0$ 使得任意$0$ 點附近  鄰域 $B_r(0)$,存在相異點 $x,y \in B_r(0)$ 滿足 $x = -y$ 使得在此鄰域中 $f(x) =f(y)$。注意到 $|x-y| = |x- (-x)| < r \Rightarrow |x| < r/2$ 且
\[\begin{array}{l}
f\left( x \right) - f\left( { - x} \right) = 2x\left[ {x + 2{x^2}\sin \left( {1/x} \right) - \left( { - x - 2{x^2}\sin \left( {1/x} \right)} \right)} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = {\left( {2x} \right)^2}\left[ {1 + 2x\sin \left( {1/x} \right)} \right] < {r^2}\left[ {1 + 2r} \right]
\end{array}\]由於 $r$ 為任意正數,故 $f\left( x \right) = f\left( { - x} \right)$




Proof: Inverse Function Theorem
先證 (1): 亦即要證 存在 open sets $U,V \subset \mathbb{R}^n$ 使得 ${\bf{a}} \in U$, ${\bf b} \in V$; 且 $\bf f$ 為 one-to-one on $U$ 且 ${\bf f}(U) = V$。

想法如下:要證明 one-to-one 除了利用定義之外,我們亦可透過建構輔助函數 利用 contraction principle 的幫助來得到我們所需的結果。


首先令 ${\bf{f}}'\left( {\bf{a}} \right): = A$ 且 選擇 $\lambda \in \mathbb{R}$ 使得 $2 \lambda ||A^{-1}||_L=1 $ $(*)$
(在此 $||\cdot||_L$ 表 operator norm)

由於 $\bf f$ 在 $\bf a$處可導,故可知 $\bf f'$ 為 continuous at 點 $\bf a$;亦即 對任意 $\varepsilon>0$,存在 $\delta >0$ 使得 對任意 ${\bf x} \in E$,
\[
||{\bf{x}} - {\bf{a}}|| < \delta  \Rightarrow ||{{\bf{f}}^\prime }\left( {\bf{x}} \right) - \underbrace {{{\bf{f}}^\prime }\left( {\bf{a}} \right)}_{ = A}|| < \varepsilon
\] 現在取 $\varepsilon:= \lambda$ 可推知:存在 球心為 $\bf a$ 半徑為 $\delta$ 的 open ball $U \subset E$  (表 $||{\bf x} - {\bf a}|| < \delta$) 使得 對任意 $\bf x$ $\in U$,我們有
\[
||{{\bf{f}}^\prime }\left( {\bf{x}} \right) - A|| < \lambda \ \ \ \ \ (\star)
\]現在,對任意 ${\bf y} \in \mathbb{R}^n$,定義輔助函數 $\varphi$ 如下:對任意 $\bf x$ $\in E$
\[
\varphi ({\bf{x}}): = {\bf{x}} + {A^{ - 1}}\left( {{\bf{y}} - {\bf{f}}\left( {\bf{x}} \right)} \right)
\]觀察上式,注意到 ${\bf{f}}\left( {\bf{x}} \right) = {\bf{y}}$ 若且唯若 ${\bf{x}}$ 為 fixed point of $\varphi$。 $(**)$

故我們接著計算 $\varphi'$,首先我們觀察 \[\varphi ({\bf{x}} + {\bf{h}}) - \varphi ({\bf{x}}) = {\bf{h}} - {A^{ - 1}}\left[ {{\bf{f}}\left( {{\bf{x}} + {\bf{h}}} \right) - {\bf{f}}\left( {\bf{x}} \right)} \right]\]故可推知
\[\begin{array}{l}
\varphi '({\bf{x}}) = I + {A^{ - 1}}{\bf{f}}'\left( {\bf{x}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {A^{ - 1}}\left[ {A + {\bf{f}}'\left( {\bf{x}} \right)} \right]
\end{array}\]現在對上式取 norm,並 利用 $(*)$ 與 $(\star)$ 可推知
\[\begin{array}{l}
{\left\| {\varphi '({\bf{x}})} \right\|_L} = {\left\| {{A^{ - 1}}\left[ {A + {\bf{f}}'\left( {\bf{x}} \right)} \right]} \right\|_L}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le {\left\| {{A^{ - 1}}} \right\|_L}{\left\| {A + {\bf{f}}'\left( {\bf{x}} \right)} \right\|_L}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \frac{\lambda }{2} \cdot \lambda  = \frac{1}{2}
\end{array}
\] 上式對任意 $\bf x$ $\in U$ 成立。現在利用 Mean Value Theorem 可知對任意 ${\bf x}_1$, ${\bf x}_2$ $\in U$
\[{\left\| {\varphi ({\bf{x}}_1) - \varphi ({\bf{x}}_2)} \right\|_L} \le \frac{1}{2}{\left\| {{\bf{x}}_1 - {\bf{x}}_2} \right\|_L}\]故由 Contraction principle 可知 $\varphi$ 有唯一固定點 $\bf x$ $\in U$;由 $(**)$可知存在唯一固定點  $\bf x$ 使得 ${\bf{f}}\left( {\bf{x}} \right) = {\bf{y}}$ 因此 $\bf f$ 為 one-to-one in $U$

接著我們證 ${\bf f}(U) = V$ 為 open 。
亦即要證給定任意 ${\bf y}_0 \in V$ 存在 $R>0$ 使得 開球 $B_R({\bf y}_0) \subset V$

令 $V:= {\bf f} (U)$ 則若我們取 ${{\bf{y}}_0} \in V$ 則 存在 ${\bf x}_0$ 使得 ${{\bf{y}}_0} = {\bf{f}}\left( {{{\bf{x}}_0}} \right)$ 。現在取 開球 $B_r({\bf x}_0)$ ,並且讓 $B_r({\bf x}_0)$ 的半徑 $r>0$ 足夠小 使得 開球的 closure $\bar B_r({\bf x}_0) \subset U$。

現在選 $R:= \lambda r$ 我們要證明 開球 $B_R({\bf y}_0) \subset V$,此等價證明以下 Claim:

Claim:   $\left\| {{\bf{y}} - {{\bf{y}}_0}} \right\| < \lambda r \Rightarrow {\bf{y}} \in V$
(此陳述等價對任意 $R:=\lambda r>0$ 存在 open ball $B_{\lambda r} ({\bf y}_0) \subset V$)

固定任意 $\bf y$ 滿足 $||{\bf y} - {\bf y}_0|| < \lambda r$,回憶我們先前定義的 contraction 函數 $\varphi$
\[
\varphi ({\bf{x}}): = {\bf{x}} + {A^{ - 1}}\left( {{\bf{y}} - {\bf{f}}\left( {\bf{x}} \right)} \right)
\]觀察
\[\begin{array}{l}
\left\| {\varphi ({{\bf{x}}_0}) - {{\bf{x}}_0}} \right\| = \left\| {{{\bf{x}}_0} + {A^{ - 1}}\left( {{\bf{y}} - {\bf{f}}\left( {{{\bf{x}}_0}} \right)} \right) - {{\bf{x}}_0}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \left\| {{A^{ - 1}}\left( {{\bf{y}} - {\bf{f}}\left( {{{\bf{x}}_0}} \right)} \right)} \right\| = \left\| {{A^{ - 1}}\left( {{\bf{y}} - {{\bf{y}}_0}} \right)} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} \le \left\| {{A^{ - 1}}} \right\|\left\| {{\bf{y}} - {{\bf{y}}_0}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} < \frac{1}{{2\lambda }}\lambda r = \frac{1}{2}r
\end{array}
\]若 $\bf x$ $\in \bar B_r({\bf x}_0)$ 則 $\left\| {{\bf{x}} - {{\bf{x}}_0}} \right\| \le r$ 且我們有
\[\begin{array}{l}
\left\| {\varphi ({\bf{x}}) - {{\bf{x}}_0}} \right\| = \left\| {\varphi ({\bf{x}}) - \varphi ({{\bf{x}}_0}) + \varphi ({{\bf{x}}_0}) - {{\bf{x}}_0}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} \le \left\| {\varphi ({\bf{x}}) - \varphi ({{\bf{x}}_0})} \right\| + \left\| {\varphi ({{\bf{x}}_0}) - {{\bf{x}}_0}} \right\|
\end{array}
\]由於 $\left\| {\varphi ({{\bf{x}}_1}) - \varphi ({{\bf{x}}_2})} \right\| \le \frac{1}{2}\left\| {{{\bf{x}}_1} - {{\bf{x}}_2}} \right\|$ (注意到此式成立 ${\bf x}_1, {\bf x}_2$ $\in \bar B_r({\bf x}_0)$)故可知
\[\begin{array}{l}
\left\| {\varphi ({\bf{x}}) - {{\bf{x}}_0}} \right\| \le \left\| {\varphi ({\bf{x}}) - \varphi ({{\bf{x}}_0})} \right\| + \left\| {\varphi ({{\bf{x}}_0}) - {{\bf{x}}_0}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \frac{1}{2}\left\| {{\bf{x}} - {{\bf{x}}_0}} \right\| + \frac{r}{2}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \frac{1}{2}r + \frac{r}{2} = r
\end{array}\]因此 $\varphi({\bf x}) \in B_r({\bf x}_0)$ 故 $\varphi$ 確實為 contraction on $\bar B_r({\bf x}_0)$ ;且由於 $\bar B_r$ 為 closed subset in $\mathbb{R}^n$ 故 $\bar B_r$ 為 complete ,利用 Contraction principle 可知具有唯一固定點 ${\bf x}^*$ $\in \bar B_r({\bf x}_0)$,對此 ${\bf x}^*$ 而言,我們有
\[{\bf{f}}\left( {\bf{x}^*} \right) = {\bf{y}} \in {\bf{f}}\left( {{{\bar B}_r}\left( {{{\bf{x}}_0}} \right)} \right) \subset {\bf{f}}\left( U \right) = V\]因此  ${\bf{y}} \in V$


Corollary: (f is a open mapping of E to R^n)
若 $\bf f$ $\in C^1(E)$,且 ${\bf f}: E \subset \mathbb{R}^n \to \mathbb{R}^n$ 且 若 對任意 $\bf x$,${\bf f}'({\bf x})$ 為 invertible,則 對任意 open set $W \subset E$,${\bf f}(W)$ 為 open subset of $\mathbb{R}^n$  



以下我們看個 Inverse Function Theorem 的應用:

Example
Let $L:\mathbb{R}^n \to \mathbb{R}^n$ be a bounded linear operator such that $||L(\vec x)|| = ||\vec x||$ for all $\vec x \in \mathbb{R}^n$. Define $f(\vec x):=L(\vec x) + g(\vec x)$ where $||g(\vec x)|| \le M ||\vec x||^2$ and $f \in C^1$. Show that $f$ is invertible in a neighborhood of $\vec 0 \in \mathbb{R}^n$.

Proof: First show that $f'(\vec0) = L$. Observe that
\[\begin{array}{l}
\mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{\left\| {f(\vec h) - f\left( {\vec 0} \right) - L\vec h} \right\|}}{{\left\| {\vec h} \right\|}} = \mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{\left\| {L\vec h + g(\vec h) - g(\vec 0) - L\vec h} \right\|}}{{\left\| {\vec h} \right\|}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{\left\| {g(\vec h) - g(\vec 0)} \right\|}}{{\left\| h \right\|}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \le \mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{M{{\left\| {\vec h} \right\|}^2}}}{{\left\| {\vec h} \right\|}} = \mathop {\lim }\limits_{\vec h \to \vec 0} M\left\| {\vec h} \right\| = 0\\
\Rightarrow \mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{\left\| {f(\vec h) - f\left( {\vec 0} \right) - L\vec h} \right\|}}{{\left\| {\vec h} \right\|}} = 0
\end{array}\]Hence, $f'(\vec 0) =L.$ Next, we show $L$ is invertible. Observe that for two vectors $\vec x, \vec y$ $\in \mathbb{R}^n$, suppose $L\vec x = L\vec y$, we have by linearity,

$L\left( {\vec x - \vec y} \right) = 0$. This shows $\vec x = \vec y$; i.e., $L$ is invertible. Now, by inverse function theorem, we know that $f$ is invertible in a neighborhood of $\vec 0$ $\in \mathbb{R}^n$. $\square$

2014年12月9日 星期二

[分享] Python 簡易安裝 - Anaconda

Python  (原文是大蟒蛇) 是一套程式語言,標榜簡潔易學,但由於其原始版本並沒有整合一些科學計算常用的模組,比如在數學工具常需要用到的  NumPy 模組,使用者需要再另外自行安裝這些模組套件,故這次要介紹只要安裝一個版本就可以將其常用的各種模組一網打盡的懶人?安裝方法:稱作 Anaconda  (也是一種大蟒蛇 (常指 一種叫做 森蚺 的蟒蛇 )!!)。

安裝 Anaconda 最大的好處是其支援各種作業平台 (Windows/Mac/Linux) 且完全免費,另外像是好用的 web 編碼 IPython Notebook 也整合在 Anaconda 中,可以供使用者方便在整合的環境中操作。

方法非常簡單,請至 Anaconda Scientific Python 下載 Anaconda 並安裝即可

Anaconda Scientific Python 網站

網頁開啟之後如圖所示點選下載 Download Anaconda


填入 E-mail 即可免費下載


安裝完畢 (這邊以 Windows 8 為例 (MAC 會直接顯示在桌面上)  可以再應用程式區看到


點選 Launcher 即可開始使用 Python。執行後會看到如下畫面



上圖中三種工具都可以寫 Python 程式,可依讀者喜好選用喜歡的介面嘗試。對於初學 Python 的讀者而言,個人推薦使用 Ipython-notebook 的互動式 Web 編輯介面。


那麼安裝完之後該怎麼開始學習呢?

免費學習 Python 的相關資源,如果不排斥英文的讀者,個人推薦可至 codecademy step-by-step 練習基本語法與相關功能e.g., 運算、類別、迴圈、型別;
另外亦可至 Udacity 中報名課程 Programming Foundation with Python 學習更一些直接的 Python 應用;或者 Introduction to Computer Science (with Python)

至於習慣中文的讀者可至 政大應數系 曾正男 教授的個人 BLOG 裡面也有相當豐富的 Python Note 學習。

另外如果是喜歡遊戲設計的讀者,個人推薦至 Program Arcade Games with Python and Pygame
網站。

2014年11月15日 星期六

[機率論] Martingale (3) - Example

Example: 令 $\{X_n\}$ 為 Martingale with Filtration $\mathcal{F_n}$,假設 $T$ 為 stopping time。試證 $Y_n:=X_{\min(n,T)}$ 為 Martingale with $\mathcal{F_n}$。

Proof:
首先證明 (1) $E|Y_n| < \infty $:
注意到:
\[\begin{array}{l}
{Y_n}: = {X_{n \wedge T}} = {X_n}{1_{n{\rm{ < }}T}} + {X_T}{1_{T \le n}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = {X_n}{1_{n{\rm{ < }}T}} + \sum\limits_{m = 1}^n {{X_T}{1_{T = k}}}
\end{array}\]故
\[\begin{array}{l}
E\left| {{Y_n}} \right| = E\left| {{X_{n \wedge T}}} \right| = E\left| {{X_n}{1_{n{\rm{ < }}T}} + \sum\limits_{m = 1}^n {{X_T}{1_{T = k}}} } \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le E\left| {{X_n}{1_{n{\rm{ < }}T}}} \right| + \sum\limits_{m = 1}^n {E\left| {{X_T}{1_{T = k}}} \right|} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le E\left| {{X_n}} \right| + \sum\limits_{m = 1}^n {E\left| {{X_T}} \right|}  < \infty
\end{array}\]

接著我們證明 (2) : $Y_n \in \mathcal{F}_n $
觀察 \[{Y_n}: = {X_{n \wedge T}} = {X_n}{1_{n{\rm{ < }}T}} + \sum\limits_{m = 1}^n {{X_T}{1_{T = k}}} \]由於 $1_{T>n} = 1_{T \le n}^c \in \mathcal{F}_n$ 且 $X_m \in \mathcal{F}_m \subset \mathcal{F}_n$ 且 $1_{T=m} \in \mathcal{F}_m \subset \mathcal{F}_n$ 對任意 $m\le n$ 故
\[{Y_n}: = \underbrace {{X_n}}_{ \in {F_n}}\underbrace {{1_{n{\rm{ < }}T}}}_{ \in {F_n}} + \underbrace {\sum\limits_{m = 1}^n {{X_T}{1_{T = k}}} }_{ \in {F_n}} \in {F_n}\]

最後我們證明 (3): $E[Y_{n+1}|\mathcal{F}_n] = E[X_{}]$ 注意到
\[\begin{array}{l}
E[{Y_{n + 1}}|{{{\cal F}}_n}] = E[{X_{n + 1}}{1_{n + 1 < T}} + {X_T}{1_{T \le n + 1}}|{{{\cal F}}_n}]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = E[{X_{n + 1}}{1_{n + 1 < T}}|{{{\cal F}}_n}] + E[{X_T}{1_{T \le n + 1}}|{{{\cal F}}_n}]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = E[{X_{n + 1}}{1_{n + 1 < T}}|{{{\cal F}}_n}] + E[\sum\limits_{k = 1}^n {{X_k}{1_{T = k}}}  + {X_{n + 1}}{1_{T = n + 1}}|{{{\cal F}}_n}]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = E[{X_{n + 1}}{1_{n + 1 < T}}|{{{\cal F}}_n}] + {X_T}{1_{T \le n}} + E[{X_{n + 1}}{1_{T = n + 1}}|{{{\cal F}}_n}]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = {X_n}{1_{n + 1 \le T}} + {X_T}{1_{T \le n}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = {X_n}{1_{n < T}} + {X_T}{1_{T \le n}} = {Y_n}
\end{array}\]

2014年10月25日 星期六

[數學分析] Compactness 與 Totally Boundedness

令 $X$ 為 metric space 且 metric 為 $d$;亦即 $(X,d)$ 為 metric space。

==========================
Definition: Compact Metric Space
(a) 由 open subsets 所形成的集合  $\{G_\alpha\}_{\alpha \in A} $ 被稱為 open cover 若 下列條件成立:
對任意 $x \in X$ 存在 $\alpha \in A$ 使得 $x \in G_\alpha$。

若 index set $A$ 為 finite 則 $\{G_\alpha\}$ 為 finite open cover。

(b) 我們說 metric space $(X,d)$ 為 compact 若下列條件成立:
對任意 open cover of $X$,存在 有限個 subcover of $X$。
==========================

Comment
注意到上述定義在 metric space $(X,d)$ 之上,若我們現在考慮其上的子集合:
\[
A \subset X
\]則 $A$ 仍為一個 metric space 且 metric 為 $d$;亦即 $(A,d)$ 仍為一個 metric space。


==========================
Definition: Compact Set
集合 $A \subset X$ 為 compact 若下列條件成立:
metric space $(A,d)$ 為 compact (亦即:對任意 open cover 存在 有限 subcover of $A$。)
==========================



==========================
Definition: Relatively Compact
集合 $A \subset X$ 稱為 relatively compact 若下列條件成立
\[
\bar A \subset X \text{ is compact}
\]上述 $\bar{A}$ 表示 closure of $A$
==========================

==========================
Theorem: Heine-Borel Theorem
若 $A \subset \mathbb{R}^n$ (或者 $\mathbb{C}^n$) 為 closed + bounded 則 $A$ 為 compact。
==========================

==========================
Definition: Sequentially Compact
我們說一個 metric space $(X,d)$ 為 sequentially compact 若下列條件成立
對任意 sequence in $X$ 存在 收斂 subsequence 。
==========================

==========================
Definition: Totally Bounded
一個 metric space $(X,d)$ 稱為 totally bounded 若下列條件成立:
對任意 $\varepsilon>0$,存在有限個 以半徑為 $\varepsilon$ 的 open Ball $\mathcal{B}_\varepsilon$ 所組成的集合 並且 covers $X$。
==========================


Example
考慮 $l^p$ space $:= \{\{a_n\}_n: \sum_{n}^\infty |a_n|^p < \infty, 0 <p <\infty\}$;且定義 metric 如下
\[d\left( {{a_n},{b_n}} \right): = {\left( {\sum\limits_{n = 1}^\infty  {|{a_n} - {b_n}{|^p}} } \right)^{\frac{1}{p}}}\]

Question: 試定義 半徑為1 且球心為 $\{0,0,0,...\}$ 的 open ball $\mathcal{B} \in l^p$:
ANS:\[
\mathcal{B}: = \left\{ {{{\left\{ {{a_n}} \right\}}_{n \in \mathbb{N}}}:\sum\limits_{n = 0}^\infty  {{{\left| {{a_n}} \right|}^p} < 1} } \right\}
\]
現在定義 example element in $l^p$
\[\left\{ {{e_n}^{\left( k \right)}} \right\}: = \left\{ \begin{array}{l}
0,\begin{array}{*{20}{c}}
{}
\end{array}n \ne k\\
1,\begin{array}{*{20}{c}}
{}
\end{array}n = k
\end{array} \right.
\]舉例而言,若 $k=1$ 則 上述定義表示 $e_n^{(1)} = \{1, 0, 0, 0,...\}$ 若 $k=2$ 則上述定義表示 $e_n^{(2)} = \{0, 1, 0, 0,...\}$

注意到
1. $\{e_n^{(k)}\} \in  \mathcal{\bar{B}}$
2. 且 example element 的 距離 (metric, $d$) 為 \[d({e^{(k)}},{e^{(m)}}) = {\left( {\sum\limits_{n = 0}^\infty  {{{\left| {e_n^{(k)} - e_n^{\left( m \right)}} \right|}^p}} } \right)^{\frac{1}{p}}} = {2^{\frac{1}{p}}}\]

Question: 試問 $ \mathcal{\bar{B}}$ 是否為 totally bounded?
NO! 亦即 存在 $\varepsilon>0$,使得 沒有 有限的 collection of open balls covers $X$

取 $\varepsilon < 1/2^p$ 則可證明 沒有有限的 collection of open balls covers $X$。


以下我們看個 totally bounded 的結果

=============
FACT: 若 $X$ 為 totally bounded metric space,則 $X$ 具有 countable 且 dense 的子集合 (亦即 $X$ 中存在 separable 的子集合)。
=============
Proof:
此為存在性的定理,我們要找出 一個 $X$ 的子集合 滿足 countable 與 dense。

首先由於 $X$ 為 totally bounded metric space,由定義可知 對任意 $\varepsilon >0$, 存在有限個 由半徑為 $\varepsilon>0$ 的 open ball $\mathcal{B}$ 所組成 的  cover of $X$。故對任意 $n \in \mathbb{N}$ 我們選 $\varepsilon_n:=1/n$,並且令有限個點 $x_1,...x_n \in X$,則由 toally boundedness of $X$ 我們可建構集合
\[
A_n := \{x_1, x_2,...,x_n\}
\] 使得 $X \subset \cup_i^n \mathcal{B}(x_i) $。那麼若我們現在令
\[
A:= \cup_n A_n
\] 則此集合 $A \subset X$ 且為 countable。

接著我們證集合 $A$ 為 dense。亦即要證明 :
對任意 $z \in X$,存在一組 sequence $\{z_n\} \in A$ 使得 $z_n \rightarrow z$。

現在給定任意 $z \in X$ ,則由 totally boundedness 我們可知必定存在 一個 點 $z_n \in A$ 使得 $d(z_n, z) < 1/n$ ,故對任意 $n \in \mathbb{N}$ 我們可建構一組 sequence $\{z_n\}$ 滿足
\[
\lim_{n \rightarrow \infty} d(z_n,z) =0
\]亦即 $z_n \rightarrow z$。

===================
Lemma 1: 任意 closed subset $F$ of compact metric space $X$ 必為 compact。
Proof: omitted.
===================

===================
Lemma 2: 任意 在 $X$ 中的無窮集合 必有 accumulation point 若且為若 $X$ 為 sequentially compact。
===================

Proof: $(\Rightarrow)$ 假設 在 $X$ 中的無窮集合 必有 accumulation point,我們要證明  $X$ 為 sequentially compact;亦即給定任意 sequence in $X$ ,要證明 存在 有收斂 subsequence 。

現在取 $\{p_n\}$ 為 $X$ 中任意 sequence。 將此 $\{p_n\} $ 中的元素形成集合 $A \subset X$ 且考慮以下兩種情況:
1.若 集合 $A$ 中元素為有限個,則 $\{p_n\}$ sequence 中 必定存在一點為重複出現無限次,則我們可取此點為形成 constant subsequence。
2. 若 集合 $A$ 中元素為無限個,亦即 $\{p_n\}$ 為無限個相異元素;由 假設可知
"任意 在 $X$ 中的無窮集合 必有 accumulation point "
$A$ 為 $X$ 中的無窮集合,必有  accumulation point ,此等價為 $\{p_n\}$ 具有收斂子數列。

$(\Leftarrow)$ 假設 $X$ 為 sequentially compact,要證明 任意 在 $X$ 中的無窮集合 必有 accumulation point。

令 $A \subset X$ 為無窮集合,我們要證 $A$ 必有 accumulation point。
我們取 $\{a_n\} \subset A$ 為 sequence,則由於  $X$ 為 sequentially compact,故可知給定任意sequence in $X$,必有收斂子數列。此等價為 $A$ 必有 accumulation point。

===================
Lemma 3: 若 $X$ 為 compact,則 $X$ 為 sequentially compact。
===================
Proof:
要證 $X$ 為 sequentially compact;可由 Lemma 2 我們證 任意 在 $X$ 中的無窮集合 必有 accumulation point 。

利用歸謬法(Proof by contradiction):假設 $X$ 為 compact,且存在一個 $X$ 中的無窮集合,但此集合並沒有 accumulation point 。我們要證矛盾。

故現在令 $Y \subset X$ 為此 無窮集合 (沒有 accumulation point)。則由於 $Y$ 並沒有 accumulation point ,我們可推知 對任意 $y \in Y$,存在適當的半徑 $r>0$ 使得開球 $B_r(y)$ 與 $Y$ 的交集
 \[B_r(y) \cap Y = \{y\}
\] 且由於  $Y$ 無 accumulation point,我們亦另外推知 $Y$ 為 closed。 ($Y$ is closed iff its contains all its accumulation point,但由於 $Y$ 並無 accumulation point,故 $Y$ 為 closed。)

由於 $X$ 為 compact,且 $Y \subset X$ 為 closed,由 Lemma 1 可知 $Y$ 亦為 compact。

對任意 $y$,我們確實可透過 $B_r(y)$ 來 cover $Y$ (透過 $ B_r(y) \cap Y = \{y\}$ ) 故由 compactness of $Y$ 可知必定存在有限個 subcover 來蓋住 $Y$。但此與 $Y$ 為無窮集合 矛盾。 $\square$

現在我們回憶 totally bounded
==========================
Definition: Totally Bounded
一個 metric space $(X,d)$ 稱為 totally bounded 若下列條件成立:
對任意 $\varepsilon>0$,存在有限個 以半徑為 $\varepsilon$ 的 open Ball $\mathcal{B}_\varepsilon$ 所組成的集合 並且 covers $X$。
==========================

Definition: 一個集合 $A$ 為 $\varepsilon$-net for space $X$ 若下列條件成立:
$A$ 為 finite set 且對 $x \in A$,開球 $B_\varepsilon(x)$ 建構一個 open cover of $X$。

現在我們給出等價定義: 我們說 $A$ is totally bounded 若 對任意 $\varepsilon>0$ 而言,我們有 $\varepsilon$-net。

Claim: 若 $X$ 為 sequentially compact,則 集合 $A \subset X$ 滿足 $p,q \in A, p \neq q$ 且 $d(p,q) \ge \varepsilon$ 為 有限集。
proof:


Lemma 4: 一個 sequentially compact 的 metric space $X$ 為 totally bounded + complete。

Proof:
先證 totally bounded。給定 $\varepsilon$,要建構 一個 $\varepsilon$-net。

現在令 $A \subset X$ 為一集合 滿足其中的元素之間互相之距離大於 $\varepsilon$,由 Claim 可知此集合 $A$ 為 有限集合,故對任意點 $p_i \in A$ 則我們可對每一個 $i$,建構一開球 $B_\varepsilon(p_i)$ 且此開球確實 蓋住 $X$。
亦即我們確實建構出 $\varepsilon$-net for $X$ 故  $X$ 為 totally bounded。$\square$

接著我們證  $X$ 為  complete:亦即給定任意 Cauchy sequence $\{x_n\} \subset X$ 要證明 此 $\{x_n\}$ 收斂在 $X$ 上。

由於 $X$ 為 sequentially compact ,故此 $\{x_n\}$ 具有收斂子數列 $\{x_{n_k}\}$在 $X$ 上。稱其極限為 $l$ 現在觀察 對足夠大的 $N$ 使得當 $n,n_k \ge N$ 我們有
\[\begin{array}{l}
\left| {{x_n} - l} \right| = \left| {{x_n} - {x_{{n_k}}} + {x_{{n_k}}} - l} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le \left| {{x_n} - {x_{{n_k}}}} \right| + \left| {{x_{{n_k}}} - l} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \varepsilon /2 + \varepsilon /2 < \varepsilon
\end{array}\]故$X$ 為  complete。 $\square$

2014年10月1日 星期三

[數學分析] Weierstrass Theorem (1) - 先備概念

回憶在數學分析的內容中,我們試圖利用 $\mathbb{Q}$ 在 $\mathbb{R}$ 中 dense的想法,指出 任意在 $\mathbb{R}$ 上的實數 $r$,皆可透過 一組 sequence $\{q_n\} \in \mathbb{Q}$ 逼近 。也就是說 $q_n \rightarrow r$ 當 $n \rightarrow \infty$。那麼我們想問在函數上是否也有類似的概念? Weierstrass Approximation Theorem 便是試圖回答這個問題。

Weierstrass  Approximation Theorem 主要想法: 利用多項式 均勻收斂 連續函數!!

不過在介紹之前,我們需要一些先備知識。
首先看個 算子 (operator) 的概念:
定義 $A: \text{one function} \rightarrow \text{different function}$ 為一個算子(operator)

我們看個例子:

------------
Example
Fourier transform of 函數 $f$ 為一個算子 (將函數 $f$ 映射到另一個函數 $F$)
\[F(j\omega ) = \int_{ - \infty }^\infty  f (t){e^{ - j\omega }}dt
\]-----------

那麼算子何其多? 哪一種算子適合我們?? 以下我們介紹一個即為有用的特殊算子:摺積(Convolution)

===================
Definition: Convolution (Integral)
給定兩可積函數 $f,g$ on $\mathbb{R}$,則其折積(convolution) 定義為
\[(f*g)\left( x \right): = \int f (x - y)g(y)dy = \int g (x - y)f(y)dy
\]===================

Example
$f,g$ 為在 $[-1,1]$ 上的週期函數,且 $|\delta| <1$ \[f\left( x \right): = \left\{ \begin{array}{l} 1/2\delta ,\begin{array}{*{20}{c}} {}&{} \end{array}x \in \left[ { - \delta ,\delta } \right]\\ 0,\begin{array}{*{20}{c}} {}&{}&{} \end{array}o.w \end{array} \right.
\]試求其 convolution $(f * g)(x)=?$
Proof:
\[\begin{array}{l}
f*g: = \int_{ - 1}^1 {f\left( y \right)g\left( {x - y} \right)dy}  = \int_{ - \delta }^\delta  {\frac{\delta }{2}g\left( {x - y} \right)dy} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \frac{\delta }{2}\int_{ - \delta }^\delta  {g\left( {x - y} \right)dy}. \ \ \ \ \square
\end{array}
\]

Convolution 的好處:可以保留原函數的本身的優點!!

===================
FACT: 令 $K$ 為 compact interval,若 $f \in \mathcal{C}^{\infty}(\mathbb{R})$ (smooth function) 且 $g$ 為 可積函數,則
\[
(f * g)(x) = \int_K f(y)g(x-y)dy
\]亦為在 $K$ 上 smooth function
==================
Proof: omitted.

現在我們看個函數
===================
Definition: A Specific Smooth Function
令 $\phi(x)$ 為 $\mathbb{R}$ 上的 smooth function 且滿足下列條件
在 $(-1,1)$, $\phi>0$ ;且在 $(-1,1)^c$, $\phi=0$ ;另外我們限定此函數  $\phi$ 必須滿足下列積分
\[
\int_{-1}^{1} \phi(t) dt =1
\]===================

有了上述函數,我們可以定義算子 Operator $A$ 如下:
對 $s>0$,定義 $\phi_s$ 為\[{\phi _s}(t): = \frac{1}{s}\phi (\frac{t}{s});\;\;\;\int_{-1}^1 \phi  dt = 1\]且
\[
A_s f(t) :=( \phi_s * f)(t) = \int \phi_s(t) f(x-t) dt
\]其中 $\phi \ge 0$ on $[-1,1]$ 且 $\phi =0$ on $[-1,1]^c$ 。
============
Theorem: Preliminary Lemma for Weierstrass Approximation Theorem
令 $f$ 為 有界 連續 函數 on $\mathbb{R}$ ($f \in \mathcal{C}(\mathbb{R})$) 且 令 $J$ 為任意 compact interval in $\mathbb{R}$。則 當 $s \rightarrow 0$,我們有 $A_s f \rightarrow f$ 均勻收斂 on $J$。
============

Proof:
令 $\varepsilon>0$ ,我們要證明 $A_s f \rightarrow f$ 均勻收斂;(注意到上述定理陳述是當 $s \rightarrow 0$,故令 $n := 1/s$) 故要證 存在 $N>0$ 使得 $n > N$ 我們有
\[
|A_sf(x) - f(x) | < \varepsilon
\]對任意 $x \in J$ 。

觀察
\[\small
\begin{array}{l}
|{A_s}f(x) - f(x)| = \left| {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)f\left( {x - t} \right)dt}  - f\left( x \right)} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \left| {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)f\left( {x - t} \right)dt}  - f\left( x \right)\underbrace {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)dt} }_{ = 1}} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \left| {\int_{ - \infty }^\infty  {\left[ {f\left( {x - t} \right) - f\left( x \right)} \right]{\phi _s}\left( t \right)dt} } \right| \le \int_{ - \infty }^\infty  {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon
\end{array}\]注意到上式中當 $|t| >s$時, $\phi_s =0$故上式積分範圍為
\[|{A_s}f(x) - f(x)| \le \int_{ - s}^s {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon \]
故如果可以讓上式 $|f(x-t) - f(x)|$ 對任意 $x \in J$ 都可使其任意小便完成證明。故現在透過 $J$ 為任意 compact interval on $\mathbb{R}$,我們可推知 $f$ 在 $J$ 上為 uniform continuous。亦即我們可選 $\delta >0$ 使得對任意 $u,v \in J$,
\[
|u-v| < \delta \Rightarrow |f(u) - f(v)| < \varepsilon
\]取 $u :=x, v := x+t \in J$ 則我們可知
\[
|u-v| = |x - (x+t)| < \delta \Rightarrow  |f(x) - f(x-t)| < \varepsilon
\]也就是說只要能找到 $N$ 使得 $n >N$ 且滿足 $|t| < \delta$ 則 我們便會有
\[|{A_s}f(x) - f(x)| \le \int_{ - s}^s {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon \]由於 $n =1/s; \; n >N \Rightarrow s < 1/N$ 且又由 $\phi_s(t)$ 定義可知 $t \in [-s,s]$故取 $N = 1/\delta$ 則上述自動滿足。$\square$

2014年8月23日 星期六

[系統理論] 透過 Fourier transform of correlation function 求隨機過程的頻譜

這次要介紹對於一個 隨機過程而言,如何對其討論 Fourier transform ?

給定 廣義平穩 (Wide-sense stationary (WSS) )隨機過程 $X_t$,其 autocorrelation function  僅與任意給定兩時刻 $t_1, t_2$之差有關,故我們定義
\[
E[X_{t_1} X_{t_2}] :=R_X(t_1 - t_2)
\]現在令 $t_1 = t + \tau$ 且 $t_2 = t$ 我們可將上式 autocorrelation function, $R_X(t_1 - t_2)$ 用一單變數函數改寫,記做 $R_X( \tau)$ 且滿足下列定義
\[
R_X(\tau) :=E[X_{t + \tau}X_{t}]
\]

我們可對 $R_X(\tau)$ 取 Fourier transform 如下
\[
S_X(f) := \int_{-\infty}^{\infty}R_X(\tau)e^{-j 2 \pi f \tau}d\tau
\]且 Inverse Fourier transform
\[
R_X(\tau) = \int_{-\infty}^{\infty}S_X(f) e^{j 2 \pi f \tau} d f
\]
Comment:
上述 $S_X(f)$ 又稱為功率頻譜密度( power spectral density ),我們會在以下說明。


隨機過程的功率 以及 功率頻譜 (Power Spectral and Power in Process)
為了解釋上述的結果現在我們從能量觀點來觀察一個隨機過程:
對一個隨機過程 $X_t$ 其 total energy 定義為
\[
\int_{-\infty}^{\infty} X_t^2dt
\] 而我們亦可定義 平均功率 (average power) 為
\[
\lim_{T \rightarrow \infty} \frac{1}{2T} \int_{-T}^{T} X_t^2 dt
\]但由於上述 total energy 與 average power 為對隨機過程平方做積分,其積分結果仍為隨機變數。故我們需加上期望值確保其不再隨機。故我們定義 期望平均功率(expected average power)
\[
P_X := E\left[ \lim_{T \rightarrow \infty} \frac{1}{2T} \int_{-T}^{T} X_t^2 dt \right]
\]對於 WSS 隨機過程,我們改寫上式 (透過 Fubini's theorm可以對換 期望值 與 積分順序。)
\[\begin{array}{l}
{P_X} = \mathop {\lim }\limits_{T \to \infty } \frac{1}{{2T}}\int_{ - T}^T {E\left[ {X_t^2} \right]} dt\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \mathop {\lim }\limits_{T \to \infty } \frac{1}{{2T}}\int_{ - T}^T {{R_X}\left( {t - t} \right)} dt = \mathop {\lim }\limits_{T \to \infty } \frac{1}{{2T}}\int_{ - T}^T {{R_X}\left( 0 \right)} dt\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \mathop {\lim }\limits_{T \to \infty } \frac{1}{{2T}}{R_X}\left( 0 \right)\int_{ - T}^T 1 dt\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {R_X}\left( 0 \right)
\end{array}
\]由之前我們定義的對 WSS隨機過程之 Fourier transform (事實上這邊我們用 Inverse Fourier transform),可知
\[\begin{array}{l}
{R_X}(\tau ) = \int_{-\infty} ^\infty  {{S_X}} (f){e^{j2\pi f\tau }}df\\
 \Rightarrow {R_X}\left( 0 \right) = \int_{-\infty} ^\infty  {{S_X}} (f)df
\end{array}\]且由於我們有 $E[X_t^2] = R_X(t-t) = R_X(0)$,故總結以上結果,我們有
\[
P_X := E[X_t^2] = R_X(0) = \int_{-\infty} ^\infty  {{S_X}} (f)df
\]

注意到 $S_X(f)$ 為頻率的函數,故我們稱其為 spectral,且又如同機率 $P(\cdot)$ 為機率密度 $f$ 的積分 e.g., $P(X \in B)  =  \int_B f(x)dx $,對於 expected average power 而言
\[
{P_X} = \int_{-\infty} ^\infty  {{S_X}} (f)df
\]亦可發現 $S_X(\cdot)$ 扮演類似 機率密度的角色,故我們稱之為 spectral density。

以下我們羅列幾個重要的已知結果:

========================
FACT 1: WSS 隨機過程的 autocorrelation function $R_X(t)$ 確實為 real even function ($R_X(t)$ 為實 偶函數)。
========================

Proof: 
由 $R_X(\tau)$ 之定義 $E[X_{t + \tau}X_t]$  可知其為 real function,故我們僅須證明其亦為 even function,也就是要證明 $R_X(\tau) = R_X(-\tau)$,故我們寫下
\[\begin{array}{l}
{R_X}\left( \tau  \right) = {R_X}\left( {\left( {t + \tau } \right) - t} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = E\left[ {{X_{t + \tau }}{X_t}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = E\left[ {{X_t}{X_{t + \tau }}} \right] = {R_X}\left( {t - \left( {t + \tau } \right)} \right) = {R_X}\left( { - \tau } \right)  \ \ \ \ \square
\end{array}\]

========================
FACT 2: 令WSS 隨機過程 $X_t$ 的 autocorrelation function $R_X(\tau)$ ,則對任意 $\tau$,
\[
|R_X(\tau)| \le R(0)
\]========================

Proof: 
我們要證明 $R(0)$ 確實為 $R_X(\tau)$ 的最大值。現在觀察
\[|{R_X}(\tau )| = |E[{X_{t + \tau }}{X_t}]|
\]由 Cauchy-Schwarz inequality $|E[XY]|^2 \le E[X^2]E[Y^2]$ 可知
\[\begin{array}{l}
|{R_X}(\tau )| = |E[{X_{t + \tau }}{X_t}]|\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le \sqrt {E[{X_{t + \tau }}^2]E[{X_t}^2]}
\end{array}\]且 $ {R_X}(0) = \underbrace {E[X_t^2]}_{ \ge 0} = \underbrace {E[{X_{t + \tau }}^2]}_{ \ge 0} \ge 0$ 我們可得
\[{R_X}(0) \ge \sqrt {{R_X}^2\left( 0 \right)}  = {R_X}\left( 0 \right) \ \ \ \ \square
\]


透過上述結果 (FACT 1 )我們可以證明 $S_X(f)$ 亦為 real and even function。

========================
FACT 2:
$S_X(f)$ 為 real even function
========================

Proof
利用 Euler formula: $e^{j \omega t} = \cos(\omega t) + j \sin (\omega t)$,我們可改寫 $S_X(f)$
\[\begin{array}{l}
{S_X}(f): = \int_{ - \infty }^\infty  {{R_X}} (\tau ){e^{ - j2\pi f\tau }}d\tau \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_{ - \infty }^\infty  {{R_X}} (\tau )\cos \left( {2\pi f\tau } \right)d\tau  + j\int_{ - \infty }^\infty  {{R_X}} (\tau )\sin \left( {2\pi f\tau } \right)d\tau \ \ \ \ (*)
\end{array}
\]由 FACT 1 於 $R_X(\tau)$ 為 real 且 even。且 $\cos(2 \pi f \tau)$ 為 even function,$\sin( 2 \pi f \tau)$ 為 odd function,故我們可推知

${R_X}(\tau )\cos \left( {2\pi f\tau } \right)$ 為 even function

${R_X}(\tau )\sin \left( {2\pi f\tau } \right)$ 為 odd function

又注意到 $(*)$ 中 等號右方第二個積分式:
\[
\int_{ - \infty }^\infty  {{R_X}} (\tau )\sin \left( {2\pi f\tau } \right)d\tau
\] 其中的 integrand 為 real odd function,故積分值為 $0$,亦即 $(*)$ 式變為
\[
S_X(f) = \int_{ - \infty }^\infty  {{R_X}} (\tau )\cos \left( {2\pi f\tau } \right)d\tau
\]上式積分中的 integrand 為 real even function,故 $S_X(f)$ 亦為 real and even。 $\square$

2014年7月9日 星期三

[隨機過程] 布朗運動的 Reflection Principle 與 First Passage Time Problem

定義 $\{ W_t\}$ 為標準布朗運動。現給定常數邊界 $b >0$,定義 停止時間 (stopping time) 或稱 首次穿越時間 (First passage time)
\[
\tau_b := \inf \{ t : W_t \ge b\}
\]
我們想要計算 $P(\tau_b \le t) = ?$

上述問題稱為 首次穿越時間問題 (First passage time (FPT) problem)

=========
那麼如何求解上述FPT問題呢?

首先注意到
\[
\{ \tau_b \le t, W_t >b \} \equiv \{ W_t > b\}
\] 上式成立由於布朗運動的 sample path 連續性 (Path Continuity),與 $W(0)=0$,故 $W_t > b  \Rightarrow \tau_b \le t$,亦即 $\{ W_t > b\} \subset \{ \tau_b \le t\}$。故
\[
\{ \tau_b \le t, W_t >b \} \equiv \{ W_t > b\}
\]

現在我們計算 $P(\tau_b \le t) $,利用 Law of total Probability 可得
\[\begin{array}{l}
P({\tau _b} \le t) = P({\tau _b} \le t,{W_t} < b) + P({\tau _b} \le t,{W_t} > b) \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = P({W_t} < b|{\tau _b} \le t)P\left( {{\tau _b} \le t} \right) + P({\tau _b} \le t,{W_t} > b)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = P({W_t} < b|{\tau _b} \le t)P\left( {{\tau _b} \le t} \right) + P({W_t} > b) ....\ \ \ \ (*)
\end{array}
\]上式中的 $P(W_t > b)$ 可以由布朗運動定義計算出來,因為 $W_t \sim \cal{N}(0,t)$,故
\[
P(W_t > b) = 1 - P(W_t \le b) = 1 - \Phi(\frac{b}{\sqrt{t}})
\] 其中 $\Phi(\cdot)$ 為 Standard Normal Cumulative Distribution Function.

接著,我們計算 $P({W_t} < b|{\tau _b} \le t)$,事實上由 Path Continuity 我們可知 $W_{\tau_b} = b$,故在給定 $\tau_b \le t$ 的時候,隨機過程在時刻 $t$ 時 高於 邊界 $b$ 的機率 與 低於 邊界 $b$ 的機率應該相同;亦即
\[
P({W_t} < b|{\tau _b} \le t) = \frac{1}{2}
\]
(上述結果稱為 Reflection Principle ,嚴格證明需要利用 Strong Markov property,但此處我們略過)。下圖亦顯示了 Reflection Principle 的想法



故我們將上述結果代回 $(*)$,可得
\[\begin{array}{l}
P({\tau _b} \le t) = P({W_t} < b|{\tau _b} \le t)P\left( {{\tau _b} \le t} \right) + P({W_t} > b)\\
 \Rightarrow P({\tau _b} \le t) = \frac{1}{2}P\left( {{\tau _b} \le t} \right) + P({W_t} > b)\\
 \Rightarrow P\left( {{\tau _b} \le t} \right) = 2P({W_t} > b) = 2\left( {1 - \Phi \left( {\frac{b}{{\sqrt t }}} \right)} \right)
\end{array}\]



Ref: Joseph T. Chang, "Stochastic Processes Lecture Note" Yale University.

2014年7月8日 星期二

[線性系統] 控制性矩陣 與 非奇異轉換 (Controllability matrix & Non-singular transformation)

延續先前線性系統理論 對於非奇異轉換的討論,由於 轉移函數 用 State space 表示實現的方法並不唯一;e.g., controllable canonical form, observable canonical form, digonal form. 故現在我們再進一步審視此問題

給定轉移函數 $H(s)$,現考慮對此轉移函數的任兩種 狀態空間實現 $\Sigma$ 與 $\tilde \Sigma$
\[\left\{ \begin{array}{l}
\Sigma  = (A,B,C,D)\\
\tilde \Sigma  = (\tilde A,\tilde B,\tilde C,\tilde D)
\end{array} \right.\],亦即
\[
H(s) = H_{\Sigma }(s) = C(sI-A)^{-1}B + D \equiv  \tilde{C} (sI- \tilde A)^{-1} \tilde B + \tilde D = H_{\tilde{\Sigma }}(s)
\]

那麼我們想知道是否存在一個 $n \times n$ 的非奇異轉換矩陣 $T$ 使得 我們有映射 $\Sigma \rightarrow \tilde \Sigma$

由先前文章可知,$\tilde A = T A T^{-1}$,$\tilde B = TB$,$\tilde C = C T^{-1}$,$\tilde D = D$,現在觀察下式
\[\left\{ \begin{array}{l}
\tilde B = TB\\
\tilde A\tilde B = \left( {TA{T^{ - 1}}} \right)TB = TAB\\
{{\tilde A}^2}\tilde B = \left( {TA{T^{ - 1}}} \right)TAB = T{A^2}B\\
 \vdots \\
{{\tilde A}^{n - 1}}\tilde B = \left( {TA{T^{ - 1}}} \right)TAB = T{A^{n - 1}}B
\end{array} \right.
\] 我們可以看出上式中一些運算的規則,現在將其改寫為更簡潔的形式如下
\[\underbrace {\left[ {\begin{array}{*{20}{c}}
{\tilde B}&{\tilde A\tilde B}& \cdots &{{{\tilde A}^{n - 1}}\tilde B}
\end{array}} \right]}_{: = {C_{\tilde \Sigma }}} = T\underbrace {\left[ {\begin{array}{*{20}{c}}
{AB}&{{A^2}B}& \cdots &{{A^{n - 1}}B}
\end{array}} \right]}_{: = {C_\Sigma }}
\] 亦即 $C_{\tilde \Sigma}= T C_{\Sigma}$ . $(\star)$

上式 $C_{\Sigma}$ 與 $C_{\tilde \Sigma}$ 稱為 控制性矩陣 (Controllability matrix)。故 非奇異矩陣 $T$ 可透過上述關係得到。

注意到如果為單輸入單輸出 (SISO) 系統,且假設  $C_{\Sigma}$ 與 $C_{\tilde \Sigma}$ 為方陣。 $C_{\Sigma}$ 為 non-singular,則我們可以找到非奇異轉換矩陣 $T$
\[
T = C_{\tilde \Sigma}C_{\Sigma}^{-1}
\]

若 多輸入系統,則無法直接求解反矩陣,故我們需先使 $(\star)$ 左右變成方陣:
\[
\underbrace {{C_{\tilde \Sigma }}{C_\Sigma }^T}_{\underbrace {\left( {n \times nm} \right) \times \left( {mn\times n} \right)}_{n \times n}} = T\underbrace {{C_\Sigma }{C_\Sigma }^T}_{\underbrace {\left( {n \times nm} \right) \times \left( {mn \times n} \right)}_{n \times n}}
\]現在   ${{C_\Sigma }{C_\Sigma }}$ 為 non-singular,則我們可以找到非奇異轉換矩陣 $T$
\[
T = {C_{\tilde \Sigma }}{C_\Sigma }^T{\left( {{C_\Sigma }{C_\Sigma }^T} \right)^{ - 1}}
\]

故 我們知道如果要有 非奇異矩陣 $T$,則矩陣 $C_{\Sigma} C_{\Sigma }^T$ 必須非奇異,故我們有下列 Controllability Rank conditon:

Controllability Rank Condition
 $C_{\Sigma} C_{\Sigma }^T$ 為非奇異 若且為若 $\text{rank}{C_{\Sigma}} = n$


Comment:
1. 在 MATLAB中,給定動態系統 $A, B$ 矩陣,則我們可以使用  C = ctrb(A,B) 指令來直接幫助我們計算 Controllability Matrix, C,接著再用 rank(C) 指令確認此矩陣是否滿足我們的 Controllability Rank Condition ,如果滿足我們稱此系統為可控制(controllable)。

2. non-singular transform 不改變 Eigenvalues,亦即
\[eig\left( {TA{T^{ - 1}}} \right) = eig\left( A \right)
\]其中 $eig(\cdot)$ 表特徵值。
Proof
令 $T$ 為 nonsingular transformation matrix,且 $\lambda_i$ 為 $TAT^{-1}$ 矩陣對應的 eigenvalue,也就是說 $TAT^{-1}$ 的 eigenvalues 滿足 $\det(\lambda_i I - TAT^{-1}) =0$。故
\[\begin{array}{l}
\det \left( {{\lambda _i}I - TA{T^{ - 1}}} \right) = 0\\
 \Rightarrow \det \left( {{\lambda _i}T{T^{ - 1}} - TA{T^{ - 1}}} \right) = 0\\
 \Rightarrow \det \left( {T\left( {{\lambda _i}I - A} \right){T^{ - 1}}} \right) = 0\\
 \Rightarrow \det \left( T \right)\det \left( {{\lambda _i}I - A} \right)\det \left( {{T^{ - 1}}} \right) = 0
\end{array}\]由於 $T$ 為 nonsingular,故 $T^{-1}$ 存在且 $\det(T) \neq 0$,  $\det(T^{-1}) \neq 0$。故只有
\[
\det(\lambda_i I - A) =0
\]亦即 $\lambda_i$ 亦為 矩陣 $A$ 的 eigenvalue。 $\square$

[線性系統] 實現定理 與 非奇異轉換

這次要介紹 線性系統理論 中的一個重要結果:稱作實現理論 ( Realization Theory )

考慮一個轉移函數 $H(s)$ 可以將其由 狀態空間表示,我們記做 $\Sigma$。
其中
\[\Sigma : = \left\{ \begin{array}{l}
\dot x = Ax + Bu\\
y = Cx + Du
\end{array} \right.
\] 則我們有以下定義:
==============
Definition: Realization
令 $H(s)$ 為給定轉移函數,則我們說 其狀態空間 $\Sigma $  為 $H(s)$ 的實現 (Realization) 若下列條件成立:
\[
C(sI-A)^{-1}B + D = H(s)
\]
=============
Comments:
1. 上述 實現(Realization) 意指可以透過 實體電路 (e.g., OP放大器等) "實現" 狀態方程。
2. 設 $\sum = (A,B,C,D) $ 為 $H(s)$ 的實現,現在定義 $T$ 為任意 $n \times n$ 的非奇異矩陣 (non-singular matrix),則我們可以定義下列 新系統 以狀態空間表示:
\[
\tilde {\sum} = (\tilde A, \tilde B, \tilde C, \tilde D)
\]
其中 $\tilde A = TAT^{-1}$, $\tilde B = TB$, $\tilde C = CT^{-1}$, $\tilde D = D$。

那麼現在我們來看看此新系統的轉移函數為何?

\[\begin{array}{l}
\tilde C{(sI - \tilde A)^{ - 1}}\tilde B + \tilde D = C{T^{ - 1}}{(sI - TA{T^{ - 1}})^{ - 1}}TB + D\\
 \ \ \ \ \ \ \ \ = C{T^{ - 1}}{(sT{T^{ - 1}} - TA{T^{ - 1}})^{ - 1}}TB + D\\
  \ \ \ \ \ \ \ \ = C{T^{ - 1}}{\left( {T\left( {sI - A} \right){T^{ - 1}}} \right)^{ - 1}}TB + D\\
 \ \ \ \ \ \ \ \  = C{T^{ - 1}}\left( {T{{\left( {sI - A} \right)}^{ - 1}}{T^{ - 1}}} \right)TB + D\\
  \ \ \ \ \ \ \ \ = C{\left( {sI - A} \right)^{ - 1}}B + D \\
  \ \ \ \ \ \ \ \ = H(s)
\end{array}\]

上述結果告訴我們

1. 狀態空間表示 若透過 非奇異轉換 (Non-singular transformation),其轉移函數不變 (invariant)

2. 上式non-singular transformation 等價於 將系統以新的狀態變數 $z := T x$ 改寫。
由於 $z = Tx \Rightarrow \dot z = T\dot x \Rightarrow \dot x = {T^{ - 1}}\dot z$,故原系統狀態表示可改寫為
\[\begin{array}{l}
\left\{ \begin{array}{l}
\dot x = Ax + Bu\\
y = Cx + Du
\end{array} \right. \Rightarrow \left\{ \begin{array}{l}
{T^{ - 1}}\dot z = A{T^{ - 1}}z + Bu\\
y = C{T^{ - 1}}z + Du
\end{array} \right.\\
 \Rightarrow \left\{ \begin{array}{l}
\dot z = \underbrace {TA{T^{ - 1}}}_{\tilde A}z + \underbrace {TB}_{\tilde B}u\\
y = \underbrace {C{T^{ - 1}}}_{\tilde C}z + \underbrace D_{\tilde D}u
\end{array} \right.
\end{array}\]

有了上述結果之後,我們知道同一系統的 任意狀態空間實現 都可透過 非奇異轉換 求得相同的轉移函數,那麼現在問題變成怎樣的轉移函數才可以被實現??

以下我們給出一個重要且簡潔的定理來回答這個問題:

=======================
Theorem: Realization Theorem
任意 proper (分母階數大於或者等於分子階數) 轉移函數皆為可實現 (realizable)。 
=======================

那麼問題變成已知 proper 轉移函數可以實現 (有狀態空間表示),那麼該如何實現呢? 我們用下面這個例子來說明:

現在考慮 轉移函數
\[
H(s) = \frac{b_m s^m + b_{m-1}s^{m-1} + ... + b_1 s^1 + b_0}{s^n + a_{n-1}s^{n-1} + a_{n-2}s^{n-2} + ... + a_1 s^1 + a_0} + r
\] 其中 $m < n$ (properness)

在不失一般性的情況,我們設 $m = n-1$,則我們由 Realization Theorem 可知 此轉移函數存在 狀態空間表示 (可以實現),故我們可寫成
\[\begin{array}{l}
A = \left[ {\begin{array}{*{20}{c}}
0&1&0&0& \cdots &0\\
0&0&1&0& \cdots &0\\
0&0&0&1&{0 \cdots }&0\\
 \vdots & \vdots &{}&\begin{array}{l}
0\\
 \vdots
\end{array}& \ddots & \vdots \\
0&0& \cdots & \cdots &0&1\\
{ - {a_0}}&{ - {a_1}}&{ - {a_2}}& \cdots &{ - {a_{n - 2}}}&{ - {a_{n - 1}}}
\end{array}} \right],B = \left[ {\begin{array}{*{20}{c}}
0\\
0\\
0\\
 \vdots \\
0\\
1
\end{array}} \right]\\
C = \left[ {\begin{array}{*{20}{c}}
{{b_0}}&{{b_1}}&{{b_2}}& \cdots &{{b_{m - 1}}}&{{b_m}}
\end{array}} \right]\\
D = r
\end{array}\]
上式實現 稱為 可控典型式 (Controllable Canonical form)。

Comments:
1. 為何上述實現被稱為可控典型式?

觀察上式
\[\begin{array}{l}
\dot x = Ax + Bu = A\\
 \Rightarrow \dot x = \left[ {\begin{array}{*{20}{c}}
0&1&0&0& \cdots &0\\
0&0&1&0& \cdots &0\\
0&0&0&1&{0 \cdots }&0\\
 \vdots & \vdots &{}&{\begin{array}{*{20}{l}}
0\\
 \vdots
\end{array}}& \ddots & \vdots \\
0&0& \cdots & \cdots &0&1\\
{ - {a_0}}&{ - {a_1}}&{ - {a_2}}& \cdots &{ - {a_{n - 2}}}&{ - {a_{n - 1}}}
\end{array}} \right]x + B = \left[ {\begin{array}{*{20}{c}}
0\\
0\\
0\\
 \vdots \\
0\\
1
\end{array}} \right]u
\end{array}
\] 現在計算對應的特徵方程式 $\det( sI - A)$,我們可得
\[
\det(sI-A) = s^n + a_{n-1}s^{n-1} + ... + a_0
\] 現在如果我們讓控制力 $ u = Kx$亦即
\[u = \left[ {\begin{array}{*{20}{c}}
{{k_1}}&{{k_2}}& \cdots &{{k_n}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
 \vdots \\
{{x_n}}
\end{array}} \right]
\]則 受控制的動態系統可以改寫為
\[
\dot x = Ax + Bu = Ax + B(Kx ) = (A+BK)x
\]此時
\[\begin{array}{l}
 \Rightarrow A + BK = \left[ {\begin{array}{*{20}{c}}
0&1&0& \cdots &0\\
0&0&1&{0 \cdots }& \vdots \\
0&0&0& \ddots &0\\
 \vdots & \vdots &{}&0&1\\
{ - {a_0}}&{ - {a_1}}& \cdots & \cdots &{ - {a_{n - 1}}}
\end{array}} \right] + \left[ {\begin{array}{*{20}{c}}
0\\
0\\
 \vdots \\
0\\
1
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{k_1}}&{{k_2}}& \cdots &{{k_n}}
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
0&1&0& \cdots &0\\
0&0&1&{0 \cdots }& \vdots \\
0&0&0& \ddots &0\\
 \vdots & \vdots &{}&0&1\\
{{k_1} - {a_0}}&{{k_2} - {a_1}}& \cdots & \cdots &{{k_n} - {a_{n - 1}}}
\end{array}} \right]
\end{array}\]上式可以發對每一個參數 $a_i, \forall i =0, ...,n$ 都有一個對應的控制力參數 $k_j, j=1,...,n$來與之調整,故對應的特徵方程 $\det(sI-(A+BK))$ 的特性根根 (亦即 poles)亦會被 $K$ 直接。此poles 的位置將直接影響到系統性能,故如果某動態系統可寫為可控典型式,則我們可透過上述的控制力 $u=Kx $ 直接改變每一個系統的特性根位置。

2.
在 MATLAB 中 由轉移函數轉成狀態空間實現,可以透過指令 tf2ss.m 來達成。在此不贅述

以下我們看個例子:

Example
考慮轉移函數
\[G(s) = \frac{Y(s)}{U(s)}= \frac{{{b_2}{s^2} + {b_1}{s^1} + {b_0}}}{{a_3^{}{s^3} + {a_2}{s^2} + {a_1}{s^1} + {a_0}}} + r
\]其中 $r$ 為常數。試求出 controllable canonical form:
Solution
注意到我們有額外的常數 $r$ 故可知 $D =r$ (此額外的項,表示輸入可直接影響輸出)

故我們只需專心在 strictly proper 的轉移函數部分即可。另外此例由於階數較低,我們可以用推導的方式求得 controllable canonical form。現在我們觀察轉移函數,並將其繪製成方塊圖

其中我們引入中繼函數 $X(s)$,則透過上圖我們可將轉移函數改寫回微分方程如下
\[\left\{ \begin{array}{l}
\frac{{X(s)}}{{U(s)}} = \frac{1}{{{s^3} + {a_2}{s^2} + {a_1}{s^1} + {a_0}}}\\
\frac{{Y(s)}}{{X(s)}} = {b_2}{s^2} + {b_1}{s^1} + {b_0}
\end{array} \right. \Rightarrow \left\{ \begin{array}{l}
{x^{\left( 3 \right)}} + {a_2}\ddot x + {a_1}\dot x + {a_0}x = u\\
{b_2}\ddot x + {b_1}\dot x + {b_0}x = y
\end{array} \right.\]現在我們定義狀態 $x: = {x_1},\dot x: = {x_2},\ddot x: = {x_3}$ 則上式改寫如下
\[\left\{ \begin{array}{l}
a_3^{}{x^{\left( 3 \right)}} + {a_2}\ddot x + {a_1}\dot x + {a_0}x = u\\
{b_2}\ddot x + {b_1}\dot x + {b_0}x = y
\end{array} \right. \Rightarrow \left\{ \begin{array}{l}
{{\dot x}_3} + {a_2}{x_3} + {a_1}{x_2} + {a_0}{x_1} = u\\
{b_2}{x_3} + {b_1}{x_2} + {b_0}{x_1} = y
\end{array} \right.\]且我們有 ${{\dot x}_1} = {x_2},\;{{\dot x}_2} = {x_3}$ 故我們可寫成
\[\begin{array}{l}
\dot x = Ax + Bu\\
y = Cx + Du
\end{array}\]如下
\[\left\{ \begin{array}{l}
\left[ {\begin{array}{*{20}{c}}
{{{\dot x}_1}}\\
{{{\dot x}_2}}\\
{{{\dot x}_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0&1&0\\
0&0&1\\
{ - {a_0}}&{ - {a_1}}&{ - {a_2}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] + \left[ {\begin{array}{*{20}{c}}
0\\
0\\
1
\end{array}} \right]u\\
y = \left[ {\begin{array}{*{20}{c}}
{{b_0}}&{{b_1}}&{{b_2}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right]
\end{array} \right.\]上式即為 controllable canonical form。

現在合併先前我們的 $D=r$ 故可得最終表示為
\[\left\{ \begin{array}{l}
\left[ {\begin{array}{*{20}{c}}
{{{\dot x}_1}}\\
{{{\dot x}_2}}\\
{{{\dot x}_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0&1&0\\
0&0&1\\
{ - {a_0}}&{ - {a_1}}&{ - {a_2}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] + \left[ {\begin{array}{*{20}{c}}
0\\
0\\
1
\end{array}} \right]u\\
y = \left[ {\begin{array}{*{20}{c}}
{{b_0}}&{{b_1}}&{{b_2}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] + ru \ \ \ \ \ \ \ \square
\end{array} \right.\]

上述可控典型式 與 實現定裡之間關係 我們會留待下一篇文章在做介紹。
[線性系統] Controllability Matrix

另外亦會對非奇異轉換矩陣 $T$ 的求得?? 也就是是否可以找到一個非奇異轉換矩陣 來幫助我們從一個狀態空間的實現 變成 另一個呢?? 做額外補充。

2014年7月6日 星期日

[線性系統] 線性動態系統的表示法: 轉移函數 與 狀態空間表示

這次要介紹線性系統理論中對於動態系統的表示方法:
一般而言,線性動態系統 可以用 線性微分方程(O.D.E.) 來表達,但在控制理論中亦提供兩種不同的方法來表達動態系統:

一種稱為 轉移函數(transfer function) 表示法 (主要工具為 拉式轉換)
一種稱為 狀態空間(state space) 表示法 (主要工具為 矩陣線性代數)

那麼同一種 動態系統間,不同的表示法 可以互相等價轉換,現在我們先看個例子:

Example: Dynamic System to Transfer function
考慮下列動態系統微分方程
\[
\frac{{{d^3}y}}{{d{t^3}}} + 6\frac{{{d^2}y}}{{d{t^2}}} + 5\frac{{dy}}{{dt}} - 4y = u\left( t \right) + 2\frac{{du\left( t \right)}}{{dt}}
\] 那麼我們可以對其取拉式轉換(Laplace Transform) $\mathcal{L}(\cdot)$ 來求取轉移函數,亦即
\[\begin{array}{l}
{{\cal L}}\left\{ {\frac{{{d^3}y}}{{d{t^3}}} + 6\frac{{{d^2}y}}{{d{t^2}}} + 5\frac{{dy}}{{dt}} - 4y} \right\} = {{\cal L}}\left\{ {u\left( t \right) + 2\frac{{du\left( t \right)}}{{dt}}} \right\}\\
 \Rightarrow \left\{ \begin{array}{l}
{s^3}Y\left( s \right) - {s^2}y\left( 0 \right) - s{y^{\left( 1 \right)}}\left( 0 \right) - {y^{\left( 2 \right)}}\left( 0 \right)\\
 + 6\left( {{s^2}Y\left( s \right) - sy\left( 0 \right) - {y^{\left( 1 \right)}}\left( 0 \right)} \right)\\
 + 5\left( {sY\left( s \right) - y\left( 0 \right)} \right) \\
- 4Y\left( s \right)
\end{array} \right\} = \left\{ \begin{array}{l}
U\left( s \right)\\
 + 2\left( {sU\left( s \right) - u\left( 0 \right)} \right)
\end{array} \right\}
\end{array}
\] 上述中 $s$ 表示 微分器;反之 $s^{-1}$ 稱之為積分器。

現在考慮 $y^{(k)} =0, \forall k =0,1,2,...$ 且 $u(0) =0$ 亦即我們考慮整個動態系統的初始狀態為休止 (initially at rest),且亦無初始控制力,則上述拉式轉換式可得
\[\begin{array}{l}
{s^3}Y\left( s \right) + 6{s^2}Y\left( s \right) + 5sY\left( s \right) - 4Y\left( s \right) = U\left( s \right) + 2sU\left( s \right)\\
 \Rightarrow \left( {{s^3} + 6{s^2} + 5s - 4} \right)Y\left( s \right) = \left( {1 + 2s} \right)U\left( s \right)\\
 \Rightarrow \frac{{Y\left( s \right)}}{{U\left( s \right)}} = \frac{{ 2s + 1}}{{{s^3} + 6{s^2} + 5s - 4}}
\end{array}
\] 我們稱上述 $H(s) := \frac{Y(s)}{U(s)}$ 為轉移函數 transfer function。接著除了 轉移函數表示法之外,我們亦可將其用矩陣的方式表示:這邊僅簡單介紹可控典型式(controllable canonical form):
考慮上述轉移函數
\[H\left( s \right) = \frac{{Y\left( s \right)}}{{U\left( s \right)}} = \frac{{1 + 2s}}{{{s^3} + 6{s^2} + 5s - 4}}\]可將其改寫為以下狀態空間模型
\[\left\{ \begin{array}{l}
\dot x = Ax + Bu = \left[ {\begin{array}{*{20}{c}}
0&1&0\\
0&0&1\\
4&{ - 5}&{ - 6}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] + \left[ {\begin{array}{*{20}{c}}
0\\
0\\
1
\end{array}} \right]u\\
y = Cx = \left[ {\begin{array}{*{20}{c}}
1&2&0
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right]
\end{array} \right.\]

Comments:
1. 一般在 MATLAB中,建構轉移函數可以使用 tf(NUM,DEN) 指令,其中 NUM 表示分子係數,DEN表示分母係數:以上例而言,轉移函數透過 MATLAB 建構為

tf( [2 1], [1 6 5 -4])

2. 在MATLAB 中,如果已知轉移函數欲將其轉換到狀態空間模型 (亦即 欲得到 $A,B,C,D$ 矩陣) 有一個非常簡便的指令:[A,B,C,D] = tf2ss(NUM,DEN)



有了上述例子之後我們可以回頭看看 如何從 狀態空間模型 來 求得 轉移函數:

State-Space Method to Transfer Function

現在我們考慮狀態空間模型:
\[\left\{ \begin{array}{l}
\dot x = Ax + Bu\\
y = Cx + Du
\end{array} \right.
\]其中 $x$ 為 $n \times 1$狀態變數向量,$u$ 為 $m \times 1$ 控制力向量,$y$ 為 $r \times 1$ 輸出向量,$A$為 $n \times n$ 矩陣,$B$ 為 $n \times m$ 矩陣, $C$ 為 $r \times n$ 矩陣,$D$ 為 $r \times m $矩陣。

對上式取拉式轉換 $\cal{L}(\cdot)$ 並令初值為零,則可得
\[\left\{ \begin{array}{l}
sX\left( s \right) = AX\left( s \right) + BU\left( s \right)\\
Y\left( s \right) = CX\left( s \right) + DU\left( s \right)
\end{array} \right.
\]現在整理上式可得
\[\begin{array}{l}
\left\{ \begin{array}{l}
\left( {sI - A} \right)X\left( s \right) = BU\left( s \right)\\
Y\left( s \right) = CX\left( s \right) + DU\left( s \right)
\end{array} \right.\\
 \Rightarrow \left\{ \begin{array}{l}
X\left( s \right) = {\left( {sI - A} \right)^{ - 1}}BU\left( s \right)\\
Y\left( s \right) = CX\left( s \right) + DU\left( s \right)
\end{array} \right.\\
 \Rightarrow Y\left( s \right) = C{\left( {sI - A} \right)^{ - 1}}BU\left( s \right) + DU\left( s \right)\\
 \Rightarrow Y\left( s \right) = \left[ {C{{\left( {sI - A} \right)}^{ - 1}}B + D} \right]U\left( s \right)\\
 \Rightarrow \frac{{Y\left( s \right)}}{{U\left( s \right)}} = \underbrace {C{{\left( {sI - A} \right)}^{ - 1}}B + D}_{H\left( s \right)}
\end{array}
\]上述 $H(s)$ 即為轉移函數

且注意到
\[ \Rightarrow \frac{{Y\left( s \right)}}{{U\left( s \right)}} = \underbrace {C{{\left( {sI - A} \right)}^{ - 1}}B + D}_{H\left( s \right)} = C\frac{{adj\left( {sI - A} \right)}}{{\det \left( {sI - A} \right)}}B + D\]故 轉移函數 $H(s)$ 的分母等於 $\det (sI-A)$ 亦即 $\det(sI-A)=0$為系統特徵方程;且 $H(s)$ 的 pole 等於 $A$ 矩陣的 特徵值(eigenvalue)。


Comments:
1. 對線性動態系統而言,狀態空間表示法並非唯一 (故選取的 $A,B,C,D$ 矩陣稱為轉移函數的 實現 realization)。

2. 轉移函數 $H(s)$ 為唯一。亦即轉移函數具備不變性 (invariant).

3. 若 轉移函數 $H(s)$ 分母階數 $\ge$ 分子階數,我們稱此轉移函數為 proper。若 分母階數 $>$ 分子階數,則稱此轉移函數為 strictly proper。若 分母階數 $<$ 分子階數,稱此轉移函數為 improper。同理我們可直接對矩陣形式做判斷
\[ \Rightarrow \frac{{Y\left( s \right)}}{{U\left( s \right)}} = \underbrace {C{{\left( {sI - A} \right)}^{ - 1}}B + D}_{H\left( s \right)}\]若 $D=0$,則 $H(s)$ 為 stirctly proper ;若 $D \neq  0$ 則 $H(s)$ 並非 strictly proper。

對於上述 comments 有興趣的讀者請閱讀
 [線性系統] Realization Theory and Non-singular Transformation




Example 1.: The simplest improper transfer function
\[
H(s) = s
\]亦即,若轉移函數為一 微分器 ,則此時分母為常數 $1$,階數為0階 小於 分子 $s$ 的一階。故為 improper transfer function。

Example 2
考慮系統
\[\left\{ \begin{array}{l}
\dot x = Ax + Bu = \left[ {\begin{array}{*{20}{c}}
{ - 0.1}&1\\
0&{ - 1}
\end{array}} \right]x + \left[ {\begin{array}{*{20}{c}}
1\\
1
\end{array}} \right]u\\
y = Cx = \left[ {\begin{array}{*{20}{c}}
1&0
\end{array}} \right]x
\end{array} \right.
\](a) 試求 系統輸入輸出轉移函數。
(b) 若 $y(t) = 1 - {e^{ - t}}$ 且 $x(0)=0$ 試求對應的 $u(t)$。
Solution
(a):
\[\begin{array}{l}
\frac{{Y\left( s \right)}}{{U\left( s \right)}} = \underbrace {C{{\left( {sI - A} \right)}^{ - 1}}B + D}_{H\left( s \right)}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
1&0
\end{array}} \right]{\left( {\left[ {\begin{array}{*{20}{c}}
s&0\\
0&s
\end{array}} \right] - \left[ {\begin{array}{*{20}{c}}
{ - 0.1}&1\\
0&{ - 1}
\end{array}} \right]} \right)^{ - 1}}\left[ {\begin{array}{*{20}{c}}
1\\
1
\end{array}} \right] + 0\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
1&0
\end{array}} \right]{\left[ {\begin{array}{*{20}{c}}
{s + 0.1}&{ - 1}\\
0&{s + 1}
\end{array}} \right]^{ - 1}}\left[ {\begin{array}{*{20}{c}}
1\\
1
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
1&0
\end{array}} \right]\frac{1}{{\left( {s + 0.1} \right)\left( {s + 1} \right)}}\left[ {\begin{array}{*{20}{c}}
{s + 1}&1\\
0&{s + 0.1}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
1\\
1
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \frac{{s + 2}}{{\left( {s + 0.1} \right)\left( {s + 1} \right)}}
\end{array}\]
(b):由於 $y(t) = 1 - \frac{10}{9} e^{-t} + \frac{1}{9} e^{-10t}$ 對此取拉式轉換可得
\[y(t) = 1 - {e^{ - t}} \Rightarrow Y\left( s \right) = \frac{1}{s} - \frac{1}{{s + 1}}\]故由輸入與輸出關係
\[\begin{array}{l}
H\left( s \right) = \frac{{Y\left( s \right)}}{{U\left( s \right)}} = \frac{{s + 2}}{{\left( {s + 0.1} \right)\left( {s + 1} \right)}} \Rightarrow Y\left( s \right) = \frac{{s + 2}}{{\left( {s + 0.1} \right)\left( {s + 1} \right)}}U\left( s \right)\\
 \Rightarrow \frac{1}{s} - \frac{1}{{s + 1}} = \frac{{s + 2}}{{\left( {s + 0.1} \right)\left( {s + 1} \right)}}U\left( s \right)\\
 \Rightarrow U\left( s \right) = \frac{{\left( {s + 0.1} \right)\left( {s + 1} \right)}}{{s\left( {s + 2} \right)}} - \frac{{s + 0.1}}{{s + 2}}
\end{array}\]再取反拉式轉換即可求得所需結果。

2014年6月9日 星期一

[MATLAB] cdfplot 圖形變色的小技巧

這次要介紹一個 繪製機率常用 的指令:

cdfplot

此指令用來繪製 empirical cumulative probability distribution function, cdf:

用法如下:

cdfplot(X)


其中 X 為產生的隨機變數

下圖即為使用cdfplot所產生的圖形的一個例子:

另外要介紹一個小技巧:
如果想要呈現兩張以上的 cdf 圖形,則使用不同顏色來區別會是一個好方法,但是 cdfplot指令並不支援使用者改變顏色,故我們可以使用 set 指令來幫助我們 (亦可使用 plot tool 來改變顏色):

假設有兩組隨機變數 X, Y, 那麼使用不同顏色的 cdfplot 方法如下:

    cdfplot(X) %繪製藍色線條 X 的cdf

    hold on
 
    Y_color = cdfplot(Y) %繪製紅色線條 Y 的 cdf 並記做 Y_color

    set(Y_color ,  'Color' ,  'red'); %設定顏色

    legend('X', 'Y') %對應資料名稱

    grid on  %開啟網格

那麼執行後圖形如下:(下圖的 X 與 Y 為透過 randn.m 指令產生 1,000 組 隨機變數 繪製而成)

2014年5月22日 星期四

[機率論] Martingale (2)- Martingale Convergence Theorem

假設 $X_n, n\ge 0 $ 為 submartingale。令 $a<b$ 且 $N_0 := -1$ 與 對任意 $k \ge 1$ 我們定義 stopping time 如下:
\[\begin{array}{l}
{N_{2k - 1}}: = \inf \left\{ {m > {N_{2k - 2}}:{X_m} \le a} \right\}\\
{N_{2k}}: = \inf \left\{ {m > {N_{2k - 1}}:{X_m} \ge b} \right\}
\end{array}
\] 且我們觀察以下事件
\[\begin{array}{l}
\{ {N_{2k - 1}} < m \le {N_{2k}}\}  = \{ {N_{2k - 1}} < m\}  \cap \{ m \le {N_{2k}}\} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \underbrace {\{ {N_{2k - 1}} \le m - 1\} }_{ \in {F_{m - 1}}} \cap \underbrace {{{\{ {N_{2k}} \le m - 1\} }^c}}_{ \in {F_{m - 1}}} \in {F_{m - 1}}
\end{array}\]

==============
Fact: 若 $X_m, m\ge 0$ 為 submartingale 則
\[
(b-a)EU_n \le E(X_n -a)^+ - E(X_0 - a)^+
\]其中 ${U_n}: = \sup \left\{ {k:{N_{2k}} \le n} \right\}$ 表示在 時間$n$ 之前 往上穿越的個數
==============
Proof: omitted.

==========
Theorem: Martingale Convergence Theorem
若 $X_n$ 為 submartingale 滿足 $\sup E[X_n^+] < \infty$ 則存在 $X$ 使得 $X_n \to X$ almost surely 且 $E|X| < \infty$
===========

Proof: 先證存在 $X$ 使得 $X_n \to X$ almost surely
首先考慮 $(X-a)$ 正的部分記做 $(X-a)^+$ 且注意到 $(X -a)^+ \le X^+ + |a|$。

由於  $X_n$ 為 submartingale 故由前述的 FACT 可知
\[\begin{array}{l}
(b - a)E{U_n} \le E{({X_n} - a)^ + } - E{({X_0} - a)^ + } \le E{({X_n} - a)^ + } \le EX_n^ +  + |a|\\
 \Rightarrow E{U_n} \le \frac{{EX_n^ +  + |a|}}{{b - a}}
\end{array}\]由於 $U_n \to U \; \text{as $n \to \infty$}$ (整個 $U_n$ 往上穿越過 $[a,b]$ 範圍的個數)

由假設 $\sup_n EX_n^+ < \infty$,故上式可推知 $EU < \infty$ 且 $U< \infty $ almost surely。亦即 表示在 時間 $\infty$ 之前 往上穿越 $[a,b]$ 的個數為有限次( $\Rightarrow$ 必定收斂!)

注意到上述結果對任意有理數 $a,b \in \mathbb{Q}$ 皆成立,故
\[P\left( {\bigcup\limits_{a,b \in Q}^{} {\left\{ {\lim \inf {X_n} < a < b < \lim \sup {X_n}} \right\}} } \right) = 0
\]故 $\lim\sup X_n = \lim\inf X_n$ almost surely。因此 $\lim X_n$ 存在 almost surely。

接著證明  $E|X| < \infty$
利用 Fatou Lemma 可得 $EX^+ \le \lim \inf EX_n^+ <\infty$ 故 $X<\infty $ almost surely。接著我們證明 $X > -\infty$,觀察下式
\[
EX_n^- = EX_n^+ - EX_n \le EX_n^+ - EX_0
\]利用 $X_n$ 為 submartingale ($E({X_n}|{{\cal F}_0}) \ge {X_0} \Rightarrow \underbrace {E[E[{X_n}|{{\cal F}_0}]]}_{E{X_n}} \ge E{X_0}$ )。
故再度使用 Fatou Lemma 可知
\[
EX^- \le \liminf_{n \to \infty} EX_n^- \le \sup_n EX_n^+ - EX_0 < \infty
\]

以下我們看個 上述定理所衍生的重要結果:

==============
Theorem 2: 若 $X_n \ge 0$ 為 supermartingale,則 存在 $X$ 使得 $X_n \to X$ almost surely 且 $EX \le EX_0$
==============
Proof: 先證 存在 $X$ 使得 $X_n \to X$ almost surely:

令 $Y_n := - X_n$ 則 $Y_n $為 submartingale 且 $Y_n \le 0$。

利用  Martingale Convergence Theorem :如果我們可以證明 $Y_n$ 為 submartingale 滿足 $EY_n^+ < \infty$ 則存在 $Y$ 使得 $Y_n \to Y$ almost surely

由於 $Y_n \le 0 \Rightarrow Y_n^+ =0$ 故 $EY_n^+ <\infty$。由 Martingale Convergence Theorem 可知 存在 $Y$ 使得 $Y_n \to Y$ almost surely ;亦即存在 $X$ 使得 $X_n \to X$ almost surely。


接著我們證明 $EX \le EX_0$
由於 $X_n \ge 0$ ,利用 Fatuou Lemma 可知
\[EX \le \mathop {\lim \inf }\limits_{n \to \infty } E{X_n}
\]且 $E\left[ {E\left[ {X|{F_0}} \right]} \right] = E\left[ X \right]$ 故可推知
\[\begin{array}{l}
EX \le \mathop {\lim \inf }\limits_{n \to \infty } E{X_n}\\
 \Rightarrow \underbrace {E\left[ {E\left[ {X|{F_0}} \right]} \right]}_{ = EX} \le \mathop {\lim \inf }\limits_{n \to \infty } E\left[ {E\left[ {{X_{n + 1}}|{F_0}} \right]} \right] \le E{X_0}
\end{array}\]

前面兩個 Theorem 的假設並不保證 $L^1$ 收斂。以下我們看個例子:
==================
Example: 
令 $S_n$ 為 symmetric simple random walk 且 $S_0 = 1$,亦即
\[{S_n}: = \sum\limits_{m = 1}^n {{\xi _m}}  = {S_{n - 1}} + {\xi _n}\]其中 $\xi_1,\xi_2,...$ 為 i.i.d. 且 $P(\xi_i =1) = P(\xi_i = -1) =1/2$,現在令 stopping time $N:= \inf \{n:S_n=0\}$ 且定義  $X_n:=S_{N \wedge n}$。試回答下列問題
(0): 試判斷 $S_n$ 是否為 martingale。)
(1): 試判斷 $X_n:=S_{N \wedge n}$ 是否為 martingale?
(2): $X_n$ 是否存在對應的 極限隨機過程 $X$  使得 $X_n \to X$ almost surely?
(3): $E[X_n] =?$
(4): 試證 $X_n \to X$ 並無 $L^1$-convergence
==================
Solution:
對於 (0):留給讀者證明 ( symmetric simple random walk $S_n$ 為 martingale。)

對於 (1):由於 stopping time $N:= \inf \{n:S_n=0\}$ 且  $X_n:=S_{N \wedge n}$ 故我們可推論以下兩件事實:
1. 停止後的隨機過程 $X_n$ 仍為 martingale。(留給讀者證明或者參閱:[機率論] Martingale (3) - Example  )
2. 由於停止時間定義為 $N:= \inf \{n:S_n=0\}$,故 停止後的隨機過程 $X_n \ge 0$

對於 (2):
故我們利用 Theorem 2 可知 存在 $X$ 使得 $X_n \to X$ almost surely 且 $EX_n \le EX_0 = 1$。
另外注意到收斂的隨機過程 $X \equiv 0$ (因為若不為 $0$,則 $X_{n+1} = k \pm 1$ 會震盪!! (no convergence))

對於 (3):利用 $X_n$ 為 Martingale 性質
\[E{X_n} = E\underbrace {{S_{n \wedge N}}}_{martingale} = E{S_0} = 1\]

對於 (4):由 $L^1$ convergence 定義可知條件為 $E\left| {{X_n} - X} \right| \to 0$ 且注意到
\[E\left| {{X_n} - X} \right| \to 0 \Rightarrow E{X_n} \to EX\]由前述題目可知, $EX_n = 1$ 但 $EX =0$ 故 $EX_n \nrightarrow EX$ 故 $E|X_n- X| \nrightarrow 0$ 亦即 NO $L^1$-convergence


2014年5月21日 星期三

[機率論] 淺論 Martingale (1) - 何時能 贏 or 輸掉賭局?

(NOTE: 此文為數學機率論相關文章,並無任何介紹任何賭博手法/訣竅...)

回憶前篇文章 [機率論] 淺論 Martingale (0) - 定義與性質 提及的

考慮一個硬派賭徒參加一場丟擲硬幣賭錢的遊戲,且若硬幣正面向上,則賭徒會贏得下注金並且停止遊戲 (take money and run),反之,若硬幣反面向上,則賭徒輸掉下注金但此時因為賭徒並不甘心..所以會將 賭注加倍 再繼續玩。持續 $n$ 次這樣的遊戲。那麼這位賭徒宣稱靠這套 "必勝法" 最後可以贏得一筆大錢 (至少不賠本);因為只要過程中贏得一場就可以獲得相對的加倍下注金!!

此套賭徒所宣稱的 必勝法在數學上稱做 Martingale System;我們將會在此篇文章檢驗此 Martingale 加倍賭注策略,看看之前賭徒宣稱的必勝法是否有效。

不過介紹之前需要再引入一些術語:

===========
Definition: Predictable Sequence
令 $\mathcal{F}_n, n \ge 0$ 為 Filtration , 我們稱 $H_n, n\ge 1$ 為 Predictable sequence 若下列條件成立: 若 $H_n \in \mathcal{F}_{n-1}, \; \forall n \ge 1$ (亦即 $H_n$ 為 $\mathcal{F}_{n-1}$ measurable)
===========

現在我們再次考慮 投擲銅板的賭博:若銅板正面則賭徒贏得 1元,若顯示為銅板背面則賭徒輸掉 1元。令 $X_n$ 為在 $n$ 次時賭徒的 淨收入/損失。則我們可以定義 在第 $n$ 次賭博時賭徒 "總" 贏/輸錢的量
\[{\left( {H \cdot X} \right)_n}: = \sum\limits_{m = 1}^n {{H_m}\left( {{X_m} - {X_{m - 1}}} \right)}  = \sum\limits_{m = 1}^n {{H_m}{\xi _m}}
\]其中 $\xi_n := X_n - X_{n-1}$ 表示第 $n$ 次賭博到底是贏 或者 輸 的單次金額; $H_n$ 則表示成 第 $n$ 次賭博 時候 賭徒所下注的賭金量。

Comment:
上式 $(H \cdot X)_n$ 可看為離散時間的 Ito integral。


現在我們看個例子:

Example: Martingale Strategy
考慮 $H_1 = 1$ 且 對 $n \ge 2,$ 我們使用 " 如果輸錢就加倍賭注" 的策略;亦即我們定義 $H_n$ 為 \[{H_n} = \left\{ {\begin{array}{*{20}{l}}
{2{H_{n - 1}}\begin{array}{*{20}{c}}
{}&{}
\end{array}if\begin{array}{*{20}{c}}
{}
\end{array}{\xi _{n - 1}} =  - 1}\\
{1\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array}if\begin{array}{*{20}{c}}
{}
\end{array}{\xi _{n - 1}} = 1}
\end{array}} \right.\]現在考慮若 輸 $k$ 次 之後才贏錢,試計算 $(H \cdot X)_n=?$ (此時 $n=k+1$)

Solution:
由於我們的策略是輸錢就加倍賭注:
故賭輸第一次的時候賠掉 $1$元;亦即  $(H \cdot X)_1 = -1$ 元;故下次賭注金會加倍 變成 $2$元繼續賭下一次

賭輸第二次的時候,單單這次賭徒賠掉的賭金為 $-2$ 元;故如果我們計算總輸錢量為 $(H \cdot X)_2 = -1 -2 = -3$;接著加倍賭注金 (變成 $2^2 = 4$ 元)繼續賭下一次

賭輸第三次的時候,單單這次賠掉賭金為 $-2^2$ 元;故此時 $(H \cdot X)_3 = -1 -2 -2^2 = -7$;接著加倍賭注金 (變成 $2^3 = 8$ 元)繼續賭下一次


依此類推,賭輸到第 $k$ 次 單單這次會賠掉賭金為 $-2^{k-1}$元。此時的 $(H \cdot X)_k = -1-2-...-2^{k-1}$ 接著加倍賭注金 (變成 $2^{k} $ 元)繼續賭下一次


但最後一次 $(k+1)$次 我們贏了,故最後的賭金總輸贏量為
\[{(H \cdot X)_{k + 1}} =  - 1 - 2 - ... - {2^{k - 1}} + {2^k} =  - \underbrace {\left( {1 + 2 + ... + {2^{k - 1}}} \right)}_{ = \left( {\frac{{1 \cdot \left( {{2^k} - 1} \right)}}{{2 - 1}}} \right) = \left( {{2^k} - 1} \right)} + {2^k} = 1\]
也就是說最後我們至少贏回了最初投資的 $1$ 元! $\square$

Comment:
此例子也告訴我們 "似乎" $P(\xi_m=1) > 0 $ (贏錢的機率為正值!! Really??)。但是下面的定理告訴我們:如果賭徒參與的賭局為 supermartingale,則"沒有" 任何策略可以贏錢。


==============
Theorem 1: 令 $X_n, n \ge 0$ 為 supermartingale,若 $H_n \ge 0$ 為 predictable 且對任意 $n,$ $H_n$ 有界,則 $(H \cdot X)_n$ 為 supermartingale。
==============

Proof:
要證  $(H \cdot X)_n$ 為 supermartingale;亦即
\[E\left[ {{{(H \cdot X)}_{n + 1}}|{F_n}} \right] \le {(H \cdot X)_n}
\]故我們需檢驗其滿足supmartingale三個條件:首先關於可積條件,由於 $X_n$ 為 supermartingale 且 $(H \cdot X)_n$ 為有限項 summation 故可積條件滿足;接著檢驗可測條件:注意到 $H_n$ 為 predictable (亦即 $H_n$ 為 $\mathcal{F}_{n-1}$ -measurable) ,故可推知
\[{(H \cdot X)_n} = \sum\limits_{m = 1}^n {{H_m}\left( {{X_m} - {X_{m - 1}}} \right)}  \in {F_n}\]
最後檢驗 supmartingale property:觀察
\[\begin{array}{l}
E\left[ {{{(H \cdot X)}_{n + 1}}|{F_n}} \right] = E\left[ {\sum\limits_{m = 1}^{n + 1} {{H_m}\left( {{X_m} - {X_{m - 1}}} \right)} |{F_n}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \sum\limits_{m = 1}^n {{H_m}\left( {{X_m} - {X_{m - 1}}} \right)}  + {H_{n + 1}}E\left[ {\left( {{X_{n + 1}} - {X_n}} \right)|{F_n}} \right]
\end{array}\]已知 $E\left[ {{X_{n + 1}}|{F_n}} \right] \le {X_n} \Rightarrow E\left[ {{X_{n + 1}} - {X_n}|{F_n}} \right] \le 0$ 故
\[\begin{array}{l}
E\left[ {{{(H \cdot X)}_{n + 1}}|{F_n}} \right] = \underbrace {\sum\limits_{m = 1}^n {{H_m}\left( {{X_m} - {X_{m - 1}}} \right)} }_{ = {{(H \cdot X)}_n}} + \underbrace {{H_{n + 1}}}_{ \ge 0}\underbrace {E\left[ {\left( {{X_{n + 1}} - {X_n}} \right)|{F_n}} \right]}_{ \le 0}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \le {(H \cdot X)_n}. \ \ \ \ \ \ \square
\end{array}\]

上述定理告訴我們 如果賭局呈現 supermartingale 則 沒有任何必勝法可以從中贏錢。但我們的硬派賭徒認為:如果可以考慮在賭局當中任何時間停手,那麼至少應該有 "止損" 的作用吧? 也就是說透過額外考慮 "停止" 的機制是否可以幫助我們對抗 supermartingale呢? 在回答這個問題之前我們必須先回答數學上該如何針對 "何時停止" 進行嚴格描述:

======================
Definition: Stopping Time
我們說 隨機變數 $N$ 為 停止時間 (Stopping Time) 若下列條件成立:
對任意 $N < \infty$,$\{N=n\} \in \mathcal{F}_n$ (亦即 $N$ 為 $\mathcal{F}_n$-measurable)。
======================

Comment:
我們可以已將停止時間 $N$ 視為 賭徒何時抽手不玩的時間,那麼上述條件可以視為:在時間$n$ 賭徒認為是時候該停手不玩的決定 必定是基於當時賭局所能獲得的資訊 $(\mathcal{F}_n)$ 而定


那麼現在我們可以回答原本賭徒提出的問題,也就是假設 $X_n$ 為 supermartingale 則停止機制之後的隨機過程 $X_{N \wedge n}$ 是否仍為 supermartingale (因為如果是,則上述 Theorem 1 告訴我們儘管加入停止時間,仍然沒有任何必勝法能夠獲勝。)

此問題的答案記做以下定理:
======================
Theorem 2: 若 $N$ 為 Stopping time 且 $X_n$ 為 supermartingale 則停止後的隨機過程 $X_{n \wedge N}$ 亦為 supermartingale。
======================

Proof:
我們要證明停止後的隨機過程 $X_{n \wedge N}$ 亦為 supermartingale。現在取 $H_n:= 1_{ \{N \ge n \} }$ 則觀察事件 $\{N \ge n\} = \{ N \le n-1 \}^c \in \mathcal{F}_{n-1}$ 故 $H_n$ 為 predictable。

接著觀察
\[\begin{array}{l}
{\left( {H \cdot X} \right)_n} = \sum\limits_{m = 1}^n {{H_m}\left( {{X_m} - {X_{m - 1}}} \right)} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \sum\limits_{m = 1}^n {{1_{\left\{ {N \ge m} \right\}}}\left( {{X_m} - {X_{m - 1}}} \right)} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = {1_{\left\{ {N \ge 1} \right\}}}\left( {{X_1} - {X_0}} \right) + {1_{\left\{ {N \ge 2} \right\}}}\left( {{X_2} - {X_1}} \right) + ...  + {1_{\left\{ {N \ge n} \right\}}}\left( {{X_n} - {X_{n - 1}}} \right)
\end{array}\]注意到由於 $X_n$ 為 supermartingale 且  $H_n$ 為 predictable,由 Theorem 1 可知 $(H \cdot X)_n$ 為 supermartingale,故
\[\begin{array}{l}
{\left( {H \cdot X} \right)_n} = {X_{n \wedge N}} - {X_0}\\
 \Rightarrow {X_{n \wedge N}} = \underbrace {{{\left( {H \cdot X} \right)}_n}}_{{\rm{supermartingale}}} + \underbrace {{X_0}}_{{\rm{constant}}}
\end{array}\]上式右方: supermartingale $(H \cdot X)_n$ 加上常數隨機過程 $X_0$ 仍為 supermartingale,亦即 ${X_{n \wedge N}}$ 為 supermartingale。 $\square$

Comment:
若 $X_n$ 為 martingale 則 $X_{n \wedge N}$ 亦為 martingale。有興趣的讀者可參閱
[機率論] Martingale (3) - Example

Ref: Durrett, Probability Theory and Examples, Cambridge





2014年5月20日 星期二

[機率論] 淺論 Martingale (0) - 定義與性質

關於 Martingale Theory (中文譯作 鞅論),原本 Martingale 指的是套在馬身上的韁繩
https://commons.wikimedia.org/wiki/File:Martingale_(PSF).png


在機率論中,Martingale 泛指一類特定的隨機過程。起初的想法如下:

考慮一個硬派賭徒參加一場丟擲硬幣賭錢的遊戲:若硬幣正面向上,則賭徒會贏得下注金並且停止遊戲 (take money and run),反之,若硬幣反面向上,則賭徒輸掉下注金。

但此時因為賭徒並不甘心..所以他採取的策略是把 賭注加倍 再繼續玩。持續 $n$ 次這樣的遊戲。那麼這位賭徒宣稱靠這套 "必勝法" 最後可以 贏得一筆大錢 or 至少不輸;因為只要過程中贏得一場就可以獲得相對的加倍下注金!! (但此法真的可行嗎? 我們會在後續在做介紹)


現在我們引入嚴格定義:

=================
Definition: Filtration Adaptedness
令 $\mathcal{F}_n$ 為 filtration (亦即 $\sigma$-algebra $\mathcal{F}_n \subset \mathcal{F}_{n+1}, \; \forall n$) 則我們說 $X_n$ 為 adapted to $\mathcal{F}_n$ 若 $X_n $ 為 $\mathcal{F}_n$-measurable。

我們說一個 random sequence $\{X_n\}$ 為 Martingale with respect to $\{\mathcal{F}_n\}$若下列條件成立:
1. 可積條件:$E|X_n| < \infty$
2. 可測條件:$X_n$ 為 adapted to $\mathcal{F}_n$ ($\forall n$, $X_n $ 為 $\mathcal{F}_n$-measurable)
3. Martingale 性質:對任意 $n$,$E[X_{n+1}|\mathcal{F}_n] = X_n$
=================

Comment:
若上述定義中的 Martingale 性質 的 $=$ 號 換成 $\le$ 則我們稱 $\{X_n\}$ 為 supermartingale 反之,若 $=$ 號 換成 $\ge$ 則我們稱 $\{X_n\}$ 為 submartingale 


以下我們看個例子:

Example: Coin Tossing Game
考慮連續投擲一枚公平硬幣的遊戲:定義隨機變數 $\xi_n$ 表示為第 $n$-th 投擲銅板且
\[{\xi _n}: = \left\{ \begin{array}{l}
 + 1,\begin{array}{*{20}{c}}
{}&{}
\end{array}head\\
 - 1,\begin{array}{*{20}{c}}
{}&{}
\end{array}tail
\end{array} \right.;\begin{array}{*{20}{c}}
{}&{}
\end{array}P\left( {{\xi _n} = 1} \right) = P\left( {{\xi _n} =  - 1} \right) = 1/2\]注意到此遊戲中,每次投擲硬幣出現的結果之間彼此獨立!。

接著我們定義新的隨機變數 $X_n:= \xi_1 + ... + \xi_n$, 且 sigma-algebra $\mathcal{F}_n:=\sigma(\xi_1,...,\xi_n)$ 對任意 $n \ge 1$。且 $X_0 :=0$ 其對應的 sigma-algebra $\mathcal{F}_0:=\{\emptyset, \Omega\}$。
現在我們宣稱此 $X_n$ (賭徒在第 $n$次賭博後所贏的錢) 為 martingale。

Proof:
現在檢驗此隨機變數 $X_n$ 是否為 martingale ? 亦即需要檢驗 $X_n$ 是否滿足 Martingale 的三個條件,首先檢驗
可積條件: \[\begin{array}{*{20}{l}}
{E|{X_n}| = E|{\xi _1} + ... + {\xi _n}|}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le E|{\xi _1}| + ... + E|{\xi _n}|}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = n\left[ {1P\left( {{\xi _n} = 1} \right) + \left| { - 1} \right|P\left( {{\xi _n} =  - 1} \right)} \right] < \infty }
\end{array}\]接著檢驗 可測條件:由於$\mathcal{F}_n:=\sigma(\xi_1,...,\xi_n)$ 對任意 $n \ge 1$,故可知 $X_n$ 確實為 $\mathcal{F}_n$-measurable。

最後檢驗 Martingale property:固定任意 $n \ge 1$,觀察
\[\begin{array}{l}
E[{X_{n + 1}}|{{{\cal F}}_n}] = E[\left( {{\xi _1} + ... + {\xi _n} + {\xi _{n + 1}}} \right)|{{{\cal F}}_n}]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \left( {{\xi _1} + ... + {\xi _n}} \right) + E[{\xi _{n + 1}}|{{{\cal F}}_n}]\begin{array}{*{20}{c}}
{}&{}
\end{array}\left( {{\xi _{n + 1}}\begin{array}{*{20}{c}}
{}
\end{array}independent\begin{array}{*{20}{c}}
{}
\end{array}of{{{\cal F}}_n}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = {X_n} + E[{\xi _{n + 1}}]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = {X_n} + \left[ {1P\left( {{\xi _{n + 1}} = 1} \right) + \left( { - 1} \right)P\left( {{\xi _{n + 1}} =  - 1} \right)} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = {X_n} + \left[ {1 \cdot \frac{1}{2} + \left( { - 1} \right)\frac{1}{2}} \right] = {X_n}
\end{array}\]由於三個條件都滿足,故可知 $X_n$確實為 martingale。 $\square$

Comment: 
如果上述例子換成 $P(\xi_n =1) \le 1/2$ (e.g., 莊家把硬幣動一點手腳?) 則  Martingale property 會得到
\[
E[X_{n+1}| \mathcal{F}_n] \le X_n
\]亦即,$X_n$ 為 supermartingale。


現在看幾個簡單的結果:

=================
FACT 1: 假設 $X_n$ 為 martingale w.r.t. $\mathcal{G}_n$ 且令 $\mathcal{F}_n:= \sigma(X_1,...,X_n)$,則 $\mathcal{G}_n \supset \mathcal{F}_n$ 且 $X_n$ 為 martingale w.r.t. $\mathcal{F}_n$。
=================

Proof:
首先檢驗 $\mathcal{G}_n \supset \mathcal{F}_n$ ,由於  $\mathcal{F}_n:= \sigma(X_1,...,X_n)$ 為 smallest sigma-algebra generated by $X_1,...,X_n$ 故  $\mathcal{G}_n \supset \mathcal{F}_n$ 。

接者我們證明  $X_n$ 為 martingale w.r.t. $\mathcal{F}_n$:由於已知  $X_n$ 為 martingale w.r.t. $\mathcal{G}_n$ 只需檢驗 Martingale Property 即可;亦即要證
\[E\left[ {{X_{n + 1}}|{\mathcal{F}_n}} \right] = E{X_n}
\]故現在觀察
\[\begin{array}{l}
\left\{ \begin{array}{l}
E\left[ {E\left[ {{X_{n + 1}}|{\mathcal{G}_n}} \right]|{F_n}} \right] = E\left[ {{X_{n + 1}}|{F_n}} \right]\begin{array}{*{20}{c}}
{}&{}
\end{array}\left( {tower\begin{array}{*{20}{c}}
{}
\end{array}property} \right)\\
E\left[ {{X_{n + 1}}|{\mathcal{G}_n}} \right] = {X_n}
\end{array} \right.\\
 \Rightarrow E\left[ {{X_n}|{\mathcal{F}_n}} \right] = E\left[ {{X_{n + 1}}|{\mathcal{F}_n}} \right]\\
 \Rightarrow {X_n} = E\left[ {{X_{n + 1}}|{\mathcal{F}_n}} \right]\begin{array}{*{20}{c}}
{}&{}
\end{array}\left( {{X_n} \in {\mathcal{F}_n}} \right)
\end{array}\]上述 $X_n \in \mathcal{F}_n$ 表示 $X_n$ 為 $\mathcal{F}_n$ measurable。

由前述推導可知 $X_n$ 為 martingale w.r.t. $\mathcal{F}_n$。$\square$

===============
Fact 2: 若 $X_n$ 為 supermartingale,則 對任意 $n > m$,$n,m \in \mathbb{N}$ 我們有 $E[X_n| \mathcal{F}_m] \le X_m$。
===============

Proof:
給定  $n > m$, 要證  $E[X_n| \mathcal{F}_m] \le X_m$。

首先觀察如果 $n := m+1$ 則
\[E[{X_n}|{{{\cal F}}_m}] = E[{X_{m + 1}}|{{{\cal F}}_m}] \ \ \ \ (*)
\]又因為 $X_n$ 為 supermartingale 故對任意 $n$,我們有 $E[{X_{n + 1}}|{{{\cal F}}_n}] \le {X_n}$ 亦即
\[E[{X_n}|{{{\cal F}}_m}] = E[{X_{m + 1}}|{{{\cal F}}_m}] \le {X_m}
\]故 $n=m+1$ 時候 $E[X_n| \mathcal{F}_m] \le X_m$。


現在令 $n:=m +k$,$k \ge 2$ 觀察
\[\begin{array}{l}
E[{X_{m + k}}|{{{\cal F}}_m}] = E[E\left[ {{X_{m + k}}|{{{\cal F}}_{m + k - 1}}} \right]|{{{\cal F}}_m}]\begin{array}{*{20}{c}}
{}&{}
\end{array}\left( {tower\begin{array}{*{20}{c}}
{}
\end{array}peroperty} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} \le E[{X_{m + k - 1}}|{{{\cal F}}_m}]\begin{array}{*{20}{c}}
{}&{}
\end{array}\left( {by\begin{array}{*{20}{c}}
{}
\end{array}assumption\begin{array}{*{20}{c}}
{}
\end{array}E[{X_{n + 1}}|{{{\cal F}}_n}] \le {X_n}} \right)
\end{array}\]接著利用 induction 可證得 $E[X_n| \mathcal{F}_m] \le X_m$。$\square$


上述結果對 submartingale 與 martingale 亦成立:



=================
FACT 3: 
(a) 若 $X_n$ 為 submartingale,則 對任意 $n > m$,$n,m \in \mathbb{N}$ 我們有 $E[X_n| \mathcal{F}_m] \ge X_m$。
(b) 若 $X_n$ 為 martingale,則 對任意 $n > m$,$n,m \in \mathbb{N}$ 我們有 $E[X_n| \mathcal{F}_m] =X_m$。
=================
Proof: omitted。(幾乎與 FACT 2 證明一致)


 =================
Corollary for FACT 3:
 假設 $X_n$ 為 martingale w.r.t. $\mathcal{F}_n$ 則
\[
E[X_n] = E[X_m]= E[X_0], \;\; \forall n>m
\]=================
Proof: 令 $n>m$ 且  $X_n$ 為 martingale,由 FACT3 可知  $E[X_n| \mathcal{F}_m] =X_m$,故兩邊再次同取期望值,利用條件期望值定義可得
\[\begin{array}{l}
E[{X_n}|{F_m}] = E[{X_m}]\\
 \Rightarrow \underbrace {E\left[ {E[{X_n}|{F_m}]} \right]}_{ = E{X_n}} = \underbrace {E\left[ {E[{X_m}]} \right]}_{ = E{X_m}} \ \ \ \ \square
\end{array}\]



 =================
FACT 4: 若 $X_n$ 為 martingale w.r.t. $\mathcal{F}_n$ 且函數 $\varphi$ 為 convex 滿足 對任意 $n$ 而言,$E|\varphi(X_n)| < \infty$,則 $\varphi(X_n)$ 為 submartingale w.r.t. $\mathcal{F}_n$。
 =================
Proof: 要證  $\varphi(X_n)$ 為 submartingale w.r.t. $\mathcal{F}_n$。亦即要證
\[E\left[ {\varphi \left( {{X_{n + 1}}} \right)|{\mathcal{F}_n}} \right] \ge \varphi \left( {{X_n}} \right) \]
由於函數 $\varphi$ 為 convex 滿足且對任意 $n$ 而言,$E|\varphi(X_n)| < \infty$ 故我們利用(Conditional) Jensen inequality 可知
\[\varphi (\underbrace {E\left[ {{X_{n + 1}}|{\mathcal{F}_n}} \right]}_{ = {X_n}}) \le E\left[ {\varphi \left( {{X_{n + 1}}} \right)|{\mathcal{F}_n}} \right]\]注意到上式左方利用了假設 $\varphi(X_n)$ 為 submartingale w.r.t. $\mathcal{F}_n$,亦即 $E[X_{n+1} | \mathcal{F}_n] = X_n$ 故我們有 \[\varphi ({X_n}) \le E\left[ {\varphi \left( {{X_{n + 1}}} \right)|{{{\cal F}}_n}} \right]\]即為所求。$\square$

=================
Corollary for FACT4: 考慮 $X_n$ 為 martingale w.r.t. $\mathcal{F}_n$ ,若 $p \ge 1$ 且 $E|X_n|^p <\infty, \; \forall n$ 則 $|X_n|^p$ 為 submartingale w.r.t. $\mathcal{F}_n$
=================

Proof: 觀察 $|x|^p$ 為 convex function,故利用 FACT4 得證


現在我們想問 FACT 4 反向是否成立? 如果不,那麼加甚麼條件可以使其成立?
=================
FACT 5: 若 $X_n$ 為 submartingale w.r.t. $\mathcal{F}_n$ 且 $\varphi$ 為 increasing convex 函數 且滿足 $E|\varphi(X_n)| <\infty\; \forall n$ 則 $\varphi(X_n)$ 為 submartingale w.r.t. $\mathcal{F}_n$
=================

Proof:
要證明 $\varphi(X_n)$ 為 submartingale w.r.t. $\mathcal{F}_n$ ;亦即
\[E\left[ {\varphi \left( {{X_{n + 1}}} \right)|{F_n}} \right] \ge \varphi ({X_n})\]
首先注意到 $\varphi$ 為 increasing 故可知 $x \le y \Rightarrow \varphi(x) \le \varphi(y)$,現在觀察
\[\underbrace {\varphi \left( {{X_n}} \right) \le \varphi \left( {E\left[ {{X_{n + 1}}|{F_n}} \right]} \right)}_{{\rm{by}}\begin{array}{*{20}{c}}
{}
\end{array}{X_n} \le E\left[ {{X_{n + 1}}|{F_n}} \right]\begin{array}{*{20}{c}}
{}
\end{array}\& \begin{array}{*{20}{c}}
{}
\end{array}\varphi \begin{array}{*{20}{c}}
{}
\end{array}{\rm{is}}\begin{array}{*{20}{c}}
{}
\end{array}{\rm{increasing}}} \le E\left[ {\varphi \left( {{X_{n + 1}}} \right)|{F_n}} \right]\]

Corollary for FACT5
1. 若 $X_n$ 為 submartingale 且 $a$ 為任意常數,則 $(X_n - a)^+$ 亦為 submartingale。 (其中 $(x)^+$ 表示 只取 $x$ 正的部分)
2. 若 $X_n$ 為 supermartingale,則 $X_n  \wedge a$ 亦為 supermartingale。

Proof 1. 令 $\varphi(x):= (x-a)^+ $只需驗證 $\varphi$ 為 convex 即可(why?) 因為一旦 $\varphi$為 convex 則直接應用 FACT5 即可得證)。故我們現在檢驗 convexity:給定 $x,y$ 與 $\lambda \in [0,1]$ 觀察
\[\begin{array}{l}
\phi \left( {\lambda x + \left( {1 - \lambda } \right)y} \right) = {\left( {\lambda x + \left( {1 - \lambda } \right)y - a + \lambda a - \lambda a} \right)^ + }\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} = {\left( {\lambda \left( {x - a} \right) + \left( {1 - \lambda } \right)\left( {y - a} \right)} \right)^ + }\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} \le \lambda {\left( {x - a} \right)^ + } + \left( {1 - \lambda } \right){\left( {y - a} \right)^ + }
\end{array}\]故為 convex function。


Proof 2: 由於  $X_n$ 為 supermartingale,故 $-X_n$ 為 submartingale,且 $\min\{x,a\} = -\max\{x,a\}$。令 $\varphi(x) := \max\{x,a\}$ ;由於 maximum function 為 convex function,故可直接使用 FACT 5 證得所需的部分。

延伸閱讀
[機率論] 淺論 Martingale (1) - 何時能 贏 or 輸掉賭局?


Ref: Durrett, Probability Theory and Examples, Cambridge

2014年4月24日 星期四

[隨機分析] Black-Scholes PDE for European Call option (1)

延續上篇 [隨機分析] Black-Scholes PDE for European Call option (0),這次要來證明 Black-Scholes Formula
\[
{\scriptsize f(t,S_t) = S \Phi \left( \frac{\ln(S_t/K) + (r+\frac{1}{2} \sigma^2) (T-t) }{\sigma \sqrt{T-t}}\right) - K e^{-r (T-t)} \Phi \left( \frac{\ln(S_t/K) + (r - \frac{1}{2}\sigma^2) (T-t) }{\sigma \sqrt{T-t}}\right)}
\]其中 $\Phi (\cdot)$ 為 Standard Normal Cumulative distribution function (CDF)

現在令 $x= S_t$,上述的 Black-Scholes Formula 確實為 Black-Scholes PDE 的解,亦即上式為下列PDE的解:
\[
rf(t,x) = {f_t}(t,x) + rx{f_x}(t,x) + \frac{1}{2}{f_{xx}}(t,x){\sigma ^2}{x^2}
\]且滿足終端邊界條件 $f(T,x) = h(x), \ \forall x \in \mathbb{R}$


我們將分成下列幾個小步驟逐步完成此證明:


步驟1:首先證明下列等式成立:

Claim 1: $K e^{-r(T-t)} \Phi ' (d_2(T-t,x)) = x \Phi' (d_1(T-t,x))$
其中
\[
d_1 (T-t, x) =  \frac{\ln(x/K) + (r+\frac{1}{2} \sigma^2) (T-t) }{\sigma \sqrt{T-t}} \\
d_2 (T-t,x) =  \frac{\ln(x/K) + (r - \frac{1}{2}\sigma^2) (T-t) }{\sigma \sqrt{T-t}} \\
\]
Proof
我們證明
\[
K e^{-r(T-t)} \Phi ' (d_2(T-t,x))- x \Phi' (d_1(T-t,x))=0
\]由於 $\Phi (\cdot)$ 為 Standard Normal Cumulative distribution function (CDF) ,故 $\Phi '(\cdot)$ 即為 Standard Normal density,亦即
 \[\left\{ \begin{array}{l}
\Phi'\left( {{d_1}\left( {T - t,x} \right)} \right) = \frac{1}{{\sqrt {2\pi } }}{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}\\
\Phi'\left( {{d_2}\left( {T - t,x} \right)} \right) = \frac{1}{{\sqrt {2\pi } }}{e^{ - \frac{{{d_2}{{\left( {T - t,x} \right)}^2}}}{2}}}
\end{array} \right.
\]現在觀察 $d_2(T-t,x) = d_1(T-t,x) - \sigma \sqrt{T-t}$,故直接計算
\[\begin{array}{l}
K{e^{ - r(T - t)}}\Phi '({d_2}(T - t,x)) - x\Phi '({d_1}(T - t,x))\\
 = K{e^{ - r(T - t)}}\frac{1}{{\sqrt {2\pi } }}{e^{ - \frac{{{d_2}{{\left( {T - t,x} \right)}^2}}}{2}}} - x\frac{1}{{\sqrt {2\pi } }}{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}\\
 = \frac{1}{{\sqrt {2\pi } }}\left[ {K{e^{ - r(T - t)}}{e^{ - \frac{{{d_2}{{\left( {T - t,x} \right)}^2}}}{2}}} - x{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}} \right]\\
 = \frac{1}{{\sqrt {2\pi } }}\left[ {K{e^{ - r(T - t)}}{e^{ - \frac{{{{\left[ {{d_1}\left( {T - t,x} \right) - \sigma \sqrt {T - t} } \right]}^2}}}{2}}} - x{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}} \right]\\
 = \frac{1}{{\sqrt {2\pi } }}\left[ {K{e^{ - r(T - t)}}{e^{ - \frac{{{d_1}^2\left( {T - t,x} \right) - 2{d_1}\left( {T - t,x} \right)\sigma \sqrt {T - t}  + {\sigma ^2}\left( {T - t} \right)}}{2}}} - x{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}} \right]\\
 = \frac{1}{{\sqrt {2\pi } }}{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}\left[ {K{e^{ - r(T - t)}}{e^{\frac{{2{d_1}\left( {T - t,x} \right)\sigma \sqrt {T - t} }}{2}}}{e^{\frac{{ - {\sigma ^2}\left( {T - t} \right)}}{2}}} - x} \right]\\
 = \frac{1}{{\sqrt {2\pi } }}{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}\left[ {K{e^{ - r(T - t)}}{e^{\frac{{\ln (x/K) + (r + \frac{1}{2}{\sigma ^2})\left( {T - t} \right)}}{{\sigma \sqrt {T - t} }}\sigma \sqrt {T - t} }}{e^{\frac{{ - {\sigma ^2}\left( {T - t} \right)}}{2}}} - x} \right]\\
 = \frac{1}{{\sqrt {2\pi } }}{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}\left[ {K{e^{ - r(T - t)}}\left( {\frac{x}{K}} \right){e^{(r + \frac{1}{2}{\sigma ^2})\left( {T - t} \right)}}{e^{\frac{{ - {\sigma ^2}\left( {T - t} \right)}}{2}}} - x} \right]\\
 = \frac{1}{{\sqrt {2\pi } }}{e^{ - \frac{{{d_1}{{\left( {T - t,x} \right)}^2}}}{2}}}\left[ {{e^{ - r(T - t)}}x{e^{r\left( {T - t} \right)}} - x} \right] = 0. \ \ \ \ \square
\end{array}
\]

步驟2:證明下列Claim:
Claim 2: (Theta of the Option)
\[
{f_t}\left( {t,x} \right) =  - rK{e^{ - r(T - t)}}\Phi ({d_2}(T - t,x)) - \frac{{\sigma x}}{{2 \sqrt {T - t} }}\Phi '({d_1}(T - t,x))
\]
Proof
直接計算 $f(t,x)$ 的對 $t$ 偏導數
\[\begin{array}{l}
{f_t}(t,x) = \frac{\partial }{{\partial t}}f\left( {t,x} \right) = \frac{\partial }{{\partial t}}\left[ {x\Phi \left( {{d_1}(T - t,x)} \right) - K{e^{ - rT}}{e^{rt}}\Phi \left( {{d_2}(T - t,x)} \right)} \right]\\
 \Rightarrow {f_t}(t,x) = x\frac{{\partial \Phi }}{{\partial t}}\left( {{d_1}(T - t,x)} \right) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - K{e^{ - r(T)}}\left[ {r{e^{r(t)}}\Phi \left( {{d_2}(T - t,x)} \right) + {e^{r(t)}}\frac{{\partial \Phi }}{{\partial t}}\left( {{d_2}(T - t,x)} \right)} \right]\\
 \Rightarrow {f_t}(t,x) =  - rK{e^{ - r(T - t)}}\Phi \left( {{d_2}(T - t,x)} \right) + x\frac{{\partial \Phi \left( {{d_1}(T - t,x)} \right)}}{{\partial t}} \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - K{e^{ - r(T - t)}}\frac{{\partial \Phi \left( {{d_2}(T - t,x)} \right)}}{{\partial t}} \ \ \ \ (*)
\end{array}
\]由 Standard Normal CDF $\Phi(\cdot)$ 定義,我們可以分別計算:
\[\begin{array}{l}
\frac{{\partial \Phi \left( {{d_1}(T - t,x)} \right)}}{{\partial t}} = \frac{\partial }{{\partial t}}\left\{ {\frac{1}{{\sqrt {2\pi } }}\int_{ - \infty }^{{d_1}(T - t,x)} {{e^{\frac{{ - {z^2}}}{2}}}} dz} \right\} \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  = \frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_1}(T - t,x)} \right)}^2}}}{2}}}\frac{\partial }{{\partial t}}{d_1}(T - t,x)} \right]\\
\frac{{\partial \Phi \left( {{d_2}(T - t,x)} \right)}}{{\partial t}} = \frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}\frac{\partial }{{\partial t}}{d_2}(T - t,x)} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}\frac{\partial }{{\partial t}}\left[ {{d_1}(T - t,x) - \sigma \sqrt {T - t} } \right]} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{\sqrt {2\pi } }}{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}\left[ {\frac{{\partial {d_1}(T - t,x)}}{{\partial t}} + \frac{\sigma }{{2\sqrt {T - t} }}} \right]
\end{array}
\]將上面計算出來的兩項偏導數式子帶回 $(*)$,並利用 Claim 1 的結果整理可得
\[
 \Rightarrow {f_t}(t,x) =  - rK{e^{ - r(T - t)}}\Phi \left( {{d_2}(T - t,x)} \right) \\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - \frac{\sigma }{{2\sqrt {T - t} }}K{e^{ - r(T - t)}}\frac{1}{{\sqrt {2\pi } }}{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}\\
\]利用 $d_1(T-t,x) = d_2(T-t,x) - \sigma \sqrt{T-t}$,帶入上式
\[\begin{array}{l}
 \Rightarrow {f_t}(t,x) =  - rK{e^{ - r(T - t)}}\Phi \left( {{d_2}(T - t,x)} \right) \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - \frac{\sigma }{{2\sqrt {T - t} }}K{e^{ - r(T - t)}}\frac{1}{{\sqrt {2\pi } }}{e^{\frac{{ - {{\left( {{d_1}(T - t,x) - \sigma \sqrt {T - t} } \right)}^2}}}{2}}}\\
 \Rightarrow {f_t}(t,x) =  - rK{e^{ - r(T - t)}}\Phi \left( {{d_2}(T - t,x)} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} - \frac{\sigma }{{2\sqrt {T - t} }}K{e^{ - r(T - t)}}\frac{1}{{\sqrt {2\pi } }}{e^{\frac{{ - {d_1}^2(T - t,x)}}{2}}}{e^{\frac{{2\sigma {d_1}(T - t,x)\sqrt {T - t} }}{2}}}{e^{\frac{{ - {\sigma ^2}\left( {T - t} \right)}}{2}}}\\
 \Rightarrow {f_t}(t,x) =  - rK{e^{ - r(T - t)}}\Phi \left( {{d_2}(T - t,x)} \right) - \frac{{\sigma x}}{{2\sqrt {T - t} }}\Phi '\left( {{d_1}(T - t,x)} \right)
\end{array}
\] $\square$

步驟3:證明下列Claim:
Claim 3: (Delta of the Option)
\[
{f_x}\left( {t,x} \right) =  \Phi ({d_1}(T - t,x))
\]
Proof
想法同Claim 2,直接計算對 $x$ 偏導數
\[\begin{array}{l}
{f_x}\left( {t,x} \right) = \frac{\partial }{{\partial x}}f(t,x) = \frac{\partial }{{\partial x}}\left[ {x\Phi \left( {{d_1}(T - t,x)} \right) - K{e^{ - r(T - t)}}\Phi \left( {{d_2}(T - t,x)} \right)} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \Phi \left( {{d_1}(T - t,x)} \right) + x\frac{\partial }{{\partial x}}\Phi \left( {{d_1}(T - t,x)} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} - K{e^{ - r(T - t)}}\frac{\partial }{{\partial x}}\Phi \left( {{d_2}(T - t,x)} \right) \ \ \ \ (**)
\end{array}
\]分別計算
\[\begin{array}{l}
\frac{{\partial \Phi \left( {{d_1}(T - t,x)} \right)}}{{\partial x}} = \frac{\partial }{{\partial x}}\left\{ {\frac{1}{{\sqrt {2\pi } }}\int_{ - \infty }^{{d_1}(T - t,x)} {{e^{\frac{{ - {z^2}}}{2}}}} dz} \right\}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_1}(T - t,x)} \right)}^2}}}{2}}}\frac{\partial }{{\partial x}}{d_1}(T - t,x)} \right]\\
\frac{{\partial \Phi \left( {{d_2}(T - t,x)} \right)}}{{\partial x}} = \frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}\frac{\partial }{{\partial x}}{d_2}(T - t,x)} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}\frac{\partial }{{\partial x}}\left[ {{d_1}(T - t,x) - \sigma \sqrt {T - t} } \right]} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{\sqrt {2\pi } }}{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}\left[ {\frac{{\partial {d_1}(T - t,x)}}{{\partial x}}} \right]
\end{array}
\]帶回偏導式 $(**)$ 可得
\[\begin{array}{l}
{f_x}\left( {t,x} \right) = \Phi \left( {{d_1}(T - t,x)} \right) + \frac{1}{{\sqrt {2\pi } }}\left[ {x{e^{\frac{{ - {{\left( {{d_1}(T - t,x)} \right)}^2}}}{2}}}\frac{\partial }{{\partial x}}{d_1}(T - t,x)} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} - K{e^{ - r(T - t)}}\frac{1}{{\sqrt {2\pi } }}{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}\left[ {\frac{{\partial {d_1}(T - t,x)}}{{\partial x}}} \right]\\
 \Rightarrow {f_x}\left( {t,x} \right) = \Phi \left( {{d_1}(T - t,x)} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} + \frac{1}{{\sqrt {2\pi } }}\left\{ {x{e^{\frac{{ - {{\left( {{d_1}(T - t,x)} \right)}^2}}}{2}}} - K{e^{ - r(T - t)}}{e^{\frac{{ - {{\left( {{d_2}(T - t,x)} \right)}^2}}}{2}}}} \right\}\left[ {\frac{{\partial {d_1}(T - t,x)}}{{\partial x}}} \right]
\end{array}
\]利用Claim 1的結果,我們可知
\[{f_x}\left( {t,x} \right) = \Phi \left( {{d_1}(T - t,x)} \right) \ \ \ \ \square
\]。

現在,由上述 Claim 2 的結果: ${f_x}\left( {t,x} \right) = \Phi \left( {{d_1}(T - t,x)} \right)$ 我們可立刻求得 $f_x(t,x)$ 對 $x$ 的二階偏導數 (Gamma of the Option):
\[{f_{xx}}\left( {t,x} \right) = \frac{{\partial \Phi \left( {{d_1}(T - t,x)} \right)}}{{\partial x}} = \frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_1}(T - t,x)} \right)}^2}}}{2}}}\frac{\partial }{{\partial x}}{d_1}(T - t,x)} \right]
\]由於
\[\frac{\partial }{{\partial x}}\left[ {\frac{{\ln (x/K) + (r + \frac{1}{2}{\sigma ^2})(T - t)}}{{\sigma \sqrt {T - t} }}} \right] = \frac{1}{{\sigma \sqrt {T - t} }}\frac{1}{x}
\]故
\[{f_{xx}}\left( {t,x} \right) = \frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_1}(T - t,x)} \right)}^2}}}{2}}}\frac{1}{{\sigma x\sqrt {T - t} }}} \right]\]

步驟4:證明下列 Claim:
Claim 4: Black-Scholes Formula satisfies Black-Scholes PDE

Proof
回憶 Black-Scholes PDE:
\[
rf(t,x) = {f_t}(t,x) + rx{f_x}(t,x) + \frac{1}{2}{f_{xx}}(t,x){\sigma ^2}{x^2}
\]現在將 Claim 2, 3 計算出來的結果 $f_t(t,x), f_x(t,x)$ 與 二階偏導數 $f_{xx}(t,x)$ 帶入PDE中
\[
rf(t,x) = {f_t}(t,x) + rx{f_x}(t,x) + \frac{1}{2}{f_{xx}}(t,x){\sigma ^2}{x^2}
\],我們得到
\[\begin{array}{l}
 \Rightarrow rf(t,x) =  - rK{e^{ - r(T - t)}}\Phi ({d_2}(T - t,x)) - \frac{{\sigma x}}{{2\sqrt {T - t} }}\Phi '({d_1}(T - t,x))\\
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + rx\Phi \left( {{d_1}(T - t,x)} \right) + \frac{1}{2}\frac{1}{{\sqrt {2\pi } }}\left[ {{e^{\frac{{ - {{\left( {{d_1}(T - t,x)} \right)}^2}}}{2}}}\frac{1}{{\sigma x\sqrt {T - t} }}} \right]{\sigma ^2}{x^2}\\
 \Rightarrow f(t,x) = x\Phi \left( {{d_1}(T - t,x)} \right) - K{e^{ - r(T - t)}}\Phi ({d_2}(T - t,x))
\end{array}
\]$ \square$


步驟5:證明符合 Terminal condition:
Claim 5: $f(T,x) = h(x)$

Proof
考慮 $x>K$,我們得到
\[
\mathop {\lim }\limits_{t \to T} {d_1}\left( {T - t,x} \right) =  + \infty  \Rightarrow \mathop {\lim }\limits_{t \to T} {d_2}\left( {T - t,x} \right) =  + \infty
\]故
\[ \Rightarrow f(T,x) = S - K \ \ \ \ (1)
\]

考慮 $0<x<K$,
\[\mathop {\lim }\limits_{t \to T} {d_1}\left( {T - t,x} \right) =  - \infty  \Rightarrow \mathop {\lim }\limits_{t \to T} {d_2}\left( {T - t,x} \right) =  - \infty
\]故
\[ \Rightarrow f(T,x) = 0 \ \ \ \ (2)
\] 合併 $(1) + (2)$ 得到Terminal condition:
\[
f(T,x) = (x - K)_+ = h(x)
\]