[數學分析] Power Series and Analytic Functions

================================
Definition: Power Series & Analytic Series 
一個  具有下列形式的 Series 稱為 Power Series：對任意 $x \in \mathbb{R}$，
\[
f(x) = \sum_{n=0}^\infty c_n x^n
\]或者更廣義的來說：
\[
f(x) = \sum_{n=0}^\infty c_n (x-a)^n
\]若函數 $f$ 具有 power series 我們稱為 解析函數 Analytic function。
================================

Comments:
1. 解析函數為 "無窮" series 此暗示了一旦 解析函數被定義即表此 series 收斂。

2. 一般而言對於 power series 我們有兩種方法判斷 series 是否收斂
(a) 採用 Ratio Test ：但此法僅能判斷 series 是否 pointwise convergence。此法如下：
考慮 $f(x) = \sum_{n=0}^\infty c_n (x-a)^n$ ；則 Ratio Test 要判斷 第 $n$ 項 與 第 $n+1$項 之比值是否小於1。如果小於1我們說此 series converges pointwise。亦即 Ratio Test 檢驗下式是否成立：
\[\mathop {\lim }\limits_{n \to \infty } \left| {\frac{{{c_{n + 1}}{{(x - a)}^{n + 1}}}}{{{c_n}{{(x - a)}^n}}}} \right| < 1?
\]關於 Ratio Test 可參考下例：

Example: 
試利用 Ratio Test 判斷 $\sum\limits_{n = 1}^\infty  {\frac{n}{{{2^n}}}} $ 是否收斂?

Solution
令 $c_n =  {\frac{n}{{{2^n}}}}$ 則我們僅需檢驗
\[\mathop {\lim }\limits_{n \to \infty } \left| {\frac{{{c_{n + 1}}}}{{{c_n}}}} \right| < 1?\] 故觀察\[\mathop {\lim }\limits_{n \to \infty } \left| {\frac{{{c_{n + 1}}}}{{{c_n}}}} \right| = \mathop {\lim }\limits_{n \to \infty } \left| {\frac{{\frac{{n + 1}}{{{2^{n + 1}}}}}}{{\frac{n}{{{2^n}}}}}} \right| = \mathop {\lim }\limits_{n \to \infty } \left| {\frac{{n + 1}}{{2n}}} \right| = \frac{1}{2} < 1\]故 收斂。

(b) 採用 Weierstrass M-test: 此法可以判斷 series 是否 uniformly convergence。
關於 M-test：
令 $\{f_n\}$ 為定義在集合 $E$ 上的 函數 sequence 使得 對任意 $t \in E$， $|f_n(t)| \le M_n$；若 $\sum_n^\infty M_n < \infty$ 則 $\sum_n^\infty f_n(x)$ converges uniformly。

詳細關於 Weierstrass M-test 證明與性質請讀者參閱 ： [數學分析] 逐點收斂與均勻收斂(2) - Series version

3. 若 $f(x) = \sum_{n=0}^\infty c_n (x)^n$ 在 $|x| < R$ 收斂( $R$ 可以是 $\infty$)； 則我們說 $f$ 可以用 power series 在 $x=0$點"展開" (此種展開的 power series 稱為 Maclaurin series )
若 $f(x) = \sum_{n=0}^\infty c_n (x-a)^n$ 在 $|x-a|<R$ 收斂；則我們說 $f$ 可以用 power series 在 $x=a$ 點"展開" (此種展開的 power series 稱為 Taylor Series)


============
Theorem 
假設  $f(x) := \sum_{n=0}^\infty c_n (x-a)^n$ 對 $|x-a|<R$ 皆收斂 的 Analytic function，則
1. 對任意 $\varepsilon >0$， $f(x)$ 在區間 $[a-R+\varepsilon, a+R-\varepsilon]$ 上均勻收斂。且
2. $f$ 可微 並 滿足下式
\[
f'(x) = \sum_{n=1}^\infty n c_n x^{n-1}
\]============

Comment: $R$ 又稱為收斂半徑。

 Proof: 只證 1.
要證  $f(x) := \sum_n c_n x^n$  均勻收斂，我們可使用 Weierstrass M-test: 給定 $\varepsilon >0$，觀察
\[\left| {{c_n}{x^n}} \right| \le \left| {{c_n}{{\left( {R - \varepsilon } \right)}^n}} \right|
\]故現在只需證明 $\sum\limits_n {\left| {{c_n}{{\left( {R - \varepsilon } \right)}^n}} \right|} $ 收斂。即可保證均勻收斂。

注意到 對 $|x|<R$， $f(x) = \sum_{n=0}^\infty c_n x^n$ 收斂 故可推知
\[\sum\limits_n {\left| {{c_n}{{\left( {R - \varepsilon } \right)}^n}} \right|} \]亦為收斂。由 M-test 可知 $f(x) := \sum_n c_n x^n$ 在區間 $[-R+\varepsilon, R-\varepsilon]$ 上均勻收斂

==============================
Corollary: Analytic Function is Smooth
假設  $f(x) := \sum_{n=0}^\infty c_n (x-a)^n$ 對 $|x-a|<R$ 皆收斂，則 $f(x)$為 smooth。亦即 對 $|x| < R$，$f(x)$ 具有任意階導數
==============================

Comment:
給定解析函數 $f(x) := \sum_{n=0}^\infty c_n (x-a)^n$，則 $f^{n}(a) = n! c_n$，也就是說我們可以求得係數
\[{c_n} = \frac{{{f^n}(a)}}{{n!}}
\]但注意到若我們把上述係數收集起來建構一個 Series，此 Series 並不一定收斂到原函數 $f$。也就是說一個 具有係數為 $\frac{f^{(n)}(a)}{n!}$ 的 power series 並不一定為解析函數!


我們用以下一些例子來說明如何求 Power Series 的收斂半徑
Example 1
考慮 $f(x) = \sum_{k=0}^\infty \frac{x^k}{k!}$ (NOTE: $f(x) = e^x$ )試求 收斂半徑 $R=?$

Solution
注意到此例為 Power Series，我們可採用 Ratio Test 檢驗此級數是否收斂，亦即檢驗
\[\mathop {\lim }\limits_{k \to \infty } \left| {\frac{{\frac{{{x^{k + 1}}}}{{\left( {k + 1} \right)!}}}}{{\frac{{{x^k}}}{{k!}}}}} \right| = \mathop {\lim }\limits_{k \to \infty } \left| {\frac{{{x^1}}}{{k + 1}}} \right| = \left| x \right|\mathop {\lim }\limits_{k \to \infty } \left| {\frac{1}{{k + 1}}} \right|\]若 $|x| < \infty$ 則上述極限趨近於 $0$ 滿足 Ratio Test 條件，故級數收斂。故收斂半徑 $R = \infty$ 即可。 $\square$

Example 2
令 $a>0$，考慮 $f(x) = \sum_{k=0}^\infty \frac{x^k}{a^k}$ 試求 收斂半徑 $R=?$

Solution

由 Ratio Test，觀察

\[\mathop {\lim }\limits_{k \to \infty } \left| {\frac{{\frac{{{x^{k + 1}}}}{{{a^{k + 1}}}}}}{{\frac{{{x^k}}}{{{a^k}}}}}} \right| = \mathop {\lim }\limits_{k \to \infty } \left| {\frac{{{x^1}}}{a}} \right| = \left| {\frac{x}{a}} \right|\]若 

\[\left| {\frac{x}{a}} \right| < 1\]則 級數收斂，亦即 $\left| x \right| < a$，故取收斂半徑 $R:= a$ 即可。 $\square$

[數學分析] 淺談有限維度空間的 Linear Transformation

這邊介紹 $\mathbb{R}^n$ 空間的 線性轉換 (Linear Transformation)；

但我們首先從無窮維任意向量空間開始定義：

======================
令 $X,Y$ 為任意 向量空間 (Vector Space)：
Definition: Linear Transformation
我們稱 映射 $A : X \to Y$ 為 線性轉換 (Linear Transformation) 若下列條件成立：對任意 ${\bf{x}},{\bf{y}} \in X$ 與 純量 $c \in \mathbb{R}$，
\[\begin{array}{l}
A\left( {{\bf{x}} + {\bf{y}}} \right) = A{\bf{x}} + A{\bf{y}}\\
A\left( {c{\bf{x}}} \right) = cA{\bf{x}}
\end{array}\]======================

Comment:

1. 注意到上述符號： $A ({\bf x}) $ 表示 $A$ 作用在 ${\bf x}$ 上!!  並非乘法! 一般而言，若 $A$ 為 linear ，$A({\bf x}) $ 會記為 $A \bf x$ (讀者須避免與乘法造成誤會!)

2. 考慮 Linear transformation $A: X \to Y$ ，若 $\left\{ {{{\bf{x}}_1},{{\bf{x}}_2},...,{{\bf{x}}_n}} \right\}$ 為 $X$ 空間的 基底 (basis)，則任意向量 ${\bf x} \in X$ 有唯一表示：
\[{\bf{x}} = \sum\limits_{i = 1}^n {{c_i}{{\bf{x}}_i}} \]且由 Linearity of $A$ 可知
\[A{\bf{x}} = A\left( {\sum\limits_{i = 1}^n {{c_i}{{\bf{x}}_i}} } \right) = \sum\limits_{i = 1}^n {{c_i}A{{\bf{x}}_i}} \]

======================
Definition: Linear Operator
Linear Transformation  $A : X \to X$ 稱為 線性算子 (Linear Operator) 。
======================

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

Definition: Invertible Linear Operator
Linear Operator $A : X \to X$ 為 invertible 若下列條件成立：
1. $A$ 為 one-to-one；亦即 對任意 ${{\bf{x}}_1},{{\bf{x}}_2} \in X$, ${{\bf{x}}_1} \ne {{\bf{x}}_2} \Rightarrow A{{\bf{x}}_1} \ne A{{\bf{x}}_2}$
2. $A$ 為 onto；亦即 對任意 ${\bf y} \in X$ 存在 ${\bf x} \in X$ 使得 $A {\bf x} = {\bf x}$

若 Linear Operator $A$ 為 invertible 則其 inverse 我們記做 $A^{-1}$ on $X$ 且滿足
對任意 ${\bf x} \in X$，\[
A^{-1}A({\bf x}) = {\bf x}
\]======================

現在我們看幾個結果：
======================
Theorem 1: 考慮 Linear Operator $A: X \to X$ 且 $X$ 為 有限維度的 vector space。則 $A$ 為 one-to-one 若且為若 $A$ is onto。
======================

Proof: omitted

Comments/Notations:
1. 一般而言，我們定義 $L(X,Y)$ 為一個集合，其中的元素為所有由 $X$ 映射到 $Y$ 的 Linear transformation 所組成。

2. $L(X) := L(X,X)$

3. Addition and Scalar multiplication of Linear Operators
若 $A_1, A_2 \in L(X,Y)$ 且 $c_1, c_2 \in \mathbb{R}$，則對任意 ${\bf x} \in X$，我們可以定義
\[({c_1}{A_1} + {c_2}{A_2}){\bf{x}}: = {c_1} \cdot \underbrace {{A_1}{\bf{x}}}_{ \in L\left( {X,Y} \right)} + {c_2} \cdot \underbrace {{A_2}{\bf{x}}}_{ \in L\left( {X,Y} \right)}\]故 $({c_1}{A_1} + {c_2}{A_2}){\bf{x}} \in L\left( {X,Y} \right)$

4. Composition of Linear Operators:
若 $X,Y,Z$ 為 Vector Spaces 且若 $A \in L(X,Y)$ 與 $B \in L(Y,Z)$ 則我們可以定義 composition of $A$ and $B$ : 對任意 ${\bf x} \in X$
\[
(B \circ A){\bf x} = B(A{\bf x})
\]且 $B \circ A \in L(X,Z)$

5. Operator Norms
考慮 $A \in L(\mathbb{R}^n, \mathbb{R}^m)$ 則我們定義 Operator norm $||A||_L$ 如下：對任意 ${\bf x} \in X$，
\[
||A||_L:=\sup_{||x|| =1} ||A {\bf x}||
\]
且上述 Operator norm 滿足 $||A {\bf x}|| \le ||A||_L ||{\bf x}||$ 對任意 ${\bf x} \in X$。(在不失一般性之下，我們通常將 operator norm $||A||_L$ 直接記做 $||A||$。)
---


現在我們看以下幾個關於 operator norm 的衍生結果：
=================
FACT 1: 若 $A \in L(\mathbb{R}^n, \mathbb{R}^m)$ 則 $||A|| < \infty$ 且 $A$ 為 uniformly continuous mapping。
=================

Proof:
令 $A \in L(\mathbb{R}^n, \mathbb{R}^m)$，我們首先證明  $||A|| < \infty$ ；由定義可知
\[||A|| = ||A|{|_L}: = \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||A{\bf{x}}|| \ \ \ \ (*)
\]現在令 $\left\{ {{{\bf{e}}_1},...,{{\bf{e}}_n}} \right\}$ 為 $\mathbb{R}^n$ 空間的 standard basis，則可知任意 ${\bf x}$ 可用上述的 standard basis 做唯一表示，故我們現在取 ${\bf x}$ 滿足 $||{\bf x}|| =1$ ；亦即我們可寫
\[{\bf{x}}: = \sum\limits_{i = 1}^n {{c_i}{{\bf{e}}_i}}
\]且 $|c_i| \le 1\; \forall i=1,...,n$ 故 $(*)$ 變成
\[\begin{array}{*{20}{l}}
{||A|| = \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||A{\bf{x}}|| = \mathop { }||A\sum\limits_{i = 1}^n {{c_i}{{\bf{e}}_i}} ||}\\
{\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = ||\sum\limits_{i = 1}^n {{c_i}A{{\bf{e}}_i}} || \le \sum\limits_{i = 1}^n {\left\| {A{{\bf{e}}_i}} \right\|}  < \infty }
\end{array}\]
接著我們證明 $A$ 為 uniformly continuous，給定 $\varepsilon>0$ 我們要證明 存在 $\delta>0$ 使得 對任意 ${\bf u,v} \in \mathbb{R}^n$ ，
\[||{\bf{u}} - {\bf{v}}|| < \delta  \Rightarrow ||A{\bf{u}} - A{\bf{v}}|| < \varepsilon \]
如果我們選 $\delta < \varepsilon/||A||$ 則我們有
\[||A{\bf{u}} - A{\bf{v}}|| = ||A\left( {{\bf{u}} - {\bf{v}}} \right)|| \le \underbrace {||A||}_{ < \infty } \cdot \underbrace {||{\bf{u}} - {\bf{v}}||}_{ < \frac{\varepsilon }{{||A||}}} < \varepsilon \]若 $||{\bf{u}} - {\bf{v}}|| < \delta $ 成立。亦即 $A$ 為 uniformly continuous。$\square$



