[機率論] 三角陣列

在機率論中，我們常看到的是單一指標序列：$ \{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$保證總強度有限。

[隨筆] 當學生研究遇上「做不出來」的困境

這幾年指導學生的時候常遇到的問題就是學生會說「因為 OOO 做不出來，所以改用 XXX 方法」，有的甚至直接跳到 metaheuristic 方法，或者學生就等著看老師要怎麼辦，抑或是看能不能就直接更換題目。這種時候都讓我感到相當痛苦。

要知道「做不出來」(是主觀能力認定)  與「此問題無解」(是客觀事實否定) 其實有天淵之別，為了避免學生在「原方法尚未分析清楚」的情況下任意切換方法，導致研究方向失控或失去理論基礎。我將我的想法稍作整理，我想應該在廣義的(控制理論、隨機系統、最佳化、金融工程)領域都能適用：

什麼不是更換研究方法的理由：

以下理由都不足以支持換方法：

• 「跑不出答案(跑了很多次)」、「電腦算不動」、「算法不 converge 」、「結果怪怪的」、「找不到答案」、「證不出來」、「資料拿不到」
• 「我看別人（文獻）用這方法有效」、「別人(文獻)都這樣用」、「文獻看不懂」
• 「我覺得 metaheuristic 方法 GitHub 上有現成 package 比較簡單」
• 「我不知道怎麼 debug」、「code不會寫」

只說「做不出來」其實本身沒有任何意義。這類說法大多是「執行結果不如預期」而非「方法原理上不可行」。

要換方法應先提交 Failure Analysis Report：

未提交前，不應任意更換方法，也不該自行更動研究方向。這份報告的目的是要讓人看得出來，你已經有試過各種「系統性修正」，而不是亂試新方法，Failure Analysis Report 至少包含：

1. 原方法的完整理論與演算法描述
• 問題的 objective、constraints、dynamics
• 參數設定
• 算法步驟
• 預期應滿足的最佳性條件（如 KKT、Bellman、HJB）
• 預期應滿足的穩定性條件（如 Lyapunov function）
• 預期應滿足的強健性條件
• 預期應滿足的算法複雜度條件
• 預期應滿足的近似條件
2. 明確指出「哪裡做不出來」，只說「做不出來」= 無效論證。學生應回答：
• 失敗發生在哪一行計算？
• 是gradient / subgradient / Jacobian / Hessian 算不出來？
• 約束是否不相容？
• 數值解是否跳出可行域？數值誤差？
• dynamics 無法滿足？
• initial condition 是否導致 divergence？
• 實驗/模擬結果是否可重現？(不同資料集都指向同一結論)
• 模擬結果不佳的具體意義(穩定性不好？報酬不佳？變異太大？)
3. 合理的失敗原因推論（有理論或合理假設），例如：
• 模型非凸 → local solver 卡在 local minima
• state/control constraint 過於嚴格 → 無可行解
• dynamics stiffness 太高 → 數值爆炸
• objective/loss scale 不當 → 需要 normalization
• 多期多目標計算
4. Impossibility claim 的證明: 若你要宣稱「這個問題做不到 / 不可能」必須附上 理論或模擬證據，例如：

• 證明無可行解
• 顯示最佳性條件（KKT / Bellman）不可同時滿足
• 顯示系統缺失某robustness/stability/performance
• 指出該問題在某些條件下為 NP-hard
• 提供反例或實驗結果，清楚展示失敗原因

 沒有上述證據，只說「做不出來」、「不可能」等說法，是不會被直接接受的。我預期學生應該要提供：

1. 具體失敗證據（至少一種）
• 數值例子(宣稱非凸應該繪製其非凸的圖例)
• 圖表 (solution path, 誤差收斂曲線，state trajectory, etc)
• log / 訊息 (錯誤碼，停止條件)
• constraint violation 
• Optimality Condition (e.g., KKT) violation
• Complexity analysis  
• 數值或者理論反例
2. 至少三種「結構化修正」嘗試。以最佳化問題為例，可以包括：
• 調整 step size
• 更換 initial condition
• 放寬或修改部分 constraint
• scaling / normalization / shifting
• convex surrogate、linearization / relaxation
• 理論上合理的 heuristic（不是隨便 metaheuristic）
• greedy algorithm with provable approximation ratio 是合理的 heuristic；而 genetic algorithm without convergence guarantee 則不是。
• 求解器更換 (Gurobi/MOSEK/CVX)
• 更換solver本身仍應有明確理由，比如問題規模大小變動等等。

對採用「新方法」的要求：必須有合理性證據

允許換方法的合理理由示例：

• 新方法與研究問題結構更一致（例如 convex 問題改用 QP）
• 可以證明更好的 optimality/stability/robustness 性質
• 可以證明可行性、收斂性
• 文獻中有具體、可查證的支持

不合理理由示例：

• 「github上有現成套件」
• 「我覺得 metaheuristic 比較方便」
• 「網路上有人這樣用」
• 「我自己跑起來比較順」

若新方法無法在 「理論上更強」 或與 「結構更相容」 則禁止更換。未達以上要求就換方法，我傾向於將其視同無效研究行為。不僅浪費自己時間也浪費指導教授時間。

反思：

研究不是亂試方法，特別在遇到困難的時候，應該要去理解原方法限制在哪？為什麼失敗？

雖然說是這樣說，但是可能更多時候師生立場不同，可能學生觀點會認為是老師們都是「站著說話不腰疼」，只會在旁邊指指點點，但是在我自己經驗裡，其實情況更多時候往往相反：是我本人自己(而非學生)跳下去解決問題，重寫理論、重跑模擬、重寫論文幾乎是家常便飯。

如果長期都是這樣，那指導學生的意義何在？畢竟我本人已經有一博三碩，應該是不需要再多一個學位，因此這些關於「合格的研究方法」以及在「方法失敗時的分析與回報」的標準，確實應該是在研究最早期就應該先說清楚。