[機率論] 三角陣列

在機率論中，我們常看到的是單一指標序列：$ \{X_n\}_{n=1}^\infty := (X_1, X_2, \dots,) $ 比如說 iid 序列或者至少定義在同一個機率空間 $(\Omega, \mathcal{F}, P)$上的序列。 此時只有一個指標 $n$，而 $X_n$ 指涉的是該序列第 $n$ 個隨機變數。

標準的大數法則(Law of Large Numbers, LLN) 與經典形式的中央極限定理(Central Limit Theorem, CLT) 常處理的就是這種單一指標序列 $X_1, X_2, \ldots$，其中每個 $X_i$ 的分佈固定。但許多重要情形下，隨著樣本數增加，個別隨機變數的分布可能隨 $n$ 改變，隨機變數序列的聯合分佈本身也會有所變化。三角陣列(triangular array)提供了處理這類問題的框架。

現在我們考慮以下情況，固定整數 $n$，考慮第 $n$ 列的 $n$ 個 Bernoulli 隨機變數： $$ X_{n,1},\dots, X_{n,n} $$ 但是如果我們允許 $n$ 改變，也就是每個 $n$ 都有一整列新的隨機變數序列，則整個聯合分佈也可能跟著改變。比如說 $n=10$，我們有 $$X_{10,1}, X_{10,2}, \dots, X_{10,10}$$ 共 10個 Bernoulli 隨機變數，他們具有一個聯合分佈 (joint distribution)。但是若 $n = 100$，我們有 $$X_{100,1}, X_{100,2}, \dots, X_{100,100}$$ 共 100 個 Bernoulli 隨機變數，其聯合分佈一般不同於前一組 $X_{10,1}, ,X_{10,2}, \dots, X_{10,10}$ 的 joint distribution。這時，如果我們指涉的對象為「第一個 Bernoulli 變數」在 $n=10$ 是 $X_{10,1}$ 與 $n=100$ 是 $X_{100,1}$ 是不同物件，此時這種結構無法再用單一序列來描述，為此我們可以引入三角陣列 (triangular array)

Definition (Triangular Array): 一個三角陣列(triangular array)是指一族以兩個指標標記的隨機變數 $\{X_{n,i}\}_{n\geq 1, 1\leq i \leq n}$，其中第 $n$ 列包含 $X_{n,1}, \dots, X_{n,n}$

Remark. 若將其排列起來可得 $$ \begin{matrix} n=1: & X_{1,1} \\ n=2: &X_{2,1} &   X_{2,2} \\ n=3: &X_{3,1} & X_{3,2} & X_{3,3} \\ \vdots & \vdots & \vdots & \ddots \end{matrix} $$ 第 $n$ 列有 $n$ 個變數，因此看起來是「三角形」，這只是視覺上的名字。注意到上述定義不要求不同 $n$ 列之間有任何獨立性或相容性，通常只在每一列之內做假設。

三角陣列在許多機率論有重要結果，比如以下的 Lindeberg-Feller 中央極限定理：

Lindeberg-Feller CLT: 對每個 $n \ge 1$，令 $\{X_{n,i}\}_{i=1}^{n}$ 為一族隨機變數，其整體族 $\{X_{n,i}\}_{n \ge 1, \, 1 \le i \le n}$ 構成一個三角陣列，對每個 $n$ 而言，$X_{n,1}, \dots, X_{n,n}$ 相互獨立，且滿足 $\mathbb{E}[X_{n,i}] = 0$。定義 $$ S_n := \sum_{i=1}^{n} X_{n,i} $$ 且 $$ \sigma_n^2 := \text{var}(S_n) > 0 $$ 若 Lindeberg 條件成立，亦即對 $\varepsilon > 0$，我們有 $$ \lim_{n \to \infty} \frac{1}{\sigma_n^2} \sum_{i=1}^{n} \mathbb{E}[X_{n,i}^2 \mathbf{1}_{|X_{n,i}| > \varepsilon \sigma_n}] = 0 $$ 則 $\frac{S_n}{\sigma_n} \xrightarrow{D} \mathcal{N}(0,1)$。