==================
FACT 2: 若 $A,B \in L(\mathbb{R}^n, \mathbb{R}^m)$ 且 $c$ 為 純量，則 operator norm 滿足
\[
||A+B|| \le ||A|| + ||B||;\;\;\; ||c A|| = |c| ||A||
\] =================
Proof:
首先證明 operator norm 滿足 三角不等式 $||A+B|| \le ||A|| + ||B||$；對任意 ${\bf x} \in \mathbb{R}^n$，觀察
\[\begin{array}{l}
||A + B|| = \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||\left( {A + B} \right){\bf{x}}|| = \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||A{\bf{x}} + B{\bf{x}}||\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||A{\bf{x}}|| + \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||B{\bf{x}}||\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le ||A|| + ||B||
\end{array}\]
接著我們證明 $ ||c A|| = |c|\cdot ||A||$；對任意 ${\bf x} \in \mathbb{R}^n$，觀察
\[\left| {\left| {c \cdot A} \right|} \right| = \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||cA{\bf{x}}|| = \left| c \right|\mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||A{\bf{x}}|| = \left| c \right|\left| {\left| A \right|} \right| \ \ \ \ \square
\]

==================
FACT 3: 考慮 $A \in L(\mathbb{R}^n, \mathbb{R}^m)$ 且 $B \in L(\mathbb{R}^m, \mathbb{R}^k)$，則
\[
||B \circ A|| \le ||B|| ||A||
\] =================
Proof: 
\[\begin{array}{l}
|B \circ A|| = \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||B\left( {A{\bf{x}}} \right)|| \le \mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||B||||A{\bf{x}}||\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = ||B|| \cdot \underbrace {\mathop {\sup }\limits_{||{\bf{x}}|| = 1} ||A{\bf{x}}||}_{ = ||A||} = ||B|| \cdot ||A||
\end{array} \ \ \ \ \square
\]


==================
FACT 4:  $L(\mathbb{R}^n, \mathbb{R}^m)$ 配備 norm $||A-B||$為 metric space。其中 $A,B \in L(\mathbb{R}^n, \mathbb{R}^m)$
 =================
Proof: omitted.


由於 FACT 4 ，我們知道 $L(\mathbb{R}^n, \mathbb{R}^m)$ 為 metric space，故 topological 架構 (e.g., open, close, compactness,...)可以再其上被討論。

======================
Theorem 2: 令 $\Omega:=L(\mathbb{R}^n)$ 為 invertible linear operators 的集合，則
(a) 若 $A \in \Omega, B \in L(\mathbb{R}^n)$ 且 $||B-A|| \cdot ||A^{-1}|| <1$ 則 $B \in \Omega$
(b) $\Omega \subset L(\mathbb{R}^n)$ 為 open 且 映射 $A \to A^{-1}$ 為 continuous on $\Omega$
======================

Proof:
要證 $B \in \Omega$，亦即 $B$ 為 invertible linear operators。 (由前述 Theorem 1 我們只需證 $B$ 為 one-to-one 即可。) 現在令 $||A^{-1}|| := 1/\alpha$ 且 $||B-A|| := \beta$ 則 由 假設可知 $||B-A|| \cdot ||A^{-1}|| <1 \Rightarrow \beta < \alpha$。

