機率方法

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

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

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

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

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

機率方法常常需要使用馬可夫不等式、和等數學工具。

應用機率方法的例子
雖然在艾狄胥之前就有利用機率方法的證明（像是 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}}

，那必然存在邊著色的方法使得圖中沒有同色的 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 的環。

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

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

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

:\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. 不存在大小為 \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。

參見
*互動式證明系統
*拉斯維加斯算法
*
*
*隨機圖

评论 (0)