上述 Lindeberg-Feller CLT 推廣經典 CLT：

Proof: 取 $X_{n,i} := \frac{Y_i - \mu}{\sqrt{n}}$ 其中 $Y_i$ 為 iid 且均值為 $\mu$ 變異為 $\sigma^2$。則不難發現 $$ S_n := \sum_{i=1}^{n} X_{n,i} = \sum_{i=1}^{n} \frac{Y_i - \mu}{\sqrt{n}} = {\sqrt{n}}(\bar{Y}_n - \mu) $$ 其中 $\bar{Y}_n := \frac{1}{n} \sum_{i=1}^{n} Y_i$。現在我們檢驗 Lindeberg 條件：固定 $\varepsilon > 0$，我們觀察 \begin{align*} \frac{1}{\sigma_n^2} \sum_{i=1}^{n} \mathbb{E}[X_{n,i}^2 \mathbf{1}_{|X_{n,i}| > \varepsilon \sigma_n}] &= \frac{1}{\sigma^2} \sum_{i=1}^{n} \mathbb{E}[ (\frac{Y_i - \mu}{\sqrt{n}})^2 \mathbf{1}_{|\frac{Y_i - \mu}{\sqrt{n}}| > \varepsilon \sigma}] \\ &= \frac{1}{\sigma^2} \sum_{i=1}^{n} \mathbb{E}[ (\frac{(Y_i - \mu)^2}{{n}}) \mathbf{1}_{|{Y_i - \mu}| > \varepsilon \sigma \sqrt{n}}] \\ &= \frac{1}{\sigma^2 n} \sum_{i=1}^{n} \mathbb{E}[ (Y_i - \mu)^2 \mathbf{1}_{|{Y_i - \mu}| > \varepsilon \sigma \sqrt{n}}] \\ &= \frac{1}{\sigma^2 n} \sum_{i=1}^{n} \mathbb{E}[ (Y_1 - \mu)^2 \mathbf{1}_{|{Y_1 - \mu}| > \varepsilon \sigma \sqrt{n}}] &&\text{$Y_i$ are iid}\\ &= \frac{1}{\sigma^2 n} n \mathbb{E}[ (Y_1 - \mu)^2 \mathbf{1}_{|{Y_1 - \mu}| > \varepsilon \sigma \sqrt{n}}] \\ &= \frac{1}{\sigma^2} \mathbb{E}[ (Y_1 - \mu)^2 \mathbf{1}_{|{Y_1 - \mu}| > \varepsilon \sigma \sqrt{n}}] \\ \end{align*} 注意到 $(Y_1 - \mu)^2 \mathbf{1}_{|{Y_1 - \mu}| > \varepsilon \sigma \sqrt{n}} \xrightarrow{a.s.} 0$ 且 $(Y_1 - \mu)^2 \mathbf{1}_{|{Y_1 - \mu}| > \varepsilon \sigma \sqrt{n}} \leq (Y_1 - \mu)^2 $，因為 ${\rm var}(Y_1)= \sigma^2<\infty$故 $(Y_1-\mu)^2$可積，由 Dominated Convergence Theorem (DCT) 可知 \begin{align*} \lim_{n\to\infty} \frac{1}{\sigma_n^2} \sum_{i=1}^{n} \mathbb{E}[X_{n,i}^2 \mathbf{1}_{|X_{n,i}| > \varepsilon \sigma_n}] &= \lim_{n\to\infty} \frac{1}{\sigma^2} \mathbb{E}[ (Y_1 - \mu)^2 \mathbf{1}_{|{Y_1 - \mu}| > \varepsilon \sigma \sqrt{n}}] \\ &= \frac{1}{\sigma^2} \mathbb{E}[ \lim_{n\to\infty} (Y_1 - \mu)^2 \mathbf{1}_{|{Y_1 - \mu}| > \varepsilon \sigma \sqrt{n}}] \\ &= 0 \end{align*} 故 Lindeberg條件成立，由 Lindeberg-Feller CLT 可知， $$ \underbrace{ \frac{S_n}{\sigma_n}}_{= \frac{\sqrt{n}}{\sigma}(\bar{Y}_n - \mu)} \xrightarrow{D} \mathcal{N}(0,1) $$ 亦即標準CLT成立。 

 三角陣列的使用非常廣泛，除了前述的CLT之外，比如Poisson 極限定理(或稱 Weak Law of Small Numbers)，我們定義 $S_n := \sum_{i=1}^{n} X_{n,i}$ 則每個 $S_n$ 都是一個隨機變數且數列 $\{S_n\}_{n \ge 1}$ 可以討論收斂性。