現在觀察：對任意 ${\bf x} \in \mathbb{R}^n$ 我們有
\[\alpha |{\bf{x}}| = \alpha |{A^{ - 1}}A{\bf{x}}| \le \alpha \left\| {{A^{ - 1}}} \right\||A{\bf{x}}| = |A{\bf{x}}|
\]且
\[\begin{array}{l}
|A{\bf{x}}| = |A{\bf{x}} - B{\bf{x}} + B{\bf{x}}|\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le |\left( {A - B} \right){\bf{x}}| + |B{\bf{x}}|\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le \left\| {A - B} \right\||{\bf{x}}| + |B{\bf{x}}|\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \beta |{\bf{x}}| + |B{\bf{x}}|
\end{array}\]將上述結果合併可推得
\[\begin{array}{l}
\left\{ \begin{array}{l}
\alpha |{\bf{x}}| \le |A{\bf{x}}|\\
|A{\bf{x}}| \le \beta |{\bf{x}}| + |B{\bf{x}}|
\end{array} \right.\\
 \Rightarrow \alpha |{\bf{x}}| \le \beta |{\bf{x}}| + |B{\bf{x}}|\\
 \Rightarrow \left( {\alpha  - \beta } \right)|{\bf{x}}| \le |B{\bf{x}}| \ \ \ \ \ (*)
\end{array}
\]注意到由於 $\beta < \alpha$ 故可知若 ${\bf x} \neq 0$ 則 $B{\bf{x}} \ne 0$ 故 $B$ 為 one-to-one。且因為 $\mathbb{R}^n$ 為 finite-dimensional vector space，由 前述 Theorem 可知 $B \in \Omega$

接著我們證明 $(b)$

首先證明 $\Omega$ 為 open，亦即給定 $A \in \Omega$ 存在 $\delta >0$ 使得 open ball $B_\delta(A) \subset \Omega$

觀察 open ball ${B_\delta }(A): = \left\{ {B:\left\| {A - B} \right\| < \delta } \right\}$ 故若我們選 $\delta := \alpha$ 亦即 選 $\delta := 1/\left\| {{A^{ - 1}}} \right\|$ 即可。

我們接著證明 映射 $A \to A^{-1}$ 為 continuous on $\Omega$
觀察
\[\begin{array}{l}
\left\| {{B^{ - 1}} - {A^{ - 1}}} \right\| = \left\| {{B^{ - 1}}\left( {A - B} \right){A^{ - 1}}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le \left\| {{B^{ - 1}}} \right\|\left\| {A - B} \right\|\left\| {{A^{ - 1}}} \right\| \le \frac{{\left\| {{B^{ - 1}}} \right\|\beta }}{\alpha }  \ \ \ \ (\star)
\end{array}\]再者我們回憶 $(*): \left( {\alpha  - \beta } \right)|{\bf{x}}| \le |B{\bf{x}}|$，現在若取 ${\bf x} := B^{-1}{\bf y}$ 可得
\[\begin{array}{l}
\left( {\alpha  - \beta } \right)|{\bf{x}}| \le |B{\bf{x}}|\\
 \Rightarrow \left( {\alpha  - \beta } \right)|{B^{ - 1}}{\bf{y}}| \le |B{B^{ - 1}}{\bf{y}}|\\
 \Rightarrow |{B^{ - 1}}{\bf{y}}| \le \frac{1}{{\alpha  - \beta }}|{\bf{y}}|\\
 \Rightarrow \left\| {{B^{ - 1}}} \right\| \le \frac{1}{{\alpha  - \beta }}
\end{array}\]故 $(\star)$ 變成
\[\begin{array}{l}
\left\| {{B^{ - 1}} - {A^{ - 1}}} \right\| \le \frac{{\left\| {{B^{ - 1}}} \right\|\beta }}{\alpha }\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} \le \frac{\beta }{{\left( {\alpha  - \beta } \right)\alpha }}
\end{array}\]現在若我們讓 $||A-B|| \to 0$ 亦即  $||A - B|| \to 0 \Rightarrow \beta  \to 0$ 則
\[
||A^{-1} - B^{-1}|| \to 0
\]亦即映射 $A \to A^{-1}$ 為 continuous on $\Omega$


ref: W. Rudin, Principle of Mathematical Analysis, 3rd Edition.

[機率論] 淺論 弱大數法則

以下我們討論一些關於 弱大數法則(Weak Law of Large Numbers, WLLN) 的結果，首先介紹 一組隨機變數 數列 的 機率收斂  (Convergence in Probability)

=============================
Definition: Convergence in Probability
令 $Y_n$ 為一組隨機變數 sequence，我們說 $Y_n$ converges to $Y$ in probability 若下列條件成立：對任意 $\varepsilon >0$
\[
P(|Y_n - Y| > \varepsilon) \rightarrow 0 \;\; \text{ as  $n \rightarrow \infty$}
\]=============================

Comments:
1. 上述定義等價為
\[
P(|Y_n - Y| \leq \varepsilon) \rightarrow 1 \;\; \text{ as  $n \rightarrow \infty$}
\]
2. 上述定義中 $Y_n \to^P Y$ 的 $Y$ 可為隨機變數或者為常數。
3. 機率收斂在 機率論與隨機過程，以及 統計理論中 扮演重要角色，比如機率收斂在統計中等價稱為 consistent estimator，在此不做贅述。

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

Definition: Uncorrelated Random Variables

接著再回憶我們說一組隨機變數 $X_i, \; i \in \mathbb{N}$ 且 $E [X_i^2] <\infty$ 為 uncorrelated 若下列條件成立：當 $i \neq j$
\[
E[X_i X_j] = E[X_i] E[X_j]
\]============================

現在我們看個 uncorrelated 隨機變數的結果

=============================
Theorem:
令 $X_1, X_2,...X_n$ 為 uncorrelated 且 $E[X_i^2] < \infty$ 則
\[
var(X_1 + ... + X_n ) = var(X_1) + ... + var(X_n)
\]其中 $var(X)$ 為 variance of $X$。
=============================

Proof: omitted.


=============================
Lemma:
若 $p >0$ 且 $E[|X_n|^p] \rightarrow 0$ 則 $X_n \rightarrow 0$ in probability。
=============================

Proof:
要證明 $X_n \rightarrow 0$ in probability，亦即
\[P(|{X_n} - 0| > \varepsilon ) \to 0
\]首先觀察下列事件等價
\[\begin{array}{l}
\left\{ {|{X_n}| > \varepsilon } \right\} = \left\{ {|{X_n}{|^p} > {\varepsilon ^p}} \right\}\\
 \Rightarrow P\left\{ {|{X_n}| > \varepsilon } \right\} = P\left\{ {|{X_n}{|^p} > {\varepsilon ^p}} \right\}
\end{array}
\]由 Markov inequality 可知
\[P\left\{ {|{X_n}| > \varepsilon } \right\} = P\left\{ {|{X_n}{|^p} > {\varepsilon ^p}} \right\} \le \frac{{E\left[ {|{X_n}{|^p}} \right]}}{{{\varepsilon ^p}}}
\]由於 $E[|X_n|^p] \rightarrow 0$ ，且 $\varepsilon^p $ 為定值，故
\[P\left\{ {|{X_n}| > \varepsilon } \right\} \le \frac{{E\left[ {|{X_n}{|^p}} \right]}}{{{\varepsilon ^p}}} \to {\rm{0}}\]


=============================
Theorem: $L^2$ Weak Law
令 $X_1, ..., X_n$ 為 uncorrelated 隨機變數 且 $E[X_i] = \mu$，$var(X_i) \le C < \infty$。現在定義隨機變數的和 $S_n := X_1 + X_2 + ... + X_n$ 則
\[
S_n/n \rightarrow \mu \text{  in Probability as  $n \rightarrow \infty$}
\]=============================

Proof
要證明 給定 $\varepsilon>0$ 當 $n \rightarrow \infty$
\[P\left( {\left| {\frac{{{S_n}}}{n} - \mu } \right| > \varepsilon } \right) \to 0 \ \ \ \ (*)
\]不過如前一個定理所述，若我們可以證明 $E\left[ {{{\left| {\frac{{{S_n}}}{n} - \mu } \right|}^2}} \right] \to 0$ 則 $(*)$ 自動滿足。

首先觀察
\[E\left[ {\frac{{{S_n}}}{n}} \right] = \frac{1}{n}E\left[ {{S_n}} \right] = \frac{1}{n}\sum\limits_{i = 1}^n {E{X_i}}  = \frac{\mu }{n}n = \mu \]則
\[\begin{array}{l}
E\left[ {{{\left| {\frac{{{S_n}}}{n} - \mu } \right|}^2}} \right] = E\left[ {{{\left| {\frac{{{S_n}}}{n} - E\left[ {\frac{{{S_n}}}{n}} \right]} \right|}^2}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} = var\left( {\frac{{{S_n}}}{n}} \right) = \frac{1}{{{n^2}}}var\left( {{S_n}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{{n^2}}}var\left( {\sum\limits_{i = 1}^n {{X_i}} } \right)
\end{array}\]由於 $X_1, ..., X_n$ 為 uncorrelated 隨機變數，故我們有 $var\left( {\sum\limits_{i = 1}^n {{X_i}} } \right) = \sum\limits_{i = 1}^n {var\left( {{X_i}} \right)} $ 將此結果帶入上式可得
\[\begin{array}{l}
E\left[ {{{\left| {\frac{{{S_n}}}{n} - \mu } \right|}^2}} \right] = \frac{1}{{{n^2}}}var\left( {\sum\limits_{i = 1}^n {{X_i}} } \right) = \frac{1}{{{n^2}}}\sum\limits_{i = 1}^n {var\left( {{X_i}} \right)} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} \le \frac{1}{{{n^2}}}Cn = \frac{1}{n}C \to 0
\end{array}\]當 $n \rightarrow \infty$ 故 $L^2$-convergence。又 $L^2$ convergence 保證 convergence in Probability，故
\[P\left( {\left| {\frac{{{S_n}}}{n} - \mu } \right| > \varepsilon } \right) \to 0 \ \ \ \ \square
\]

現在問題變成若我們想要拓展上述的 Weak law (e.g., 拔除 finite 2nd moment 條件 )，則我們必須引入一些新的定義如下：

============================
Definition: Tail Equivalence of Two Sequences of Random Variables
我們說兩隨機變數的 sequences $\{X_n\}$ 與 $\{Y_n \}$ 為 Tail Equivalent 若下列條件成立
\[
\sum_n P(X_n \neq Y_n) < \infty
\]===========================

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

Definition: Truncation Function
定義以下剪切函數(truncation function)
\[X{1_{\left| X \right| \le M}} := \left\{ \begin{array}{l}
X,\begin{array}{*{20}{c}}
{}&{}
\end{array}\left| X \right| \le M\\
0,\begin{array}{*{20}{c}}
{}&{}
\end{array}\left| X \right| > M
\end{array} \right.\]============================

首先看幾個結果
FACT 1: 若 $Y \ge 0$ 且 $p >0$ 則
\[
E[Y^p] = \int_0^\infty p y^{p-1} P(Y>y)dy
\]Proof: 首先觀察積分
\[\begin{array}{l}
\int_0^\infty  p {y^{p - 1}}P(Y > y)dy = \int_0^\infty  p {y^{p - 1}}\int_\Omega ^{} {{1_{Y > y}}dP} dy\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \int_0^\infty  {\int_\Omega ^{} {{1_{Y > y}}} p} {y^{p - 1}}dPdy\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \int_\Omega ^{} {\int_0^\infty  {{1_{Y > y}}} p{y^{p - 1}}dydP} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \int_\Omega ^{} {\int_0^Y {p{y^{p - 1}}} dydP}
\end{array}\] 因為 $ \int_0^Y {p{y^{p - 1}}} dy = {Y^p}$ 故代入上式可得
\[ \Rightarrow \int_0^\infty  p {y^{p - 1}}P(Y > y)dy = \int_\Omega ^{} {\int_0^Y {p{y^{p - 1}}} dydP = } \int_\Omega ^{} {{Y^p}dP = } E[{Y^p}] \ \ \ \ \square
\]


現在我們可以介紹 General Weak Law of Large Number：

=============================
Theorem: Weak Law of Large Number
令 $X_1, X_2, ... $ 為 i.i.d. 隨機變數 且 $S_n := X_1 + X_2 + ... + X_n$。若
(1) $\sum_{j=1}^n P(|X_j > n|) \rightarrow 0$
(2) $\frac{1}{n^2} \sum_{j=1}^n E[ X_j^2 1_{|X_j \le n|}] \rightarrow 0$
則
\[
S_n / n - \mu_n \rightarrow 0 \text{  in Probability}
\] 其中 $a_n := \sum_{j=1}^{n}E [X_j 1 _{|X_j| \le n}]$
=============================

Comments
在證明之前有幾點值得注意，上述 Weak Law of Large Number 並無對 $E[X_i^2]$ 有做假設

Proof
首先定義 $X_{nj}' := X_j 1_{|X_j| \le n}$ 且 $S_n' := \sum_{j=1}^n X_{nj}'$ 則觀察 Tail parts
\[\sum\limits_{j = 1}^n {P\left( {{X_{nj}}' \ne {X_j}} \right)}  = \sum\limits_{j = 1}^n {P\left( {\left| {{X_j}} \right| > n} \right) \to 0}
\]上述收斂成立由 Hypothesis $(1)$。接著我們觀察
\[\begin{array}{l}
P\left( {\left| {{S_n} - {S_n}'} \right| > \varepsilon } \right) \le P\left( {{S_n} \ne {S_n}'} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} \le P\left( {\bigcup\limits_{j = 1}^n {\left\{ {{X_{nj}}' \ne {X_j}} \right\}} } \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array} \le \sum\limits_{j = 1}^n {P\left( {{X_{nj}}' \ne {X_j}} \right)}  = \sum\limits_{j = 1}^n {P\left( {\left| {{X_j}} \right| > n} \right) \to 0}
\end{array}\]故可知
\[
S_n - S_n' \rightarrow 0 \text{  in Probability }
\]
現在觀察
\[\begin{array}{l}
P\left( {\frac{{\left| {{S_n}' - E{S_n}'} \right|}}{n} > \varepsilon } \right) \le \frac{{E\left[ {{{\left| {{S_n}' - E{S_n}'} \right|}^2}} \right]}}{{{n^2}{\varepsilon ^2}}} = \frac{{{\mathop{\rm var}} \left( {{S_n}'} \right)}}{{{n^2}{\varepsilon ^2}}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array}{\rm{ = }}\frac{{{\mathop{\rm var}} \left( {{S_n}'} \right)}}{{{n^2}{\varepsilon ^2}}}{\rm{ = }}\frac{1}{{{n^2}{\varepsilon ^2}}}\sum\limits_{j = 1}^n {{\mathop{\rm var}} \left( {{X_{nj}}'} \right)} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \le \frac{1}{{{n^2}{\varepsilon ^2}}}\sum\limits_{j = 1}^n {E\left[ {{{\left( {{X_{nj}}'} \right)}^2}} \right]} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{{n^2}{\varepsilon ^2}}}\sum\limits_{j = 1}^n {E\left[ {{{\left( {{X_j}{1_{\left\{ {\left| {{X_j}} \right| \le n} \right\}}}} \right)}^2}} \right]} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{{n^2}{\varepsilon ^2}}}\sum\limits_{j = 1}^n {E\left[ {{X_j}^2{1_{\left\{ {\left| {{X_j}} \right| \le n} \right\}}}} \right]}  \to 0 \ \ \ \ (**)
\end{array}\]上式收斂結果來自 Hypothesis (2)。

注意到\[{a_n}: = \sum\limits_{j = 1}^n E [{X_j}{1_{|{X_j}| \le n}}] = E\left[ {\sum\limits_{j = 1}^n {{X_j}{1_{|{X_j}| \le n}}} } \right] = E\left[ {{S_n}'} \right]\]故由 $(**)$ 可知
\[\frac{{{S_n}' - {a_n}}}{n}\mathop  \to \limits^P 0\]故現在觀察
\[\frac{{{S_n} - {a_n}}}{n} = \frac{{{S_n} - {S_n}' + {S_n}' - {a_n}}}{n} = \frac{{{S_n} - {S_n}'}}{n} + \frac{{{S_n}' - {a_n}}}{n}\mathop  \to \limits^P 0\]

[電子學] 淺談二極體 Diode - I/V characteristics

半導體二極體 (Diode) 基本上即為一個 PN junction 如下圖所示

上圖中 箭頭方向表示 diode 的電流方向，亦即 diode 為兩端子 單向導通的 (非線性)元件。

理想二極體 (Ideal Diode)特性：
下圖為 Ideal diode 的電流電壓特性圖 ($i,v$ characteristics)

• 施加 "負"電壓 (逆向偏壓 reverse biase) 在 diode 兩端上，diode不導通 $\Rightarrow$ 電流為 $0$ $\Rightarrow$ 此時 diode 呈現開路(open circuit)狀態。
• 施加 "正" 電壓 (順向偏壓 forward bias)在 diobe 兩端上，則 diode 導通$\Rightarrow$ 此時 diode 呈現短路(short circuit)狀態。

真實二極體 (Real diode) 的電流/電壓 (I/V characteristics)特性如下圖

當diode兩端施加電壓  $v>0$ (上圖右方 forward bias 部分)，我們可以近似其 電流電壓關係為
\[
i = I_S \left[ e^{v/V_T}-1\right]
\]其中 $I_S$ 為 反向飽和電流 (reversed saturation current)，$V_T$ 為 熱電壓 (thermal voltage)滿足下式
\[
V_T := \frac{kT}{q}
\]其中 $k$ 為 Boltzmann's constant = $1.38 \times 10 ^{-23}$ Joules/Kelvin，$T$為絕對溫度 (Kelvin, K)，$q$ 為 單位電荷帶電量=$1.60 \times 10^{-19}$ Coulomb。

一般而言在室溫下 $(300 )$ K 時，thermal voltage 為 $V_T = 25$ mV (=$0.025$ V)。

現在我們觀察上圖，我們可以得到下列結論：

• 當輸入 diode 的電壓低於 $0.5 {\rm v}$時，其 diode 電流 $i$ 幾乎可以忽略，此 $0.5 \rm v$ 稱為 切入電壓 (cut-in voltage)
• 當輸入 diode 電壓 高於 cut-in voltage $0.5 \rm v$ 時，diode 視為 forward bias (對比於 ideal diode, forward bias 電壓為 0 $\rm v$)。
• 當輸入 diode 電壓 高於 $0.7 \rm v$時(一般約為 $0.6~0.8$ v)，diode 視為完全導通，故可假設導通的 diode 有 0.7 壓降。

[半導體] N-P type semiconductor

半導體 (Semiconductor): 

導電度(electric conductivity) 介於 導體(conductor or metal) 與 絕緣體 (insulator) 之間之物質 ，低溫時，導電度不佳，但若提高溫度時(提高溫度視為給予外界能量)，則導電度良好e.g.,  元素週期表 IV族元素 Si, Ge 。

一般可用有無 添加(doping) 雜質分為

1.  本質半導體 (Intrinsic Semiconductor) 
2. 雜質 or 外質半導體 (Extrinsic Semiconductor)。

Comments:
1. 本質半導體(intrinsic semiconductor) 一般可視為 純矽(pure silicon) (亦即無任何雜質的矽) 的同義字；另一方面外質半導體一般又稱作 (Doped silicon) 另外對於 外質半導體 我們可在由添加的成分不同分成

• N-type semiconductor: 添加 V族元素 e.g., 磷P, 砷As 
• P-type semiconductor: 添加 III族元素 e.g., 硼B, 鎵 Ga 

2. 本質半導體 電子與電洞濃度相同 $n = p: = {n_i}(T) \approx 1.5 \times {10^{10}}\;(\# /c{m^3})$。關於電子與電洞濃度會在稍後在做進一步介紹。

3. 導電度 (Conductivity, $\sigma$) 定義為 每單位電場強度 $E$ 造成的飄移電流密度(drift current density, $J$)。一般材料用 電阻率 (Resistivity, $\rho$) 來表示 材料阻擋電流的程度，定義為

\[
\rho := 1/\sigma
\]

3. 導體的例子： 銅 (Cu) e.g., 銅導線

不過在介紹 N-type 與 P-type 半導體之前，我們需要一些對半導體的專有名詞的介紹：

Si 的原子結構與特性

Si 原子結構：

Si 原子數: 14，其原子結構的最外層有4 個價電子(Valence electron)

上圖顯示了矽晶圓的原子結構 (以二維表示)，每一個 矽原子與他人以共價鍵 (Covalent bonds) 方式結合。

自由電子 (free electron) 與 電洞(hole)

當施加外在能量(e.g., 提高溫度)，則電子會得到能量 $\Rightarrow $ 導電性提升，

• 自由電子(free electrons)： (帶負電荷)
  當價電子 (valence electron) 或得額外能量脫離 共價鍵結構(covalenet bonds) 便會成為自由電子 free electron，亦即不再被束縛，可以在整個 Si 晶圓中自由移動 (形成電流)
• 電洞(holes)：(帶正電荷)
  電子移動後留下的空洞稱為電洞。

載子 (carriers) 與 載子濃度

可以自由移動帶電荷的物質微粒 e.g., holes and electrons 都可視為一種載子，

關於載子濃度可分為 電子濃度與 電洞濃度

• 電子濃度 $(n)$: negative charge
• 電洞濃度 $(p)$: positive charge 

上述兩者單位皆為 $\#/{cm^3}$

熱平衡狀態 (Thermal Equilibrium)

產生率 (generation rate, $G(T)$)：表單位時間 單位體積產生的電子電洞對

\[G(T): = {f_1}(T)
\]複合率 (recombination rate, $R(T)$)：表單位時間 單位體積複合的電子電洞對

\[R(T): = n \times p \times {f_2}(T)
\]其中 $f_1(T), f_2(T)$ 表示為 產生率 與 複合率皆為 溫度 $T$ 的函數。
現在我們說熱平衡即為 $R(T) \equiv G(T)$，由上式 $G(T), R(T)$ 的定義，我們改寫熱平衡關係如下

\[\begin{array}{*{20}{l}}
{R(T) \equiv G(T)}\\
{ \Rightarrow n \times p \times {f_2}(T) = {f_1}(T)}\\
{ \Rightarrow n \times p = \frac{{{f_1}(T)}}{{{f_2}(T)}}: = {f_3}\left( T \right) = {n_i}^2\left( T \right)}
\end{array}\]上式中的 $n \times p = n_i^2(T)$ 稱作 質量作用定律 (mass-action law)

現在考慮 均勻參雜 (Uniform doping)  III, V 族元素，則我們將可大幅改變半導體的電特性。但不改變其他的物理化學性質

N-type Semiconductor
當半導體參雜 5價 雜質 e.g.,  磷P, 砷As 時，由於這些雜質原子因具有5個價電子，故會在半導體中額外提供一個自由電子，但不形成電洞。

• 5價雜質又稱 施子雜質(donor impurities) 以 $N_D$ 表示雜質濃度
• 加入5價雜質後，半導體的電子濃度 $n$ 會大幅提升 由 $n=n_i$ 提升到 $N_D$
• 加入5價雜質後，半導體的電洞濃度 $p$ 會大幅下降 
• 總和前述，可知道 $n >> p$ 故電子為 多數載子(Majority carrior) 而 電洞為少數載子 (minority carrior) ，我們稱此類添加了 5價雜質的半導體為 N-type Semiconductor 

P-type Semiconductor
當半導體參雜 3價 雜質 e.g., 硼B, 鎵 Ga 時，由於這些雜質原子因具有3個價電子，故會在半導體中接受一個自由電子並在他處形成一個電洞，但不同時產生額外自由電子。

• 3價雜質又稱 受子雜質(acceptor impurities)以 $N_A$ 表示雜質濃度
• 加入3價雜質後，半導體的電洞濃度 $p$ 會大幅提升 由 $p = n_i$ 提升到 $N_A$
• 加入3價雜質後，半導體的電子濃度 $n$ 會大幅下降 
• 總和前述，可知道 $p >> n$ 故電洞為多數載子(Majority carrior) 而 電子為少數載子 (minority carrior) ，我們稱此類添加了 3價雜質的半導體為 P-type Semiconductor 

Comment:
不論 N-type 或者 P-type 半導體都呈現電中性 (charge neutrality)
對 N-type 而言：5價雜質放出自由電子之後，本身雜質離子變成帶正電荷，此數目與帶負電的電子相同故整體而言呈現電中性。
對 P-type 而言：3價雜質接受自由電子 額外產生電洞之後，本身雜質離子變成帶負電荷，此數目與帶正電的電洞相同故整體而言呈現電中性。

Appendix: 專有名詞
價電子(valence electron):原子最外層能圈之電子數
游離 (ionizing):原子失去電子或獲得電子的現象
離子(ion):產生游離的原子:

• a.正離子:失去電子而帶正電之原子
• b.負離子:獲得電子而帶負電之原子

[轉載] 信耶穌才能得救?這樣霸道?

這是轉貼唐崇榮 牧師於2008年神學講座
是一個提問的轉錄"信耶穌才能得救? 這樣霸道?"
.
答案非常有趣 跟各位分享一下
.
[youtube=http://www.youtube.com/watch?v=lX6pTHt7sB0] 

.
=======以下轉錄自 基督教小小羊園地===========
歸正運動是歷史上一個最純潔的運動，
因為它從起初就呼籲歸回聖經。
.
歸正不是一個宗派，
它是一種精神，一個神聖的邀請，
邀請全教會全信徒回到全本聖經。
.

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

延伸閱讀: 基督教小小羊園地

很棒的一個網站，內容以歸正神學為基礎，相信全本聖經是由神所默示，且沒有謬誤之處
推薦對基督教徒與非基督教徒參考

.

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

.

關於 唐崇榮 博士 簡介 (Ref: Wiki)

.

[動態規劃] 淺談 離散時間動態規劃 (1) - Bellman equation in Infinite Horizon

這次要介紹 無窮時間的 Bellman Equation，亦即我們的 Cost function 為 branch cost 加到無窮大的情況：
\[
J(u) := \displaystyle \sum_{k=0}^{\infty} J(x(k), u(k)) + \Phi(x(N))
\]
那麼現在問題變成 儘管我們手上有 有限時間的 Bellman Equation (請參考前篇文章)，但對於此類無窮時間的問題該如何處理??

亦即如果今天我們 cost function 的 $N \rightarrow \infty$ 該怎麼處理? 我們稱這一類問題叫做 Steady State Dynamic Programming 或稱 Dynamic Programming in Infinite Horizon。

無窮時間的動態規劃問題 (Dynamic Programming Problem in Infinite Horizon)：

考慮 Performance index (cost function)
\[
J(u) := \displaystyle \sum_{k=0}^{\infty} J(x(k), u(k)) + \Phi(x(N))
\]狀態方程( state equation)
\[
x(k+1) = f(x(k), u(k)), \ x(0) \ \text{is given} \\
\]其中 $x(k)$ 為系統在第 $k$ 時刻的 狀態，$f:\mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}^n$，
與控制力拘束條件
\[
u(k) \in \Omega
\]其中$\Omega$ 為拘束條件

此時對應的 Bellman Equation (or Dynamic Programming Equation) 寫為如下的 functional form
\[
I(x) = \min_{u \in \Omega} \{ J(x,u) + I(f(x,u)) \}
\]亦即與 $N$ 無關
上式稱為 Steady State Bellman Equation 或者 Bellman Equation in Infinite Horizon。


現在我們看個例子：

Example
考慮系統狀態方程表示如下：
\[x(k+1) = x(k) - u(k)
\]且 cost function 為
\[
J(u) = \displaystyle \sum_{k=0}^{\infty} (x(k+1)-u(k))^2 + x^2(k+1)
\]試求 Optimal $u^*$ 與其對應的 optimal cost to go

Solution
首先我們寫下 Steady State Bellman Equation:
\[
I(x) = \min_{u \in \Omega} \{J(x,u) + I(f(x,u)) \}
\]現在我們要求解上式，故我們首先猜一個解 (事實上此問題在之前文章中我們解過有限時間的 Bellman equation，當時我們解出 Optimal cost to go 具有 $I(x) = \alpha x^2$ 的形式，有興趣的讀者可前往前篇文章檢驗)，故我們現在很合理的可以猜這 $I(x) = \alpha x^2$ 其中 $\alpha$ 為代定係數 $\alpha \geq 0$。
故我們將此解代入 Steady State Bellman Equation，可得
\[\begin{array}{l}
I(x) = {\min _{u \in \Omega }}\{ J(x,u) + I(f(x,u))\} \\
 \Rightarrow \alpha {x^2} = {\min _{u \in \Omega }}\{ {(x - u)^2} + {x^2} + \alpha {\left( {x - u} \right)^2}\} \\
 \Rightarrow \alpha {x^2} = {\min _{u \in \Omega }}\{ {x^2} + \left( {1 + \alpha } \right){\left( {x - u} \right)^2}\}
\end{array}
\]由 FONC: $\frac{\partial }{{\partial u}} = 0$，我們可求解上式右方最佳控制力 $u^*$ ：
\[
u^* = x
\]故代回上式我們得到
\[\begin{array}{l}
\alpha {x^2} = {x^2}\\
 \Rightarrow \alpha  = 1
\end{array}
\] 故如果我們選 $\alpha =1$即可解得 Steady-State Bellman Equation。 $\square$

上述問題可以進一步拓展到 $\mathbb{R}^n$ 空間，這一類問題在控制理論中稱為無窮時間的線性二次調節器 (Linear Quadratic Regulator, LQR) 問題，有興趣的讀者請參考：
[最佳控制] 離散時間 穩態線性二次調節器 Discrete Time Linear Quadratic Regulator in Infinite Horizon via Dynamic Programming

[機率論] 期望值 與 Lebesgue 積分

這次要介紹機率論中一個重要的概念：期望值 (Expectation)，本質上期望值被視為一個 Lebesgue 積分。更進一步地說就是在較抽象的高等機率論中， 期望值被定義為對某機率測度 (Probability measure, $P$ ) 的 Lebesgue 積分 。亦即 考慮機率空間為 $(\Omega, \mathcal{F}, P)$，則 $E[X]$ 具有如下形式：
\[
E[X] := \int_{\Omega} X d P  = \int_\Omega X(\omega) P(d\omega)
\]

我們由 Simple Function 出發 逐步建構 Lebesgue integral：

Step 1: Simple function 的期望值：

首先，我們定義 $X$ 為一個 simple function。亦即此函數可由 可測集合 (measurable sets $A_i$ ) 的 Indicator function 所組成。我們將其寫作是 Finite sum 如下：
\[
X = \displaystyle \sum_{i=1}^{n} c_i 1_{A_i}
\]其中 $c_i \in \mathbb{R}$， $A_i \in \mathcal{F}$ 且
\[{1_A}\left( x \right): = \left\{ \begin{array}{l}
1,\begin{array}{*{20}{c}}
{}
\end{array}if\begin{array}{*{20}{c}}
{}
\end{array}x \in A\\
0,\begin{array}{*{20}{c}}
{}
\end{array}if\begin{array}{*{20}{c}}
{}
\end{array}x \notin A
\end{array} \right.\]則我們定義 對此 Simple function $X$ 的期望值 (或稱對此 Simple function 的 Integral)為
\[
E[X] := \int X dP := \sum_{i=1}^n c_i P( \{A_i\} )
\]接著，我們定義對 非負隨機變數 的期望值：

Step 2: 非負隨機變數 的期望值：

對任意 非負隨機變數 $Y$ $(Y : \Omega \rightarrow [0,1])$，我們定義 $Y$ 的期望值為上述 simple function 的期望值的 supremum，亦即
\[
E[Y] := \sup \{E[X]: 0 \leq X \leq Y \ \text{with $X$ a simple function}  \}
\] 注意到 $E[X] := \int X dP := \sum_{i=1}^n c_i P(\{A_i\}) $


有了上述定義，我們可以拓展到一般的隨機變數：


Step 3: 一般隨機變數的期望值：

最後，對一般的 隨機變數的情況，該如何定義其期望值呢?

想法如下：
透過將 一般隨機變數 轉換為 上述 非負隨機變數，再用上述非負隨機變數所定義的期望值 即可。

故現在考慮 $Y$ 為任意隨機變數，我們引入兩個 新的非負隨機變數 $Y^+, Y^- \geq 0$ (此法類似線性規劃中，將最佳化問題改寫成標準型式所加入的 slack variable: 有興趣的讀者請參考: [最佳化] 淺談線性規劃(0)- Standard form of Linear Programming )：
\[
Y^+ := Y \cdot 1_{ \{ Y \geq 0 \} }\\
Y^- := -Y \cdot 1_{ \{ Y \leq 0 \}}
\]那麼現在觀察上述 新引入的隨機變數，我們可知其與原本任意隨機變數有如下關係：
\[
Y=Y^+ - Y^-
\]且上述新的隨機變數 (由於 $Y^+, Y^- \geq 0$)，故其期望值可由先前所定義的 非負隨機變數期望值定義而得，故 $E[Y^+], E[Y^-]$ 為 well-defined。有了這些結果我們可以定義對一般隨機變數 $Y$ 的期望值為：
\[
E[Y] := E[Y^+] - E[Y^-] \ \ \ \ (*)
\]上式為 well-defined 若 $E[Y^+], E[Y^-]$ 並非全為 $\infty$ (亦即只要不要發生 $\infty - \infty$ 的情況，則上述定法的期望值 $E[Y]$ 都是 well-defined。 )

Comment:
1. 上式 $(*)$ 與下列積分等價：
\[
\int Y dP := \int Y^+ dP - \int Y^- dP
\]
2. 若 $E|X| = E[X^+] + E[X^-] < \infty$ 則我們稱 $X$ 有 finite expectation，(因為 $E[X^+] < \infty$ 且 $E[X^-] < \infty$)。
3. 如果現在給定 $X$ 但想計算 $X$ 在某個子集上的期望值，也就是說我們現在不是取整個樣本空間 $\Omega$ 而是只有某個 $\mathcal{F}$ 中的集合 $A \in \mathcal{F}$ 則我們仍可求其期望值
\[
\int_A X dP = \int_\Omega X 1_A dP = E[X 1_A]
\]上式稱作 integral of $X$ with respect to $P$ over $A$。另外若此積分存在且有限，則我們稱 $X$ 為 integrable with respect to $P$ over $A$


注意到期望值 $E[X] = \int_\Omega X dP $ 仍不容易計算，因為樣本空間 $\Omega$ 可以內含各式各樣奇形怪狀的東西比如說 $\Omega:=\{apple, orange...\}$，此時計算 $E[X]$ 顯然會過於抽象。那麼我們想問什麼時候才可能比較容易計算 $E[X]$？答案是如果 能給出 $X$ 的 累積分佈函數 (Cumulative Distribution Function, CDF) , 記作 $F$, with respect to $P$，亦即 $F(x) := P(X \le x)$  則 $E[X]$ 可計算如下
\[
E[X] = \int_\Omega X dP = \int_{-\infty}^{\infty} x dF(x) \;\;\;\;\; (*)
\]讀者應注意到第二等式 內含的是 $x$ 不是 $X$，且 上式 $(*)$ 為 Riemann-Stigjies Integral。
若 $X$ 有機率密度函數 (Probability Density Function, f) with respect to $P$ 則回憶機率密度函數定義為 $dF(x)/dx = f(x)$ 故我們可以得到更容易計算的期望值如下
\[
E[X] = \int_{-\infty}^{\infty} x dF(x) = \int_{-\infty}^\infty x f(x) dx
\]但上式有一定限制，因為任意隨機變數必定存在 CDF 但不一定有 PDF (因為 CDF 不一定可微，故不一定有 PDF)

Comments: 
1. 若 $g$ 為 measurable 函數 on $\mathbb{R}$ 則我們亦可計算 $E[g(X)]$，亦即
\[
E[g(X)] = \int_\Omega g(X) dP = \int_{-\infty}^\infty g(x) dF(x) = \int_{-\infty}^\infty g(x) f(x)dx
\]
2. 若 $X$ 為離散隨機變數取值為 $x_1,...,x_n$ 且 具有 probability mass function, pmf with respect to $P$, 記作 $P(X = x_n) = p(x_n)$, 則
\[
E[X] = \sum_{n=1}^\infty x_n p(x_n)
\]
且
\[
E[g(X)] = \sum_{n=1}^\infty g(x_n) p(x_n)
\]

現在看幾個例子：
Example 1:
$\Omega :=\{1,2,3,4\}$ 且 $\mathcal{F} := \sigma ( \{1\}, \{2\}, \{3\}, \{4\})$ 且 令隨機變數 $X = i$ 其中 $i=1,2,3,4$ 且
\[
P(X=1)=1/2;\;\; P(X=2) = 1/4;\;\; P(X=3)=1/6;\;\; P(X=4)=1/12
\]現在令 $X:= 5 \cdot 1_{\{X=1\}} + 2 \cdot 1_{\{X=2\}} - 4 \cdot 1_{\{X=3 \text{ or } X=4\}}$。試求 $E[X]=?$
Solution:
\[\begin{array}{*{20}{l}}
\begin{array}{l}
E[X] = \int_\Omega  {XdP = \sum\limits_n^{} {{x_n}P\left( {X = {x_n}} \right)} } \\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = 5\int_\Omega  {{1_{\left\{ {X = 1} \right\}}}dP}  + 2\int_\Omega  {{1_{\left\{ {X = 2} \right\}}}dP}  - 4\int_\Omega  {{1_{\left\{ {X = 3orX = 4} \right\}}}dP}
\end{array}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = 5 \cdot P\left( {X = 1} \right) + 2 \cdot P\left( {X = 2} \right) - 4 \cdot \underbrace {P\left( {X = 3orX = 4} \right)}_{ = P\left( {\left\{ {X = 3} \right\} \cup \left\{ {X = 4} \right\}} \right) = P\left( {X = 3} \right) + P\left( {X = 4} \right)}}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = 5\left( {\frac{1}{2}} \right) + 2\left( {\frac{1}{4}} \right) - 4\left( {\frac{1}{6} + \frac{1}{{12}}} \right) = 2}
\end{array}\]

Example 2:
同上題，試求 $E[X^2]=?$
Solution:
\[\begin{array}{l}
E[{X^2}] = \int_{ - \infty }^\infty  {{x^2}f\left( x \right)dx}  = \sum\limits_n^{} {{{\left( {{x_n}} \right)}^2}P\left( {X = {x_n}} \right)} \\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = 5P\left( {X = 1} \right) + 2P\left( {X = 2} \right) + 4P\left( {\left\{ {X = 3} \right\} \cup \left\{ {X = 4} \right\}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = 25\left( {\frac{1}{2}} \right) + 4\left( {\frac{1}{4}} \right) + 16\left( {\frac{1}{6} + \frac{1}{{12}}} \right) = \frac{{35}}{2}
\end{array}\]

Example 3:
假設 $X \sim \mathcal{N}(0,1)$ 亦即我們有 pdf
\[
f_X(x) = \frac{1}{ \sqrt{2 \pi}} \exp(-x^2/2)
\]試證 $E[X]=0$
Proof:
觀察 \[\begin{array}{l}
E[X] = \int_\Omega  {XdP}  = \int_{ - \infty }^\infty  {xdF\left( x \right)}  = \int_{ - \infty }^\infty  {xf\left( x \right)dx} \\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \int_{ - \infty }^\infty  {x\frac{1}{{\sqrt {2\pi } }}\exp \left( { - {x^2}/2} \right)dx} \\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \frac{1}{{\sqrt {2\pi } }}\int_{ - \infty }^\infty  {x{e^{\frac{{ - {x^2}}}{2}}}dx}
\end{array}\]現在令\[u = \frac{{{x^2}}}{2} \Rightarrow 2du = 2xdx\]則 $E[X] = 0$
上述積分有更快速的做法如下：因為 被積函數 $x exp(-x^2/2)$ 為奇函數，且積分範圍對原點對稱 $(-\infty, \infty)$ 故積分為零。此法同理可證 $E[X^3]=E[X^5]=E[X^{2k+1}] = 0$ $k\in \mathbb{N} $



Example 4:
令 $a>0$，設 $F$ 為在 $[0, 3a]$ 上的連續函數滿足
\[F\left( x \right): = \left\{ \begin{array}{l}
\pi ,\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array}0 \le x < a\\
4 + a - x,\begin{array}{*{20}{c}}
{}&{}
\end{array}a \le x < 2a\\
{\left( {x - 2a} \right)^2},\begin{array}{*{20}{c}}
{}&{}
\end{array}x \ge 2a
\end{array} \right.
\]且在 $(0, 3a)$ 有一階導數連續 $F' = f$ 且 $f \in L^1(0,3a)$ 試計算 下列 Lebesgue-Stieltjes integral,
\[\int_{\left( {0,3a} \right]}^{} {xdF\left( x \right)}
\]

Solution
Lebesgue-Stieltjes integral 重點在於對於不連續處需給定其測度值。給定之後其餘部分如同一般微積分課程中採用的積分方法計算即可。故我們直接求解
\[\begin{array}{l}
\int_{\left( {0,3a} \right]}^{} {xdF\left( x \right)}  = \int_{\left( {0,a} \right]}^{} {xd\left( \pi  \right)}  + \int_{\left( {a,2a} \right]}^{} {xd\left( {4 + a - x} \right)}  + \int_{\left( {2a,3a} \right]}^{} {xd{{\left( {x - 2a} \right)}^2}} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} + {\left. {x\left( {F\left( x \right) - F\left( {x - } \right)} \right)} \right|_{x = a}} + {\left. {x\left( {F\left( x \right) - F\left( {x - } \right)} \right)} \right|_{x = 2a}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = 0 - \int_{\left( {a,2a} \right]}^{} {xdx}  + 2\int_{\left( {2a,3a} \right]}^{} {x\left( {x - 2a} \right)dx}  + a\left( {4 - \pi } \right) + 2a\left( { - 4 + a} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \frac{{{a^2}}}{2} + \frac{{8{a^3}}}{3} - \left( {4 + \pi } \right)a \ \ \ \ \square
\end{array}\]


一些期望值性質我們將其記錄如下：令 令 $a,b \in \mathbb{R}$ 且 $X,Y$ 為隨機變數，回憶  $E[X \cdot 1_A] = \int_A X dP$ 則
Property (1): Absolutely Integrability
\[
\int_A XdP < \infty \Leftrightarrow \int_A |X| dP < \infty
\]
Property (2): Linearity
\[
\int_A (a X + bY)dP = a \int_A X dP + b \int_A Y dP
\]
Property (3): Countably Additivity over sets
若 $\{A_n\}$ disjoint set sequences 則
\[
\int_{\cup_n A_n} X dP = \sum_n \int_{A_n} X dP
\]
Property (4): Nonnegativity
若 $X \ge 0$ $P$-almost surely (記作 $P$-a.s.)，則
\[
\int_A X dP \ge 0
\]其中 $P$-a.s. 表示 $P(X \ge 0) = 1$。

comments: 為何要在意 almost surely? 因為我們只關心測度非零的區域，測度為零的情況比如說 單點的測度為零我們並不關心。

Property (5): Monotonicity
若 $X_1 \le X \le X_2$ almost surely 則
\[
\int_A X_1 dP \le \int_A X dP \le \int_A X_2 dP
\]
Property (6): Modulus Inequality
\[
\left| \int_A X dP \right| \le \int_A |X| dP
\]


有了上述期望值的概念之後，我們可以看看如果我們取 limit 甚麼時候可以與 積分互換：也就是說 若現在 給定 一組隨機變數的數列 $\{X_n\}$ 我們想問
\[
\int_A \lim_{n \to \infty} X_n dP =?= \lim_{n \to \infty} \int_A X_n dP
\]回憶在高等微積分我們希望積分極限互換的情況的條件是需要 uniform convergence 但在機率論或者測度理論我們有以下三個極為重要的定理可以幫助我們在不需 uniform convergence 條件之下仍可達成積分與極限互換，此三個定理分別為 Dominated Convergence Theorem，Monotone Convergence Theorem、Fatou's Lemma
此三者為機率論 與積分理論的重要基石。分別紀錄如下：

考慮 $\{X_n\}$ 為任意隨機變數的 sequence。
=========================
Dominated Convergence Theorem (DCT)
若 $ P( \lim_{n \to \infty} X_n = X) =1$ 且對 $1 \leq n < \infty$，
\[
|X_n| \leq Y \text{ a.s. } \ \& \ E[Y] < \infty
\]，則 $E[|X|]<\infty$ 且
\[
\lim_{n \rightarrow \infty} E[X_n] = E[\lim_{n \rightarrow \infty} X_n] = E[X]
\]========================

=========================
Monotone Convergence Theorem (MCT)
若 $ 0 \leq X_n \leq X_{n+1} (亦即為 Monotone Functions), \ \forall n \geq 1$ 且 $\lim_{n \rightarrow \infty} X_n = X$則
\[
\lim_{n \rightarrow \infty} E[X_n] = E[\lim_{n \rightarrow \infty} X_n] = E[X]
\]========================

=========================
Fatou's Lemma
若 $X_n \ge 0 \text{ a.s. } \ \forall n \geq 1$ 則
\[
E[\liminf_{n \rightarrow \infty} X_n] \leq \liminf_{n \rightarrow \infty} E[X_n]
\]========================

ref:
S. I. Resnick, A Probability Path, Birkhauser
J. M. Steele, Stochastic Calculus and Financial Applications, Springer

J. A. Gubner, Probability and Random Processes for Electrical and Computer Engineers, Cambridge.

[動態規劃] 淺談 離散時間動態規劃 (0) - Principle of Optimality & Bellman equation in Finite Horzion

這次要跟大家介紹離散時間的動態規劃 (Dynamic Programming, D.P.) 問題：
此為最佳化理論中的一種方法，由 Professor Bellman 的 Principle of Optimality 所奠基。

基本想法如下： 從最佳解往回推 (backward)，逐步求解最佳值。再從初始位置沿著以求得的最佳路徑前進到最佳解。

我們現在把動態規劃問題寫下：

(有限時間) 動態規劃問題 (Dynamic Programming Problem in Finite Horizon)：

考慮 Performance index (cost function)
\[
J(u) := \displaystyle \sum_{k=0}^{N-1} J(x(k), u(k)) + \Phi(x(N))
\]與離散時間的狀態方程( state equation)
\[
x(k+1) = f(x(k), u(k)), \ x(0) \ \text{is given} \\
\]其中 $x(k) \in \mathbb{R}^n$ 為系統在第 $k$ 時刻的 狀態，$u(k) \in \mathbb{R}^m$ 為控制力，函數 $f:\mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}^n$，

另外我們仍需考慮控制力拘束條件
\[
u(k) \in \Omega_k(x(k))
\]其中 $\Omega_k$ 為第 $k$ 時刻的拘束條件

Comment:
1. 關於狀態方程：上式中的 $f(x(k),u(k))$ 稱作 autonomous state equation
但事實上DP問題亦可直接考慮 Non-autonomous state equation，(亦即函數中考慮時間 $k$)
\[
f((x(k), u(k), k))
\] Example: Autonomous and Non-autonomous system
Autonomous state equation:  $x(k+1) = x(k) + u(k)$
Non-autonomous state equation: $x(k+1) = k \cdot x(k)$

2. 關於 Performance Index
\[
J(u) := \displaystyle \sum_{k=0}^{N-1} J(x(k), u(k)) + \Psi (x(N))
\] 其中 $J(x(k), u(k))$ 稱為 Branch cost。 $\Psi (x(N))$ 稱為 Terminal cost。


現在我們介紹 Bellman's Principle of Optimality

==========================
Principle of Optimality
假設我們有一組 optimal sequence
\[
u^*(0), u^*(1), ..., u^*(N-1)
\]令 $x^*(0), x^*(1), ..., x^*(N)$ 為 induced states，亦即對 $k=0,1,...,N-1$
\[
u(k) \in \Omega_k(x^*(k))
\]且 $x^*(k+1) = f(x^*(k),u^*(k))$  (也就是說上述的 optimal sequence 最佳化整個問題。)
那麼現在考慮一個 子問題 (subproblem)：
考慮 $k = l$ (現在考慮由 時刻 $l$ 開始 (不是從 $0$ 開始) )，初始狀態現在為 $x(l)=x^*(l)$ (亦即此時的初始狀態 $x(l)$ 落在最佳解上 $x^*(l)$)，此時對應的 Cost function 為
\[
J_l(u) := \displaystyle \sum_{k=l}^{N-1} J(x(k), u(k)) + \Psi (x(N))
\]則 Principle of Optimality 告訴我們
\[
u^*(l), u^*(l+1), ..., u^*(N-1)
\]為對此 subproblem 的 optimal sequence.
==========================
Comment:
上述的 Principle of Optimality 其實表達的想法很簡單，就是如果已有一組最佳解序列在手，那麼從任意時刻開始的解也必須是最佳解。比如說我有一組最佳控制力序列
$u^*(0), u^*(1), ..., u^*(10)$ 那麼考慮從 $k=5, 6,...10$ 的子問題，則對應的控制力序列
\[
u^*(5), u^*(6),...u^*(10)
\]亦為此子問題的最佳解。

或者更淺白的說，假設今天要坐飛機到美國，最佳航程為

台灣 => 香港 =>美國

如果今天如果不從台灣開始，而是從香港開始(且香港已經在最佳路徑上)，則到美國的這條路徑仍維持最佳解。(香港=>美國)


Proof: Bellman's Principle of Optimality

用矛盾證法 (Proof by contradiciton)，
考慮一 子問題(subproblem) 為 從狀態 $x^*(l)$ 開始，且此狀態落在最佳解上，但 $u^*(k), \ k=l,l+1,...,N-1$ 並非 Optimal sequence。

既然上述不是 subproblem 的 Optimal sequence，則必定有其他人比此 $u^*$ 這組 sequence 可以得到更低的 cost，也就是說存在一組
\[
\hat{u}(l), \hat{u}(l+1),... \hat{u}(N-1)
\]使得 $J_l(\hat{u}) < J_l (u^*)$

現在我們定義 Optimal sequence: $\tilde{u}(k)$
\[\tilde u(k): = \left\{ \begin{array}{l}
{u^*}\left( k \right),\begin{array}{*{20}{c}}
{}
\end{array}k < l\\
\hat u\left( k \right),\begin{array}{*{20}{c}}
{}
\end{array}l \le k \le N - 1
\end{array} \right.
\] 那麼我們現在觀察 整個最佳化問題 (非子問題 ) 的 cost；亦即對 $k=0$ 開始 (而非 $k=l$)，則我們有
\[\begin{array}{l}
J\left( {\tilde u} \right) = \sum\limits_{k = 0}^{N - 1} {J\left( {x\left( k \right),u\left( k \right)} \right)}  + \Psi \left( {x\left( N \right)} \right)\\
 \Rightarrow J\left( {\tilde u} \right) = \underbrace {\sum\limits_{k = 0}^{l - 1} {J\left( {x\left( k \right),u\left( k \right)} \right)} }_{{J_0}\left( {{u^*}} \right)} + \underbrace {\sum\limits_{k = l}^{N - 1} {J\left( {x\left( k \right),u\left( k \right)} \right)} }_{{J_l}\left( {\hat u} \right)} + \Psi \left( {x\left( N \right)} \right)\\
 \Rightarrow J\left( {\tilde u} \right) < {J_0}\left( {{u^*}} \right) + {J_l}\left( {{u^*}} \right) + \Psi \left( {x\left( N \right)} \right)\\
 \Rightarrow J\left( {\tilde u} \right) < J\left( {{u^*}} \right)
\end{array}
\] 上述結果說明 $\tilde{u}$ 的序列為 Optimal sequence，但此結果與 Principle of Optimality 中原本假設的 最佳序列 $u^*(0), u^*(1),..., u^*(N-1)$ 矛盾。故得證。 $\square$

有了上述的 Principle of Optimality，我們便可以建構 Dynamic Programming Equaiton (DPE) (DPE 又稱為 Bellman equation)


Bellman Equation
首先考慮我們的 Subproblem：
由初始狀態 $x(l)$，定義 Optimal cost-to-go 記作 $I(x(l), N-l)$ (亦即考慮 Subproblem 由 $x(l)$ 開始 到 $x(N)$ 的 optimal cost )
\[I(x(l),N - l): = \mathop {\min }\limits_{\scriptstyle u(k) \in {\Omega _k},\atop
\scriptstyle k \ge l} {J_l}\left( u \right)
\]由 $J_l(u)$ 定義可知，${J_l}(u): = \sum\limits_{k = l}^{N - 1} J (x(k),u(k)) + \Psi (x(N))$，故
\[
\begin{array}{l}
I(x(l),N - l): = \mathop {\min }\limits_{\begin{array}{*{20}{c}}
{u(k) \in {\Omega _k},}\\
{k \ge l}
\end{array}} \left[ {\sum\limits_{k = l}^{N - 1} J (x(k),u(k)) + \Psi (x(N))} \right]\\
 \Rightarrow I(x(l),N - l) = \mathop {\min }\limits_{\begin{array}{*{20}{c}}
{u(k) \in {\Omega _k},}\\
{k \ge l}
\end{array}} \left[ \begin{array}{l}
J(x(l),u(l))\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + \sum\limits_{k = l + 1}^{N - 1} {J(x(k),u(k))}  + \Psi (x(N))
\end{array} \right]
\end{array}
\]由 Principle of Optimality 可知，上式可改寫為
\[
\small{\begin{array}{l}
 \Rightarrow I(x(l),N - l): = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ \begin{array}{l}
J(x(l),u(l))\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + \mathop {\min }\limits_{\begin{array}{*{20}{c}}
{u(k) \in {\Omega _k},}\\
{k > l}
\end{array}} \left\{ {\sum\limits_{k = l + 1}^{N - 1} {J(x(k),u(k))}  + \Psi (x(N))} \right\}
\end{array} \right]\\
 \Rightarrow I(x(l),N - l): = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {J(x(l),u(l)) + I\left( {x(l + 1),N - \left( {l + 1} \right)} \right)} \right]
\end{array}}
\]
上式稱為 Bellman Equation 或稱 Dynamic Programming Equation
\[
I(x(l), N-l) = \min_{u(l) \in \Omega_l} \{J(x(l), u(l)) + I(x(l+1), N-(l+1)) \}
\]

Example
考慮系統狀態方程表示如下：
\[x(k+1) = x(k) - u(k)
\]且 cost function 為
\[
J(u) = \displaystyle \sum_{k=0}^{N-1} (x(k+1)-u(k))^2 + x^2(k+1)
\]試求 Optimal $u^*(N-1), u^*(N-2),...$ 與其對應的 optimal cost to go

Solution
為簡便起見，這邊只求 $u(N-1)$ 與其對應的 optimal cost to go。

故首先由 $x(N-1)$ 開始，亦即 $l= N-1$，由 DPE 可知
\[\begin{array}{l}
I(x(l),N - l): = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {J(x(l),u(l)) + I\left( {x(l + 1),N - \left( {l + 1} \right)} \right)} \right]\\
 \Rightarrow I(x(N - 1),1) = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {J(x(N - 1),u(N - 1)) + I\left( {x(N),0} \right)} \right]\\
 \Rightarrow I(x(N - 1),1) = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {{{\left[ {x(N) - u(N - 1)} \right]}^2} + {x^2}\left( N \right) + {\rm{0}}} \right]\\
 \Rightarrow I(x(N - 1),1) = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {{{\left[ {x(N) - u(N - 1)} \right]}^2} + {x^2}\left( N \right)} \right]
\end{array}
\]現在再由系統狀態方程 $x\left( N \right) = x(N - 1) - u(N - 1) $ 代入上式可得
\[I(x(N - 1),1) = \mathop {\min }\limits_{u(N - 1)} \left[ {{{\left[ {x(N - 1) - 2u(N - 1)} \right]}^2} + {{\left[ {x(N - 1) - u(N - 1)} \right]}^2}} \right]
\] 由 FONC 求最佳解：
\[\begin{array}{l}
\frac{{\partial I(x(N - 1),1)}}{{\partial u(N - 1)}} = 0 \\
 \Rightarrow {u^*}(N - 1) = \frac{3}{5}x(N - 1)
\end{array}
\]其對應的Optimal cost-to-go
\[\begin{array}{l}
 \Rightarrow {\left. {I(x(N - 1),1)} \right|_{{u^*}}} = {\left[ {x(N - 1) - 2\frac{3}{5}x(N - 1)} \right]^2}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} + {\left[ {x(N - 1) - \frac{3}{5}x(N - 1)} \right]^2}\\
 \Rightarrow {\left. {I(x(N - 1),1)} \right|_{{u^*}}} = \underbrace {\frac{1}{5}}_{{K_{N - 1}}}{x^2}(N - 1)
\end{array}
\] 上式子中的 $K_{N-1}$ 被稱作 feedback-gain at $N-1$ stage。

接著我們計算 $x(N-2)$ 亦即 $l=N-2$ 的 Optimal cost-to-go:
\[\begin{array}{*{20}{l}}
{I(x(l),N - l): = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {J(x(l),u(l)) + I\left( {x(l + 1),N - \left( {l + 1} \right)} \right)} \right]}\\
{ \Rightarrow I(x(N - 2),2) = \mathop {\min }\limits_{u(N - 2) \in {\Omega _{N - 2}}} \left[ {J(x(N - 2),u(N - 2)) + I\left( {x(N - 1),1} \right)} \right]}\\
{ \Rightarrow I(x(N - 2),2) = \mathop {\min }\limits_{u(N - 2)} \left[ \begin{array}{l}
{\left( {x\left( {N - 1} \right) - u\left( {N - 2} \right)} \right)^2}\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + {x^2}\left( {N - 1} \right) + \frac{1}{5}{x^2}\left( {N - 1} \right)
\end{array} \right]}\\
{ \Rightarrow I(x(N - 2),2) = \mathop {\min }\limits_{u(N - 2)} \left[ \begin{array}{l}
{\left( {x\left( {N - 2} \right) - 2u\left( {N - 2} \right)} \right)^2}\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + {\left[ {x\left( {N - 2} \right) - u\left( {N - 2} \right)} \right]^2}\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + \frac{1}{5}{\left[ {x\left( {N - 2} \right) - u\left( {N - 2} \right)} \right]^2}
\end{array} \right]}
\end{array}
\] 由FONC: $\frac{\partial }{{\partial u(N - 2)}} = 0$，可知
\[\begin{array}{l}
\left\{ \begin{array}{l}
 - 4\left( {x\left( {N - 2} \right) - 2u\left( {N - 2} \right)} \right)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} - 2\left[ {x\left( {N - 2} \right) - u\left( {N - 2} \right)} \right] - \frac{2}{5}\left[ {x\left( {N - 2} \right) - u\left( {N - 2} \right)} \right]
\end{array} \right\} = 0\\
 \Rightarrow {u^*}\left( {N - 2} \right) = \frac{8}{{13}}x\left( {N - 2} \right)
\end{array}
\] 將上式代回 $I(x(N-2),2)$ 可得對應的 Optimal Cost to go 為
\[\begin{array}{l}
I(x(N - 2),2) = \left[ {\frac{9}{{{{13}^2}}}{x^2}\left( {N - 2} \right) + \frac{{25}}{{{{13}^2}}}{x^2}\left( {N - 2} \right) + \frac{5}{{{{13}^2}}}{x^2}\left( {N - 2} \right)} \right]\\
 \Rightarrow I(x(N - 2),2) = \frac{{39}}{{{{13}^2}}}{x^2}\left( {N - 2} \right)
\end{array}
\] $\square$

延伸閱讀：
[動態規劃] 淺談 離散時間動態規劃 (1) - Bellman equation in Infinite Horzion

[最佳化] 淺談 Steepest Descent Method (1) - Optimal step size

延續上篇文章 [最佳化] 淺談 Steepest Descent Method (0) -Why Steepest !?，這次我們要介紹 Steepest Descent Method with Optimal Step size

修訂後的Steepest Descent Algorithm 需要甚麼呢?

1. 初始條件 $u^0$
2. 最大跌代步長上限(Maximum fixed step size): $H$
3. Steepest Descent with Optimal Step size的跌代架構(iterative scheme) \[u^{k+1} = u^k - h_k \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||} \ \ \ \ (*)\]
4. 演算法停止判別機制(stopping criterion) : EX: \[ ||\nabla J(u^k)|| < \varepsilon\]

那麼問題變成 $h_k$ 該怎麼求?

首先我們考慮第 $k$次 跌代，手上有 $u^k$，則我們可以定義

\[
\tilde J(h) := J(u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||})
\]接著我們做 Line search 找出一個最佳的 $h \in [0,H] $ ( 亦即 $\min \tilde J(h)$) 把此 $h$ 稱做 $h_k $，也就是說

\[
\tilde J(h_k) = \displaystyle \min_{h \in [0, H]} \tilde J(h)
\]做Line search之後得到的 $h_k$ 再把他放回 $(*)$ 即可!!

\[
u^{k+1} = u^k - h_k \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||} \ \ \ \ (*)
\]上式即稱為 Steepest Descent with Optimal Step size (此Optimal step 由Line search 對 $ \min J(u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||})$ 求得)

