機率基礎工具
一句話解釋
分析隨機演算法的數學基礎：機率、條件機率、期望值，以及最重要的 Linearity of Expectation。
機率空間與公理
基本定義
機率空間
一個機率空間由三個元素組成：$(\Omega, \mathcal{F}, \Pr)$
- 樣本空間 $\Omega$： 所有可能結果的集合
- 事件空間 $\mathcal{F}$： $\Omega$ 的子集合族（可測事件）
- 機率測度 $\Pr$： $\mathcal{F} \to [0, 1]$ 的函數
Kolmogorov 機率公理
公理 1（非負性）：
$$\Pr[A] \geq 0, \quad \forall A \in \mathcal{F}$$
公理 2（規範性）：
$$\Pr[\Omega] = 1$$
公理 3（可數可加性）：
若 $A_1, A_2, \dots$ 兩兩互斥，則：
$$\Pr\left[\bigcup_{i=1}^\infty A_i\right] = \sum_{i=1}^\infty \Pr[A_i]$$
衍生性質
1. 補集： $\Pr[\bar{A}] = 1 - \Pr[A]$
2. 單調性： 若 $A \subseteq B$，則 $\Pr[A] \leq \Pr[B]$
3. 聯集界（Union Bound）：
$$\Pr[A \cup B] \leq \Pr[A] + \Pr[B]$$
4. 包含排斥原理：
$$\Pr[A \cup B] = \Pr[A] + \Pr[B] - \Pr[A \cap B]$$
條件機率與獨立性
條件機率
條件機率
定義： 給定事件 $B$ 發生，事件 $A$ 發生的機率：
$$
\Pr[A \mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}, \quad \text{若 } \Pr[B] > 0
$$
Bayes 定理
Theorem: Bayes' Theorem
$$
\Pr[A \mid B] = \frac{\Pr[B \mid A] \cdot \Pr[A]}{\Pr[B]}
$$
全機率公式（Law of Total Probability）：
若 $B_1, \dots, B_n$ 分割 $\Omega$（兩兩互斥且聯集為 $\Omega$），則：
$$
\Pr[A] = \sum_{i=1}^n \Pr[A \mid B_i] \cdot \Pr[B_i]
$$
範例：疾病檢測
- 疾病盛行率：$\Pr[\text{病}] = 0.01$
- 檢測靈敏度：$\Pr[\text{陽性} \mid \text{病}] = 0.99$
- 偽陽性率：$\Pr[\text{陽性} \mid \text{健康}] = 0.05$
問：檢測陽性時，真的有病的機率？
只有 16.6%！偽陽性嚴重稀釋了陽性結果的意義。
獨立性
定義： 事件 $A$ 和 $B$ **獨立**若：
$$
\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]
$$
等價條件：
- $\Pr[A \mid B] = \Pr[A]$（$B$ 不影響 $A$ 的機率）
- $\Pr[B \mid A] = \Pr[B]$
多個事件獨立：
事件 $A_1, \dots, A_n$ **互相獨立**若對任意子集 $I \subseteq \{1, \dots, n\}$：
$$
\Pr\left[\bigcap_{i \in I} A_i\right] = \prod_{i \in I} \Pr[A_i]
$$
隨機變數與期望值
期望值
隨機變數
隨機變數 $X$ 是從樣本空間到實數的函數：$X: \Omega \to \mathbb{R}$
期望值
離散情況：
$$\mathbb{E}[X] = \sum_{x} x \cdot \Pr[X = x]$$
連續情況：
$$\mathbb{E}[X] = \int_{-\infty}^\infty x \cdot f_X(x) \, dx$$
期望值的性質
Theorem: Linearity of Expectation
線性性：
$$\mathbb{E}[aX + bY] = a\mathbb{E}[X] + b\mathbb{E}[Y]$$
**關鍵：不需要 $X$ 和 $Y$ 獨立！**
推廣：
$$\mathbb{E}\left[\sum_{i=1}^n X_i\right] = \sum_{i=1}^n \mathbb{E}[X_i]$$
🔑 為什麼重要？
Linearity of Expectation 是隨機演算法分析的最強工具：
- 即使變數高度相關，期望仍可加
- 可以把複雜問題分解成簡單部分
- 不需要計算聯合分佈
經典應用：期望比較次數
問題： Quicksort 的期望比較次數？
定義指示變數（Indicator）：
\[X_{ij} = \begin{cases} 1 & \text{若元素 } i \text{ 和 } j \text{ 有比較} \\ 0 & \text{否則} \end{cases}\]總比較次數：
\[X = \sum_{i<j} X_{ij}\]期望：
\[\mathbb{E}[X] = \sum_{i<j} \mathbb{E}[X_{ij}] = \sum_{i<j} \Pr[i \text{ 和 } j \text{ 比較}]\]分析得 $\Pr[i \text{ 和 } j \text{ 比較}] = \frac{2}{j-i+1}$，所以：
\[\mathbb{E}[X] = 2n \ln n + O(n) = O(n \log n)\]關鍵： 不需要知道 $X_{ij}$ 之間的相關性！
常見分佈
重要分佈
Bernoulli 分佈
定義： 單次試驗，成功率 $p$
$$
X \sim \text{Bernoulli}(p)
$$
- $\Pr[X = 1] = p$，$\Pr[X = 0] = 1-p$
- $\mathbb{E}[X] = p$
- $\text{Var}(X) = p(1-p)$
Binomial 分佈
定義： $n$ 次獨立 Bernoulli$(p)$ 試驗的成功次數
$$
X \sim \text{Binomial}(n, p)
$$
- $\Pr[X = k] = \binom{n}{k} p^k (1-p)^{n-k}$
- $\mathbb{E}[X] = np$
- $\text{Var}(X) = np(1-p)$
推導（用 Linearity）：
令 $X = X_1 + \cdots + X_n$，其中 $X_i \sim \text{Bernoulli}(p)$
$$
\mathbb{E}[X] = \mathbb{E}[X_1] + \cdots + \mathbb{E}[X_n] = np
$$
Geometric 分佈
定義： 直到第一次成功的試驗次數
$$
X \sim \text{Geometric}(p)
$$
- $\Pr[X = k] = (1-p)^{k-1} p$
- $\mathbb{E}[X] = \frac{1}{p}$
- $\text{Var}(X) = \frac{1-p}{p^2}$
無記憶性（Memoryless）：
$$\Pr[X > n+m \mid X > n] = \Pr[X > m]$$
變異數與協方差
變異數
$$
\text{Var}(X) = \mathbb{E}[(X - \mathbb{E}[X])^2] = \mathbb{E}[X^2] - (\mathbb{E}[X])^2
$$
性質：
- $\text{Var}(aX + b) = a^2 \text{Var}(X)$
- 若 $X, Y$ 獨立：$\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y)$
協方差
$$
\text{Cov}(X, Y) = \mathbb{E}[(X - \mathbb{E}[X])(Y - \mathbb{E}[Y])] = \mathbb{E}[XY] - \mathbb{E}[X]\mathbb{E}[Y]
$$
性質：
- 若 $X, Y$ 獨立，則 $\text{Cov}(X, Y) = 0$（反之不一定）
- $\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y) + 2\text{Cov}(X, Y)$
總結
機率工具是隨機演算法的基礎：
- 機率公理 → Union Bound、包含排斥
- 條件機率 → Bayes 定理、全機率
- 獨立性 → 簡化計算
- 期望值 → Linearity of Expectation（最重要！）
- 常見分佈 → Bernoulli, Binomial, Geometric
下一步：用這些工具分析演算法的時間、正確性與效能！
參考資料
- Mitzenmacher & Upfal, Probability and Computing, Chapter 1-2
- Motwani & Raghavan, Randomized Algorithms, Appendix A
- Ross, A First Course in Probability