Poisson Limit Theorem:對每個 $n \geq 1$，令 $\{X_{n,i}\}_{i=1}^n$ 為一族隨機變數，其整體族 $\{X_{n,i}\}_{n\geq 1, 1\leq i \leq n}$ 構成一個三角陣列，對每個 $n$ 而言，$X_{n,1}, \dots, X_{n,n}$ 相互獨立且 $X_{n,i} \sim Bernoulli(p_{n,i})$。定義 $n$ 項有限和 $S_n:= \sum_{i=1}^n X_{n,i}$ 且假設當 $n \to \infty$，我們有 $$\max_{1\leq i \leq n} p_{n,i} \to 0$$ 且 $$\sum_{i=1}^n p_{n,i} \to \lambda <\infty$$ 則 $S_n \xrightarrow{D} Poisson(\lambda)$

Remark: 前述定理第一個條件 $\max_{1\leq i \leq n} p_{n,i} \to 0$ 保證單一事件為稀有事件；第二個條件$\sum_{i=1}^n p_{n,i} \to \lambda <\infty$保證總強度有限。

[機率論] 多變數連續映射保持機率收斂

以下我們介紹機率收斂用的推廣型連續映射定理。一些先備知識如下

Definition (Norms)

令 $\mathbf{x} \in \mathbb{R}^k$。則標準 Euclidean norm $\|\mathbf{x}\|:=\sqrt{\sum_{i=1}^k x_i^2}$。

Definition (Tightness of the law of a random vector)

令 $(\Omega, \mathcal{F}, P)$ 為機率空間 且 $\mathbf{X}$ 為 $\mathbb{R}^k$ 上的隨機向量，記其在 $(\mathbb{R}^k,\mathcal{B}(\mathbb{R}^k))$ 上的分佈為 $\mu_X$滿足 $$\mu_X(A) := P(X^{-1}(A)) = P(\{\omega \in \Omega: X(\omega) \in A\}), \qquad A \in \mathcal{B}(\mathbb{R}^k)$$ 我們說 $\mu_X$（或 $\mathbf{X}$ 的分佈）是  tight  若 對任意 $\varepsilon>0$，存在常數 $M>0$ 使得 \[ {P}(\|\mathbf{X}\|>M) = \mu_X(\{\mathbf{x}:\|\mathbf{x}\|>M\}) < \varepsilon \] 

Remark. 上述條件等價於 \[ \lim_{M\to\infty} {P}(\|\mathbf{X}\|>M)=0. \] 因此，給定任意 $\eta>0$，存在 $M>0$ 使得 \[ {P}(\|\mathbf{X}\|>M) < \frac{\eta}{2}, \quad\text{亦即}\quad {P}(\|\mathbf{X}\|\le M) > 1-\frac{\eta}{2}. \]

Lemma. 任意 $\mathbb{R}^k$-valued 隨機向量的分布都是 tight

Proof.  令 $\mathbf{X} : \Omega \to \mathbb{R}^k$ 為隨機向量，其分佈記作 $\mu_X$。由於 $\mu_X$ 是機率測度，故 $\mu_X(\mathbb{R}^k) = 1$。注意到全體 $\mathbb{R}^k$ 空間可以寫成compact sets的遞增連集極限，亦即 $$\mathbb{R}^k = \cup_{M=1}^\infty [-M, M]^k$$令 $K_M:=[-M, M]^k $則對任意 $M \in \mathbb{N}$，注意到我們有 $K_{M} \subset K_{M+1}$，亦即 $\{K_M\}$ 為遞增集合族。故由機率測度對遞增集族的連續性可得 $$1=\mu_X(\mathbb{R}^k) = \mu_X(\cup_{M=1}^\infty [-M, M]^k) = \lim_{M \to \infty} \mu_X([-M, M]^k) $$因此由極限定義可知，對任意 $\varepsilon >0$，存在$N  \in \mathbb{N}$ 使得 $M \geq N$, 我們有 $|1-\mu_X(K_M)| <\varepsilon$，由於 $\mu_X(K_M) \leq 1$，我們可去掉絕對值並將不等式等價改寫為 $\mu_X(K_M) > 1-\varepsilon$，亦即 $$\mu_X(\{ \mathbf{x} : \|\mathbf{x}\| > M\}) < \varepsilon$$