對於Steepest Descent Algorithm而言，我們有 現在的跌代步的梯度 與下一個跌代步的梯度互為垂直；亦即
\[
\left ( \nabla J(u^k) \right )^T \cdot \nabla J(u^{k+1}) =0
\]現在如果我們考慮更一般的情況，

===============================
Theorem: (Optimal Descent Condition)
考慮 $v \in \mathbb{R}^n$ 為某一個方向 (不必是梯度)，且假設 $h_k$ 把 $\tilde J(u^k + h \cdot v)$最小化，且我們的跌代式為
\[
u^{k+1} = u^k + h_k \cdot v
\]則我們有 $v^T \cdot \nabla J(u^{k+1}) =0$，我們稱此條件為 Optimal Descent Conditon。
===============================

Proof:
我們欲證  $v^T \cdot \nabla J(u^{k+1}) =0$，

故由  $h_k$ 把 $\tilde J(u^k + h \cdot v)$最小化 的假設，我們已知一階必要條件成立，故可利用一階必要條件FONC
\[\frac{{\partial \tilde J({u^k} + h \cdot v)}}{{\partial h}} = 0
\]為了方便起見，現在令 $z: = {u^k} + h \cdot v$，則上式可推得
\[\begin{array}{l}
\frac{{d\tilde J(z)}}{{dh}} = \frac{{\partial \tilde J(z)}}{{\partial {z_1}}}\frac{{\partial {z_1}}}{{\partial h}} + \frac{{\partial \tilde J(z)}}{{\partial {z_2}}}\frac{{\partial {z_2}}}{{\partial h}}... + \frac{{\partial \tilde J(z)}}{{\partial {z_n}}}\frac{{\partial {z_n}}}{{\partial h}} = 0\\
 \Rightarrow \frac{{d\tilde J(z)}}{{dh}} = \frac{{\partial \tilde J(z)}}{{\partial {z_1}}}{v_1} + \frac{{\partial \tilde J(z)}}{{\partial {z_2}}}{v_2}... + \frac{{\partial \tilde J(z)}}{{\partial {z_n}}}{v_n} = 0\\
 \Rightarrow \frac{{d\tilde J(z)}}{{dh}} = \left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{\frac{{\partial \tilde J(z)}}{{\partial {z_1}}}}\\
{\frac{{\partial \tilde J(z)}}{{\partial {z_2}}}}\\
 \vdots \\
{\frac{{\partial \tilde J(z)}}{{\partial {z_n}}}}
\end{array}} \right] = 0\\
 \Rightarrow \frac{{d\tilde J(z)}}{{dh}} = {v^T}\nabla \tilde J(z) = {v^T}\nabla \tilde J({u^k} + h \cdot v) = {v^T}\nabla \tilde J({u^{k + 1}}) = 0
