機率方法

在數學中，機率方法是一個非構造性的證明方法。機率方法由艾狄胥·帕爾發揚光大，主要在組合數學中用於證明具有某性質的數學物件的存在性。機率方法證明如果以某種方式隨機抽取物件，那有大於 0 的機率抽到給定性質的物件，進而推論這樣的物件存在。雖然證明利用到機率，但最終結論是確定性的。

機率方法在數學的其他分支也被廣泛利用，像是數論、線性代數、實分析、電腦科學和資訊理論。

## 引言

如果一群數學物件的集合都不滿足某性質，那麽從這個集合隨機選出的物件滿足該性質的機率為零。從逆否命題可知，如果從集合隨機選出的物件滿足該性質的機率大於零，則這個集合的某個物件必然滿足該性質。

同樣地，我們可以透過證明滿足性質的機率小於一，來證明存在不滿足某條件的物件。

計算某隨機變數的期望值也是機率方法中的常見手法。一個隨機變數有非零的機率大於等於期望值，因此可以證明這樣子的物件存在。進一步來說，如果可以證明此隨機變數有非零的機率小於期望值，那就可以證明這個隨機變數也有非零的機率大於期望值。

機率方法常常需要使用馬可夫不等式、切爾諾夫不等式和 Lovász Local Lemma 等數學工具。

## 應用機率方法的例子

雖然在艾狄胥之前就有利用機率方法的證明（像是 Szele (1943) 用機率方法證明了存在有很多哈密頓環的競賽圖），許多利用機率方法的有名證明是艾狄胥給出的，像是以下的兩個例子。

### 範例一

艾狄胥（1947）透過機率方法給出了一個拉姆齊數 $R(r, r)$ 的下界。$R(r, r)$ 為最小的正整數 $n$，使得把大於等於 $n$ 個點的完全圖每條邊染上紅色或藍色後，必定存在邊全為紅色或藍色的完全圖 $K_n$。

我們想要證明存在足夠小的 $n$，使得在把完全圖 $K_n$ 的邊染上紅色或藍色後，不存在同色的完全圖 $K_r$，這會使得 $R(r, r) > n$。

證明的方法為把圖上每條邊以 $1/2$ 的機率染上紅色、$1/2$ 的機率染上藍色。我們可以用以下方法計算同色子圖 $K_r$ 出現次數的期望值。

考慮任意大小為 $r$ 的點集 $S_r$。我們定義 $X(S_r)$：如果連接 $S_r$ 中兩點的所有邊顏色都相同，則 $X(S_r) = 1$，否則 $X(S_r) = 0$。定義 $X$ 是所有可能 $S_r$ 的 $X(S_r)$ 總和，可以注意到 $X$ 會是此圖中同顏色 $K_r$ 的數量。對於任意一個點集 $S_r^i$，$X(S_r^i)$ 的期望值就是 ${r \choose 2}$ 條邊顏色相同的機率（全為藍色或全為紅色）：

$$E[X(S_r^i)] = 2 \cdot 2^{-{r \choose 2}}$$

對任意 ${n \choose r}$ 個點集來說，$E[X(S_r^i)]$ 都相同。又因爲期望值的可加性，$X$ 的期望值就是

$$E[X] = \sum\limits_{i = 1}^{n \choose r} E[X(S_r^i)] = {n \choose r}2^{1-{r \choose 2}}.$$

如果 $E[X]$ 小於 $1$，那麽就存在一個邊著色的方法使得圖中邊同色的 $K_r$ 子圖數量小於 $1$，也就是子圖數量為 $0$。因此，如果

$$E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}} < 1 \Rightarrow {n \choose r} < 2^{{r \choose 2} - 1}$$

那必然存在邊著色的方法使得圖中沒有同色的 $K_r$ 子圖。

根據拉姆齊數的定義，只要正整數 $n, r$ 滿足上式，那就代表 $R(r, r) > n$。這代表 $R(r, r)$ 會隨 $r$ 呈指數性成長。

因為證明是非構造性的，找出一種塗色方法非常困難，是個未解問題。

### 範例二

艾狄胥（1959）（詳見參考文獻）回答了圖論中的下列問題：給定正整數 $g$ 跟 $k$，是否存在一張圖的著色數至少為 $k$，但只存在長度至少 $g$ 的環？

透過機率方法，我們可以證明這樣的圖對任意 $g, k$ 皆存在。我們選擇一個足夠大的 $n$，並考慮 $n$ 個點的隨機圖 $G$。我們讓 中的每條邊都有 $p = n^{\frac{1}{g} - 1}$ 的機率存在。我們可以證明以下兩個性質。

性質 1. 有超過 $\frac{1}{2}$ 的機率，使得 $G$ 中最多只有 個長度小於 $g$ 的環。

證明. 令 X 為長度小於 $g$ 的環的個數。對於正整數 $i$，完全圖 $K_n$ 中有

$$\frac{n!}{2\cdot i \cdot (n-i)!} \le \frac{n^i}{2}$$

個長度恰好為 $i$ 的環。每個這樣的環在 $G$ 的出現機率為 pi。根據馬可夫不等式。

$$\Pr \left (X> \tfrac{n}{2} \right )\le \frac{2}{n} E[X] \le \frac{1}{n} \sum_{i=3}^{g-1} p^i n^i = \frac{1}{n} \sum_{i=3}^{g-1} n^{\frac{i}{g}} \le \frac{g}{n} n^{\frac{g-1}{g}} = gn^{-\frac{1}{g}} = o(1).$$

因此，對於足夠大的 $n$，性質 1 有大於 $\frac{1}{2}$ 的機率為真。

性質 2. G 不存在大小為 $\lceil \tfrac{n}{2k} \rceil$ 的獨立集。

證明. 令 $Y$ 為 $G$ 中最大獨立集的大小。當 $y = \left \lceil \frac{n}{2k} \right \rceil\!.$ 時，我們有

$$\Pr (Y\ge y) \le {n \choose y}(1-p)^{\frac{y(y-1)}{2}} \le n^y e^{-\frac{py(y-1)}{2}} = e^{- \frac{y}{2} \cdot (py -2\ln n - p)} = o(1)$$

因此，對於足夠大的 $n$，性質 2 有大於 $\frac{1}{2}$ 的機率為真。

因為性質 1 跟 2 對足夠大的 $n$ 都有大於 $\frac{1}{2}$ 成立，這兩個性質不能是互斥的。因此，存在一張圖 $G$ 使這兩個性質皆成立。

根據性質 1，只要從 $G$ 移除最多 $\frac{n}{2}$ 個點，我們就可以得到一張新的圖 $G'$，它有 $n'\geq n/2$ 個點，而且只存在長度至少 $g$ 的環。這個新圖 $G'$ 仍然沒有大小 $\left \lceil \frac{n}{2k}\right\rceil \leq \left \lceil \frac{n'}{k}\right\rceil$ 的獨立集，至少要被分成 $k$ 個獨立集，所以 $G'$ 的著色數至少為 $k$。

## 參見

- 互動式證明系統
- 拉斯維加斯演算法
- Incompressibility method
- Method of conditional probabilities
- 隨機圖

## 延伸閱讀

- Probabilistic Methods in Combinatorics, MIT OpenCourseWare

## 參考文獻

- Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. .
- J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.
- Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics
- Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, , 2017
- Elishakoff I., Lin Y.K. and Zhu L.P., Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; 0 444 81624 0