Definition (Convergence in Probability Vector)

令 $\{\mathbf{X}_n\}$ 為 $\mathbb{R}^k$ 上的隨機向量序列，令 $\mathbf{X} \in \mathbb{R}^k$ 為一隨機向量。我們說 $\mathbf{X}_n$機率收斂(convergence in probability)到 $\mathbf{X}$，記作 $\mathbf{X}_n \overset{P}{\to} \mathbf{X}$，若下列條件成立：對任意 $\varepsilon >0$， $$P(\|\mathbf{X}_n - \mathbf{X}\|\geq \varepsilon) \to 0$$ 

有了上面的定義，我們可以給出多變數連續映射定理的敘述以及證明。

Theorem (Multivaraite Continuity Mapping): 令 $\{\mathbf{X}_n\}$ 為 $\mathbb{R}^k$ 上的隨機向量序列，令 $\mathbf{X} \in \mathbb{R}^k$ 為一隨機向量。現在取 $g: \mathbb{R}^k \to \mathbb{R}^m$ 為連續函數。若 $\mathbf{X}_n \overset{P}{\to} \mathbf{X}$ 當 $n \to\infty$，則 $$ g(\mathbf{X}_n) \overset{P}{\to} g(\mathbf{X})$$ 當 $n \to\infty$

Proof. 令 $\varepsilon >0$ 且 $\eta >0$ 。首先透過 localization 建構 compact ball ：由於 $\mathbf{X}$ 為隨機向量，由 tightness 性質可知，存在一個足夠大的常數 $M > 0$ 使得

$$ P(\|\mathbf{X}\| > M) < \frac{\eta}{2} $$

現在令 $$ S:= \overline{B}_{M+1}(\mathbf{0}) =\{\mathbf{z} \in \mathbb{R}^k: \|\mathbf{z}\| \leq M+1\}$$ 為半徑 $M+1$ 且球心在 $\mathbf{x} = \mathbf{0}$ 的closed ball。由 Heine-Borel定理，$S$ 為 closed bounded set，故 $S$ 為 $\mathbb{R}^k$中 compact set (緊緻集)。

因為 $g$ 為在 $\mathbb{R}^k$ 連續函數，故將 $g$ 限制在緊緻集 $S \subset \mathbb{R}^k$ 具有uniform continuity (均勻連續性)。這表示存在 $\delta > 0$ (不失一般性情況下，選 $\delta < 1$) 使得對所有 $\mathbf{x}, \mathbf{y} \in S$，我們有

$$\|\mathbf{x} - \mathbf{y}\| < \delta \implies \|g(\mathbf{x}) - g(\mathbf{y})\| < \varepsilon$$

現在來分析事件 $\{\|g(\mathbf{X}_n) - g(\mathbf{X})\| \geq \varepsilon\}$。如果我們限制在事件 $$E=\{\|\mathbf{X}\| \leq M\} \cap \{ \|\mathbf{X}_n - \mathbf{X}\| < \delta \}$$ 之下，則

1. $\| \mathbf{X}\| \leq M < M+1$ 可知 $\mathbf{X} \in S$。

2. 由 三角不等式 (or Minkowski不等式) $$\|\mathbf{X}_n\| = \|\mathbf{X}_n - \mathbf{X} + \mathbf{X}\| \leq \|\mathbf{X}_n - X\| + \|\mathbf{X}\| < M+1$$故 $\mathbf{X}_n \in S$。