\end{array}
\]最後一個等式成立是由於 $h$ 最小化 $\tilde J(u^k + h \cdot v)$，故稱此$h=h_k$，又由跌代式的假設 $u^{k+1} = u^k + h_k \cdot v$。 $\square$


那麼現在我們來看看如果目標函數是標準二次的情況

考慮如下標準二次函數
\[
J(u) = u^T A u + b^T u + c, \ A=A^T, \ A \succ 0
\]注意到上述二次函數可以直接用 一階必要條件FONC ( $\nabla J(u^k) =0$) 與 二階充分條件SOSC ($\nabla^2 J(u^k) \succ 0$) 直接求解，可得最佳解為 $u^* = \frac{1}{2} A^{-1}b$

那麼如果我們現在採用 Steepest Descent Algorithm with Optimal Step size $h_k$ ，我們想要知道選怎樣的 $h_k$ 可以得到同樣的最佳解呢?

故首先給定初始條件 $u^0$, 且給定足夠大的步長上限 $H$，

接著我們寫下 Line Search需要的式子
\[
\tilde J (h) := J(u^k  - h \cdot \nabla J(u^k)) \ \ \ \ (*)
\] ，目標是要找出 $h =?$

首先觀察 $(*)$，我們可以先計算上式的梯度部分，由 FONC 可知梯度為
\[
\nabla J(u^k) = 2 A u^k + b
\]故將其代入 $(*)$ 可得
\[
\tilde J(h): = J\left( {{u^k} - h\left( {2A{u^k} + b} \right)} \right)
\]又因為
\[
J(u) = u^T A u + b^T u + c
\]故可推得
\[\begin{array}{l}
 \Rightarrow \tilde J(h) = {\left( {{u^k} - h\left( {2A{u^k} + b} \right)} \right)^T}A\left( {{u^k} - h\left( {2A{u^k} + b} \right)} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} + {b^T}\left( {{u^k} - h\left( {2A{u^k} + b} \right)} \right) + c
\end{array}
\]由於 $h$ 為最小化 $\tilde J(h)$ 故由FONC對 $h$ 可知 $\frac{d \tilde J(h)}{dh} =0$ 亦即
\[\begin{array}{l}
 \Rightarrow \frac{{d\tilde J(h)}}{{dh}} = 0\\
 \Rightarrow  - {u^k}^TA\left( {2A{u^k} + b} \right) - {\left( {2A{u^k} + b} \right)^T}A{u^k}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} + 2h{\left( {2A{u^k} + b} \right)^T}A\left( {2A{u^k} + b} \right) - {b^T}\left( {2A{u^k} + b} \right) = 0\\
 \Rightarrow {h_k}: = h = \frac{1}{2}\frac{{{{\left( {2A{u^k} + b} \right)}^T}\left( {2A{u^k} + b} \right)}}{{{{\left( {2A{u^k} + b} \right)}^T}A\left( {2A{u^k} + b} \right)}}
