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