由於 $\mathbf{X}_n, \mathbf{X} \in S$ 。uniform continuity 告訴我們 $$\{\|\mathbf{X}\| \leq M\} \cap \{ \|\mathbf{X}_n - \mathbf{X}\| < \delta\} \implies \{\|g(\mathbf{x}) - g(\mathbf{y})\| < \varepsilon\}$$ 這意味著，若 $\|\|g(\mathbf{x}) - g(\mathbf{y})\| \geq \varepsilon\|$ 發生，則必然是上述事件 $E$不成立 (取 contrapositvie 敘述)： $$\{\|g(\mathbf{x}) - g(\mathbf{y})\| \geq \varepsilon \} \subset \{ \|\mathbf{X}\| > M \} \cup \{\|\mathbf{X}_n - \mathbf{X} \| \geq \delta \}$$ 兩邊同取機率測度得到

\begin{align*} P(\|g(\mathbf{x}) - g(\mathbf{y})\| \geq \varepsilon ) & \leq P( \|\mathbf{X} > M\| ) + P( \|\mathbf{X}_n - \mathbf{X} \| \geq \delta )\\ & < \frac{\eta}{2} + P( \|\mathbf{X}_n - \mathbf{X} \| \geq \delta ) \qquad (*)\end{align*}

因為 $\mathbf{X}_n \overset{P}{\to} \mathbf{X}$，故 $P( \|\mathbf{X}_n - \mathbf{X} \| \geq \delta ) \to 0$ 亦即，存在一個夠大的 $N$ 使得當 $n\geq N$，我們有

$$ P( \|\mathbf{X}_n - \mathbf{X} \| \geq \delta ) < \frac{\eta}{2} $$ 當 $n\geq N$時，式 $(*)$ 變成 $$P(\|g(\mathbf{x}) - g(\mathbf{y})\| \geq \varepsilon )  < \frac{\eta}{2} + \frac{\eta}{2} < \eta$$ 由於 $\eta$ 是任取的，故我們推得 $P(\|g(\mathbf{x}) - g(\mathbf{y})\| \geq \varepsilon )  \to 0$

[機率論] 一類含有supremum運算與期望值的不等式問題

令 $X,Y$ 為兩隨機變數定義在某機率空間 $(\Omega, \mathcal{B}, P)$ 且 $f: \mathbb{R}^2 \to \mathbb{R}$ 為一連續函數。若對 $X$ 的實現 $X=x$ 而言 (亦即，存在 $\omega \in \Omega$ 使得 $X(\omega) = x$ )，我們顯然有 

$$\mathbb{E}[f(x,Y)] \leq \sup_x \mathbb{E}[f(x,Y)]$$ 

試問上述不等式左方若將 $x$ 換回隨機變數 $X$ 時仍然成立?亦即我們想問 $$\mathbb{E}[f(X,Y)] \leq ? \sup_x \mathbb{E}[f(x,Y)]$$

答案是否定的，我們看以下的反例：

Counterexample

考慮隨機變數 $X=Y$ 且 $P(X=1)=P(X=-1) = 1/2$ 且 $f(x,y) := xy$ 則我們可驗證 $$\mathbb{E}[f(X,Y)] = \mathbb{E}[X^2] = 1/2 + 1/2 = 1$$然而如果我們觀察 $$\mathbb{E}[f(1,Y)] = \mathbb{E}[Y] = \mathbb{E}[X] = 0$$ 另外 $$\mathbb{E}[f(-1,Y)] = \mathbb{E}[-Y] = -\mathbb{E}[X] = 0$$ 故 $\sup_x\mathbb{E}[f(x,Y)] = 0$但是 $$\sup_x\mathbb{E}[f(x,Y)] < \mathbb{E}[f(X,Y)]$$

[隨機系統] 淺論賭博系統理論 (1)