\end{array}
\]
Comments:
1. 注意到上式中分母為 ${{{\left( {2A{u^k} + b} \right)}^T}A\left( {2A{u^k} + b} \right)}$ 為 $1 \times 1$ 此時分母不再是矩陣或者向量，故可以直接執行除法。且由於我們的假設 $A$ 矩陣為正定矩陣，亦即 $x^T A x >0, \forall x \neq 0$，仔細觀察上式分母，若令 $x:={\left( {2A{u^k} + b} \right)}$，我們確實得到
\[
{{{\left( {2A{u^k} + b} \right)}^T}A\left( {2A{u^k} + b} \right)} = x^T A x >0
\]

[最佳化] 淺談 Steepest Descent Method (0) -Why Steepest !?

這次要介紹的是最陡坡度法(Steepest Descent Method)，又稱 Gradient descent method：

想法：透過負梯度 (negative gradient) 作為最陡坡度，逐步找到 (局部)最小值 (最佳解 $u^*$)

這個演算法需要甚麼呢?

1. 初始條件 $u^0$
2. 固定的跌代步長(fixed step size): $h$
3. Steepest Descent 的跌代架構(iterative scheme) \[u^{k+1} = u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||}\]
4. 演算法停止判別機制(stopping criterion) : EX: 給定誤差 $\varepsilon>0$，檢驗 \[ ||\nabla J(u^k)|| < \varepsilon\]

那麼現在我們來解決一個問題：

為什麼此法被稱作 "最陡" 坡度? 
也就是說 為什麼Iterative scheme 中的方向 $ \nabla J(u^k)$ 被稱做是最陡(Steepest)方向??

考慮目標函數 $J: \mathbb{R}^n \rightarrow \mathbb{R}$，其在某點 $u^0 \in \mathbb{R}$ 與方向$v$ 的方向導數(Directional derivative at point $u^0$ in direction $v$)定義如下：

\[
{\left. {\frac{{\partial J\left( u \right)}}{{\partial v}}} \right|_{u = {u^0}}}: = {\left[ {\nabla J({u^0})} \right]^T} \cdot \frac{v}{{\left\| v \right\|}}
\]由Cauchy-Schwarz inequality $\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$，可推得上式如下：
\[
\left| {{{\left[ {\nabla J({u^0})} \right]}^T} \cdot \frac{v}{{\left\| v \right\|}}} \right| \le \left\| {\nabla J({u^0})} \right\|\frac{{\left\| v \right\|}}{{\left\| v \right\|}}
\]現在如果我們把方向 $v$ 選成梯度方向，亦即

\[
v = \nabla J(u^0)
\]則可發現上述不等式變成
\[\begin{array}{l}
 \Rightarrow \left| {{{\left[ {\nabla J({u^0})} \right]}^T} \cdot \frac{{\nabla J({u^0})}}{{\left\| {\nabla J({u^0})} \right\|}}} \right| \le \left\| {\nabla J({u^0})} \right\|\\
 \Rightarrow \frac{{{{\left\| {\nabla J({u^0})} \right\|}^2}}}{{\left\| {\nabla J({u^0})} \right\|}} \le \left\| {\nabla J({u^0})} \right\|\\
 \Rightarrow \left\| {\nabla J({u^0})} \right\| = \left\| {\nabla J({u^0})} \right\|
\end{array}
\]故可知當我們選 $v = \nabla J(u^0) $ Cauchy-Schwarz inequality 的 "等" 式成立，故 $\nabla J(u^0) $ 為使方向導數最大的值! 亦即 最陡方向(Steepest)!

至於為什麼我們說Steepest Descent (最陡坡度下降)，是因為注意到Steepest Descent 演算法中跌代式子

\[u^{k+1} = u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||}
\] 的方向為負，亦即 $- \nabla J(u^k)$ !!，故我們是朝著最陡的方向往下逐步得到最佳解(最小值) $u^*$

現在我們給個例子：

Example
考慮如下目標函數
\[
J(u) = {\left( {11 - {u_1} - {u_2}} \right)^2} + {\left( {1 + 10{u_2} + {u_1} - {u_1}{u_2}} \right)^2}
\] 1. 試證上述目標函數最佳解為 $[13, 4]^T$
2. 繪製其 $0 \le u_1 \le 20$ 與 $ 0 \le u_2 \le 15$ 的範圍
3. 給定初始值 $u^0 = [8, 12]^T $使用上述 Steepest Descent algorithm 與不同的固定步長 $h=0.01, 1.0$看看發生甚麼事情

Solution:
1. 透過一階必要條件(FONC) 與 二階充分條件(SOSC)即可求得最佳解 $u^* = [13,
4]^T$。在此不贅述。

2. 透過MATLAB contour 指令可以繪製目標函數的等高線圖如下

3. 考慮$u^0 = [8, 12]^T$ ，並考慮 $h=0.01$的情況，透過MATLAB實現上述Steepest Descent Algorithm並限制停止判別為跌代步驟不超過兩千步 $k_{max} := 2,000$。
在約 $k=1000$ 步之後，可收斂到 $u = [13.01, 3.993]$。如下圖所示： (點圖放大)；

若現在考慮 $h=1.0$ 則Steepest Descent 展示了Zig-Zag的現象，最終落在 $u=[12.6, 3.601] to [13.31, 4.08]$之間，且跌代步如下圖所示 (點圖放大)

注意到上述例子中，對於較大的固定步e.g., $h=1.0$ ，Steepest Descent 表現出來回震盪的情況，對於較小的固定步 e.g., $h=0.01$，Steepest Descent 收斂緩慢 (超過一千步才收斂)。

Summary: 
Steepest Descent Algorithm 雖然想法很直覺，但事實上本質有兩個重大的缺點：
1. 注意到Steepest Descent的跌代式子中除了要計算梯度之後，仍需要給定固定步長 $h$，如果固定步長 $h$ 太大!，則會演算法產生衝過頭的情形。也就是說假設 $h=100$ (100步長單位) 當我可能今天只需要1步就到達最佳解，但Steepest Descent Method卻被迫每次都要走步長單位為 $100$ ，則永遠只能在最佳解附近震盪永遠到不了最佳解，

2. 如果固定步長 $h$ 太小，則雖然在某種程度上解決了震盪問題，但此時收斂速度會變得異常緩慢。

如何解決上述的問題!??
我們需要徹底地拔除固定步長的限制，此法稱做 Steepest Descent with Optimal Step Algorithm。
亦即我們將原本的Steepest Descent Algorithm的跌代式中的固定步長 $h$改成動態步長 $h_k$
\[
u^{k+1} = u^k - h_k \frac{\nabla J(u^k)}{|| \nabla J(u^k)||}
\]至於此 $h_k$該怎麼選? 有興趣的讀者可以參考下篇
[最佳化] 淺談 Steepest Descent Method (1) - Optimal step size

[Seminar] 專利與發明的分享

今天碰巧在seminar聽了一場關於專利與發明的演講
演講者是環隆電氣的專利工程主管:

會中提到了專利與發明其實無所不在

但令我注意的是一個與物理有關的小故事
以下是我用片段的回憶結合 網路的完整版故事 修改而得:

某一年在美國的某所大學，有位教授在物理學的期末考上提出了一個問題
「試問如何利用氣壓計決定一棟大樓的高度？」

=>How to measure the attitude of a High-rise by a barometer?
(這答案其實顯而易見:各位若回憶國高中時期的理化課，應能知道當高度越高，壓力越低，故可由氣壓計來測得大樓之高度)

有一個學生的回答是：
「帶著氣壓計到大樓頂，氣壓計上綁著一條長繩，然後緩緩垂下，等氣壓計觸及地面時，這時繩子的長度即是大樓的高度。」

教授給了這位學生0分，但這位學生卻認為自己的答案完全正確，應該要得滿分才對。兩人爭論不休，最後這位教授請了該校校長來做仲裁者。這位被委任仲裁的校長是當初鼎鼎大名的核物理學之父歐尼斯特‧拉瑟福(Ernest Rutherford, 1908年諾貝獎得主)。

他先了解該名學生的情況以後與該教授討論。兩人決定給那名學生一個重考的機會。學生也同意了拉瑟福校長的看法。於是便舉行第二次的考試。

有趣的是補考的條件，拉瑟福校長要求學生再次作答的答案一定要包含物理知識，並且只給他六分鐘作答。

過了五分鐘，答案卷上還是一片空白，拉瑟福校長問這位學生是否要放棄?

那位學生卻說：「我腦子裡的答案有很多個，只是在想哪一個答案最好。」

想了又想，這位學生終於在最後一分鐘交了卷。

他這次的答案是：
「帶著氣壓計到大樓頂，接著讓氣壓計自由落下，同時用碼錶測量氣壓計掉到地面所花的時間，大樓高度等於二分之一乘以重力加速度乘以時間的平方(S=1/2*g*t^2)。」
答案完全正確，而且也用到物理知識，教授無奈的只好給他99分。 

仲裁圓滿結束後，大師好奇地問這位學生還有什麼答案。結果，那位學生又一口氣說出了五個答案：

1. 晴天時，先測量氣壓計長度，還有它陰影的長度、大樓陰影的長度，然後利用比例就可算出大樓的高度。

2. 帶著氣壓計爬上樓梯，沿著牆壁以氣壓計的高度為單位做記號，一直標記到頂樓，看有幾個標記，再乘以氣壓計高度，就是大樓高度。

4. 在氣壓計上綁著長繩，垂到接近地面，像鐘擺般搖晃，從擺差時間也可算出大樓高度。

5. 最後一個，最省事的方法，直接去敲大樓管理員的門，對他說有一個精美的氣壓計，只要管理員告訴你大樓的高度，就把氣壓計送給他。 

拉瑟福校長聽了搖頭苦笑，問說：「難道你不知道利用地面與樓頂大氣壓力差來計算大樓高度這種正規的方法嗎？」
學生回答說：「當然知道！但這些都是我動腦筋思考，自己想出來的方法啊！」 

這名學生的名字叫做尼爾斯‧波爾(Niels Bohr)，他後來成為舉世公認的物理奇葩，一九二二年諾貝爾物理獎得主，原子模型的締造者以及量子論的創建者。 

(from Wikipedia)

故事到此結束。

波爾所想出的其他方法，也許都不如那個正規的現成答案漂亮而又便捷，但那些卻都是他自己動腦筋想出來的。

"不願意真正用心思考" 的確是多數人的通病，遇到問題時，總是先去找有什麼現成的答案可用，有什麼公式可套，但套公式並不等於在思考。這些現成的答案、漂亮的公式，其實只是我們用來妝點門面的框框，它們阻礙了我們真正用心去思考。 

每一個想要發揮創意的人，也應該以它來提醒自己。 
專利也就是創意發明者的延伸與保護

延伸閱讀
Father of Physics: Ernest Rutherford
The Genius student: Niels Bohr

[轉錄] 學問之趣味-梁啟超

學問之趣味 by 梁啟超

我是個主張趣味主義的人，倘若用化學化分「梁啟超」這件東西，把裡頭所含一種原素名為「趣味」的抽出來，只怕所剩下的僅有個零了。我以為凡人必須常常生活於趣味之中，生活才有價值；若哭喪著臉挨過幾十年，那麼，生活便成沙漠，要他何用？

凡屬趣味，我一概都承認他是好的。但怎麼才算趣味？不能不下一個註腳。我說：「凡一件事做下去不會生出和趣味相反的結果的，這件事便可以為趣味的主體。」賭錢有趣味嗎？輸了，怎麼樣？吃酒，有趣味嗎？病了，怎麼樣？做官，有趣味嗎？沒有官做的時候，怎麼樣……諸如此類，雖然在短時間內像有趣味，結果會鬧到俗語說的「沒趣一齊來」，所以我們不能承認他是趣味。