考慮某賭博系統其報酬率定義為 i.i.d. 隨機變數，記作 $X(k)$  且具有分佈 $F_X$ 。現在定義 $V(k)$ 為在時刻 $k$ 之資產價值，且令 $K \in [0,1]$ 為投資比率，則時刻 $k$ 之投資策略可記作
\[
I(k) := K V(k)
\]且投資人資產動態模型可表為
\begin{align*}
  V(k + 1) &= V(k) + I(k)X(k) \hfill \\
   &= V(k) + KX(k)V(k) \hfill \\
   &= \left( {1 + KX(k)} \right)V(k) \hfill \\
\end{align*}

Definition: Growth Rate and Optimal Growth Rate
以投資比率 $K$ 為投資策略之資產成長率 (Growth Rate) 定義為
\[
g(K) := E[\log(1+K X(k))]
\]
另外我們接著定義 最佳成長率 (Optimal Growth Rate) 如下
\[
g^* := \max_K g(K)
\]且我們稱 $K^*$ 達到 $g^*$ 為 log-optimal feedback gain。


Comments:
上述問題的最簡形式(投擲單一銅板問題) 即為經典 凱利問題 (Kelly Optimization Problem) 且上述的最大化成長率又稱為凱利判准 (Kelly Criterion)，有興趣讀者請參閱本部落格關於凱利問題的相關文章。


上述最佳成長率存在性由下列定理確保。

=================
Theorem:
令 $X(0),X(1),...X(N-1)$ 為 i.i.d. 報酬 且具有分佈 $F_X$，現在令
\[\frac{{{V^*}(N)}}{{V(0)}} = \prod\limits_{k = 0}^{N-1} {\left( {1 + {K^*}X(k)} \right)} \]則當 $N \to \infty$，我們有
\[\frac{1}{N}\log \frac{{{V^*}(N)}}{{V(0)}} \to {g^*}\]almost surely.
=================

Proof: 首先觀察
\begin{align*}
  \frac{1}{N}\log \frac{{{V^*}(N)}}{{V(0)}} &= \frac{1}{N}\log \prod\limits_{k = 0}^{N - 1} {\left( {1 + {K^*}X(k)} \right)}  \hfill \\
   &= \frac{1}{N}\sum\limits_{k = 0}^{N - 1} {\log \left( {1 + {K^*}X(k)} \right)}  \hfill \\
\end{align*}接著注意到因為  $\{X(0),X(1),...X(N-1)\}$ 為 i.i.d. 故
\[
\{1 + {K^*}X(1),  \;1 + {K^*}X(1),...,\; 1 + {K^*}X(N-1)\}
\]亦為 i.i.d. ，且注意到 $ E\left[ {\log \left( {1 + {K^*}X(0)} \right)} \right] = {g^*}$ 故 利用 強大數法則 (請參閱下方 FACT) 可得當 $n \to \infty$ 我們有
\[\frac{1}{N}\sum\limits_{k = 0}^{N - 1} {\log \left( {1 + {K^*}X(k)} \right)}  \to E\left[ {\log \left( {1 + {K^*}X(0)} \right)} \right] = {g^*}\]almost surely。即為所求。 $\square$


=================
FACT: 強大數法則 (Strong Law of Large Numbers): 若 $X(1),X(2)...$ 為 i.i.d. 隨機變數且 $E[X(0)] $ 存在 。現令 $S(N):=X(1)+X(2)+...+X(N)$ ，則當 $N \to \infty$ 我們有
\[
\frac{S(N)}{N} \to E[X(0)]
\]almost surely
=================

Proof: Omitted. see R. Durrett, Probability Theory and Examples,

[投資理論] 數學能擊敗金融市場嗎？

以下為個人在 University of Wisconsin-Madison 臺灣學生會 2016年 第一場學術沙龍中 分享的簡報：

數學能擊敗金融市場嗎？-從控制理論觀點 （2016, 02. 16)

講者：謝宗翰
講題：數學是否能擊敗金融市場？-從控制理論觀點
簡介：此講題將試圖回答一個基本問題：是否存在一種「必勝法」，使得投資績效具備恆正報酬？我們將從現代投資理論出發，最終止於財務工程與控制理論，過程中，我們將逐步揭示何時可以透過數學幫助我們建構一組可行的「最佳」交易策略。


關於 UW-Madison 臺灣學生會 連結
https://sites.google.com/site/satuwmadison/