凡趣味的性質，總是以趣味始，以趣味終。所以能為趣味之主體者，莫如下面的幾項：
一、勞作，
二、遊戲，
三、藝術，
四、學問。
諸君聽我這段話，切勿誤會：以為我用道德觀念來選擇趣味。我不問德不德，只問趣不趣。我並不是因為賭錢不道德才排斥賭錢，因為賭錢的本質會鬧到沒趣，鬧到沒趣便破壞了我的趣味主義，所以排斥賭錢。我並不是因為學問是道德才提倡學問，因為學問的本質，能夠以趣味始，以趣味終，最合於我的趣味主義條件，所以提倡學問。

諸君要嘗學問的趣味嗎？據我所經歷過的，有下列幾條路應走：

第一，無所為。
趣味主義最重要的條件是「無所為而為」。凡有所為而為的事，都是以另一件事為目的而以這一件事為手段。為達目的起見，勉強用手段；目的達到時，手段便拋卻。例如學生為畢業證書而做學問，著作家為版權而做學問，這種做法，便是以學問為手段，便是有所為。有所為雖然有時也可以引起趣味的一種方法，但到趣味真發生時，必定要和「所為者」脫離關係。你問我「為什麼做學問？」我便答道：「不為什麼。」再問，我便答道：「為學問而學問。」或者答道：「為我的趣味。」諸君切勿以為我這些話是故弄玄虛，人類合理的生活本來如此。小孩子為什麼遊戲？為遊戲而遊戲。人為什麼生活？為生活而生活。為遊戲而遊戲，遊戲便有趣；為體操分數而遊戲，遊戲便無趣。

第二，不息。
「鴉片煙怎樣會上癮？」「天天吃。」「上癮」這兩個字，和「天天」這兩個字是離不開的。凡人類的本能，只要哪部分擱久了不用，它便會麻木，會生銹。十年不跑路，兩條腿一定會廢了。每天跑一點鐘，跑上幾個月，一天不跑時，腿便發癢。人類為理性的動物，「學問欲」原是固有本能之一種，只怕你出了學校便和學問告辭，把所有經管學問的器官一齊打落冷宮，把學問的胃口弄壞了，便山珍海味擺在面前也不願意動筷了。

第三，深入的研究。
趣味總是慢慢地來，越引越多，像倒吃甘蔗，越往下才越得好處。假如你雖然每天定有一點鐘做學問，但不過拿來消遣消遣，不帶有研究精神，趣味便引不起來。

第四，找朋友。
趣味比方電，越摩擦越出。前兩面所說，是靠我本身和學問本身相摩擦，但仍恐怕我本身有時會停擺，發電力便弱了。所以常常要仰賴別人幫助。

我說的這四件事，雖然像是老生常談，但恐怕大多數人都不曾這樣做。唉！世上人多麼可憐啊！有這種不假外求，不會蝕本，不會出毛病的趣味世界，竟沒有幾個人肯來享受！古書說的故事「野人獻曝」，我是嘗冬天曬太陽滋味嘗得舒服透了，不忍一人獨享，特地恭恭敬敬的告訴諸君，諸君或者會欣然採納吧？但我還有一句話：太陽雖好，總要諸君親自去曬，旁人卻替你曬不來。(註：原文有刪節)

來源： 南方都市報

[微積分] Taylor Expansion and Taylor Series

泰勒展開 (Taylor Expansion) 的目的：試圖將 (足夠平滑) 函數 透過 多項式近似
 NOTE: 在此我們說足夠平滑，意思是指 導數存在。

Comment:
讀者可能學過所謂的 Fourier Series ，其基本概念是試圖將函數透過 "三角函數" 近似。



Taylor Expansion (or Taylor Polynomial)
考慮某函數一階導數存在，則我們可以透過 一階多項式來近似 $f(x)$ 如下：
$$f(x) \approx a + bx$$ 則我們現在可觀察到在 $x =0$ 處， $f(0) = a$ 且其一階導數 $f'(0) = b$ 故事實上可寫
\[
f(x) \approx f(0) + f'(0) x
\]上式稱為 $f(x)$ 的 $1$ 階 Taylor Expansion

再者若此函數二階導數存在，且打算將其表為二階多項式如下： $$f(x) \approx a + bx + c x^2$$ 則同理，我們可觀察在 $x =0$ 處， $f(0) = a$ 且其一階導數 $f'(0) = b$ ， 二階導數 $f''(0) = 2c$故事實上可寫
\[\begin{array}{l}
f(x) \approx a + bx + c{x^2}\\
 \Rightarrow f(x) \approx f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{2}{x^2}
\end{array}
\]上式稱為 $f(x)$ 的 $2$ 階 Taylor Expansion

接著我們再重複做一次上述近似，再者若此函數 三階導數存在 ，我們可將其表為三階多項式形式如下： $$f(x) \approx a + bx + c x^2 + d x^3
$$同理，觀察在 $x =0$ 處， $f(0) = a$ 且其一階導數 $f'(0) = b$ ， 二階導數 $f''(0) = 2c$；三階導數 $f'''(0) = 3 \cdot 2 d$ 故事實上可寫
\[\begin{array}{l}
f(x) \approx a + bx + c{x^2} + d{x^3}\\
 \Rightarrow f(x) \approx f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{2}{x^2} + \frac{{f'''\left( 0 \right)}}{{3 \cdot 2}}{x^3}
\end{array}\]上式稱為 $f(x)$ 的 $3$ 階 Taylor Expansion

從上述分析，讀者不難發現若函數 $f(x)$ 的 $n$ 階導數存在，則 $n$ 階 Taylor Expansion 可表為下式
\[f(x) \approx f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{{2!}}{x^2} + \frac{{f'''\left( 0 \right)}}{{3!}}{x^3} + ... + \frac{{{f^{\left( n \right)}}\left( 0 \right)}}{{n!}}{x^n}\]

Example 1: 
考慮 $f(x) := e^x$， 試求 其 $3$ 階 Taylor 展開式。

Solution
$e^x$ 為平滑函數，任意階導數存在 且任意階導數相等，故前面三階導數
$$f(x) = f'(x) = f''(x) = f'''(x) = e^x
$$ 現在帶入 $x=0$ 可得 $f(0) = f'(0) = f''(0) = f'''(0) = 1$ 故其  $3$ 階 Taylor 展開式 為
\[\begin{array}{l}
f(x) \approx f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{{2!}}{x^2} + \frac{{f''\left( 0 \right)}}{{3!}}{x^3}\\
 \Rightarrow {e^x} \approx 1 + 1x + \frac{1}{{2!}}{x^2} + \frac{1}{{3!}}{x^3}
\end{array}\]亦即 我們用 $3$ 階多項式來 "近似" $e^x$。$\square$


Taylor Expansion 的誤差
那麼有了 Taylor 展開 近似 原函數之後，我們必然會想問 此展開 與 原函數差多少? 比如說考慮將 $f(x)$ 做 $n$ 階 Taylor 展開，則我們可寫
\[f(x) \approx f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{{2!}}{x^2} + \frac{{f'''\left( 0 \right)}}{{3!}}{x^3} + ... + \frac{{{f^{\left( n \right)}}\left( 0 \right)}}{{n!}}{x^n}\]現在我們引入  $n$ 階誤差項 稱作 $R_n(x) $， 則
 \[\begin{array}{l}
f(x) \approx f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{{2!}}{x^2} + ... + \frac{{{f^{\left( n \right)}}\left( 0 \right)}}{{n!}}{x^n}\\
 \Rightarrow f(x) = f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{{2!}}{x^2} + ... + \frac{{{f^{\left( n \right)}}\left( 0 \right)}}{{n!}}{x^n} + {R_n}\left( x \right)
\end{array}\]那麼誤差項 $R_n(x)$ 該如何估計? 我們可透過以下定理回答此問題

===============
Theorem: Taylor Theorem
考慮 $x \in [a,b]$ 且 $(0 \in [a,b])$，且 對函數 $f(x)$ 的 $n$ 階泰勒展開為
\[f(x) = f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{{2!}}{x^2} + ... + \frac{{{f^{\left( n \right)}}\left( 0 \right)}}{{n!}}{x^n} + {R_n}\left( x \right)\] 則存在某點 $c \in [a,b]$ 使得誤差項 \[
R_n(x) = \frac{f^{(n+1)}(c)}{(n+1)!} x^{(n+1)}
\]===============

Proof: omitted.

FACT: 由上述定理可知，誤差項有上界

\[
|R_n(x)| \le \frac{M |x|^{n+1}}{(n+1)!}
\]其中 $M:= \max\{|f^{(n+1)}(c)|\}, \forall c\in [a,b]$


Example
利用 $e^x$ 的三階泰勒展開 求 $e^{1/2}$ 的近似值 並估計誤差。

Solution
利用前例可知  $e^x$ 的三階泰勒展開 為
\[{{e^x} \approx 1 + 1x + \frac{1}{{2!}}{x^2} + \frac{1}{{3!}}{x^3}}\]我們可帶入 $x=1/2$ 即可求得所需的泰勒多項式
\[1 + 1\left( {\frac{1}{2}} \right) + \frac{1}{{2!}}{\left( {\frac{1}{2}} \right)^2} + \frac{1}{{3!}}{\left( {\frac{1}{2}} \right)^3}\] 此時泰勒多項式 與 $e^{1/2}$ 之間的 誤差項估計如下
\[\begin{array}{l}
|{R_n}(x)| \le \frac{{M|x{|^{n + 1}}}}{{(n + 1)!}}\\
 \Rightarrow |{R_3}(x)| \le \frac{{M|x{|^4}}}{{(4)!}}
\end{array}\]其中 $M:= \max\{|f^{(n+1)}(c)\}, \forall c\in [a,b]$ ，由於我們關心的是 $e^{1/2}$ 的近似值 與其誤差，故若取 $a=0, b=1/2$ 則 \[M: = \max \{ |{e^c}|\} ,\forall c \in [0,1/2] \Rightarrow M = {e^{1/2}}\] 將此 $M$ 帶回我們的誤差項可得
\[|{R_3}(x)| \le \frac{{{e^{1/2}}|1/2{|^4}}}{{(4)!}}\]注意到 上式需要 計算 $e^{1/2}$ 但我們正需要估計此數值，故需要再度放寬上界
\[|{R_3}(x)| \le \frac{{{e^{1/2}}|1/2{|^4}}}{{(4)!}} \le \frac{{\overbrace {{e^1}}^{ \approx 2.72}|1/2{|^4}}}{{(4)!}} \le \frac{{3 \cdot |1/2{|^4}}}{{(4)!}} \approx 0.008\]

Example
令 $x \in [-1,1]$，試求對 $e^x$ 而言，需要幾階 泰勒多項式 才可使其與原函數 $e^x$ 誤差小於 $0.005 ?$

Solution
回憶誤差項有上界為
\[|{R_n}(x)| \le \frac{M}{{\left( {n + 1} \right)!}}|x{|^{n + 1}}\]其中 $M:= \max\{|e^c|\}, \forall c\in [-1,1]$ 故 $M= e^1$ 亦即，
\[|{R_n}(x)| \le \frac{{{e^1}}}{{\left( {n + 1} \right)!}}|1{|^{n + 1}} = \frac{e}{{\left( {n + 1} \right)!}} \le \frac{3}{{\left( {n + 1} \right)!}}\]現在我們需要 其 小於 $0.005$ 故若取 $n=5$ 則
\[\frac{3}{{\left( {n + 1} \right)!}} \approx 0.004 \le 0.005\]


Taylor Series
那麼如果考慮如果函數  $f(x)$ 的 無窮 階導數存在 (亦即此函數為 平滑(smooth) 函數) 則我們可將在原點展開的 Taylor Expansion 寫成 無窮級數的形式 (若此級數收斂)，我們稱之為 Taylor Series ：
\[\begin{array}{l}
f(x) = f\left( 0 \right) + f'\left( 0 \right)x + \frac{{f''\left( 0 \right)}}{{2!}}{x^2} + ... + \frac{{{f^{\left( n \right)}}\left( 0 \right)}}{{n!}}{x^2} + ...\\
 \Rightarrow f(x) =\sum\limits_{k = 0}^\infty  {\frac{{{f^{\left( k \right)}}\left( 0 \right)}}{{k!}}{x^k}}
\end{array}
\] Comment:
若函數為平滑函數 (e.g., $e^x, \sin (x), \cos (x),...$)，且 Taylor Series 收斂，則 Taylor Series 收斂到原函數，不再是近似 (在此證明省略)


Example 2:
考慮 $f(x) := e^x$， 試求 其 Taylor Series。

Solution
$e^x$ 為平滑函數，任意階導數存在 且任意階導數相等；我們可將此 $e^x$ 用 Taylor Series 故對若取 $n \in \mathbb{N}$， $f^{(n)}(x) = e^x$，且在 $x=0$ 處 可得 $f^{(n)}(0)= 1$ 故其  Taylor Series 為
\[{f(x) = \sum\limits_{k = 0}^\infty  {\frac{{{f^{\left( k \right)}}\left( 0 \right)}}{{k!}}{x^k} \Rightarrow {e^x} = \sum\limits_{k = 0}^\infty  {\frac{1}{{k!}}{x^k}} } }\] (讀者可自行證明此Taylor Series 收斂，故等號確實成立。 )

Exercise:
(a) 試求 $f(x) = \sin (x)$ 的 Taylor Series。 ANS: $\sin \left( x \right) = \sum\limits_{k = 0}^\infty  {{{\left( { - 1} \right)}^k}\frac{{{x^{2k + 1}}}}{{\left( {2k + 1} \right)!}}} $
(b) 試求 $f(x) = \cos(x)$ 的 Taylor Series。 ANS: $\cos \left( x \right) = \sum\limits_{k = 0}^\infty  {{{\left( { - 1} \right)}^k}\frac{{{x^{2k}}}}{{\left( {2k} \right)!}}} $

(c) 令 $|x| <1$，試求 $f(x) = 1/(1-x)$ 的 Taylor Series。 ANS: $\frac{1}{{1 - x}} = \sum\limits_{k = 0}^\infty  {{x^k}} $

[機率論] Exponential Random Variables

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


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

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

\end{array}\]

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

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


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

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