艾狄胥（Erdős）與機率方法：用機會證明存在
保羅·艾狄胥（Paul Erdős）沒有家，沒有一般意義上的工作，幾乎沒有任何財產。他一生提著一只手提箱，在各所大學之間旅行，出現在同事家門口時說的話是「我的腦袋是敞開的」，離開時則留下一連串的定理與未解的問題，數學家們至今仍在處理。在他創造的所有東西之中，有一個想法特別突出，因為它改變了證明的做法。它叫做機率方法，而它的核心是一個聽起來幾乎像作弊的招數：拒絕把東西造出來，卻證明它存在。
問題：什麼時候秩序無可避免？
從一個聽起來很簡單的謎題開始。在六個人的聚會上，任兩個人不是朋友就是陌生人。結果發現，在任何六個人之中，你總是能找到三個彼此都是朋友的人，或是三個彼此都是陌生人的人。秩序強行出現。研究這種情況何時必然發生的數學分支叫拉姆齊（Ramsey）理論，它替這個問題配上了一個數。
拉姆齊定理保證這些數存在，但沒有說它們有多大。自然的下一個問題是：一個群體可以大到什麼程度，卻仍然避免出現任何大小為 k 的單色群集？回答這個問題，意味著要證明存在這樣一種巧妙的上色方式。而這正是動手建造變得毫無希望的地方，因為可能的上色方式數量是天文數字。
艾狄胥的招數：不要造它，數它
艾狄胥在 1947 年的洞見，是不再試圖設計一種好的上色方式，而是完全隨機地上色，然後讓算術去完成工作。這個論證簡短到可以完整地跟著走一遍。
擲硬幣為每一條連線上色
取 n 個人，考慮每一對人之間都有一條邊相連的完全網路。獨立地隨機為每條邊上色，紅色或藍色，機率各為二分之一。沒有任何巧思，沒有任何設計。只是替每一條邊擲一枚公平的硬幣。
衡量某一個群體為單色的可能性有多大
固定任意一組特定的 k 個人。他們之間共有 C(k,2) 條邊，也就是 條連線。要讓所有這些邊都是同一種顏色，是不太可能的：機率是 ，因為有兩種顏色，而且 C(k,2) 次擲硬幣的結果都要一致。把這個很小的數稱為 p。
把壞群體的期望個數加起來
需要擔心的、由 k 個人構成的不同群體共有 C(n,k) 個。根據期望值的線性性質，完全單色的群體的期望個數，就是群體的個數乘上每一個群體的機率：。這一個式子捕捉了隨機上色平均會包含多少個單色群集。
如果平均值小於 1，就必定存在一個完美的上色
現在選擇 n 大約是 。在這個選擇之下，上面的期望值會小於 1。但實際單色群體的個數是一個整數，而如果所有上色方式的平均值小於 1，那麼至少有一種上色方式的得分是 0。那種上色方式完全沒有大小為 k 的單色群體。因此 R(k,k) 大於 n，也就是大約 。
再讀一次最後那一步，因為整個魔法就在這裡。我們從未產生一個好的上色方式，也從未描述過一個。我們證明的是，平均的上色方式離完美如此之近，以致於一個完美的上色必然存在於這一堆之中的某處。這個證明讓你確定某個特定物件的存在，卻沒有指向任何一個物件。
為什麼這是革命性的
在艾狄胥之前，證明某個東西存在，幾乎總是意味著把它構造出來，或至少描述一個能構造它的程序。機率方法打破了這種期待。它確立了隨機性本身可以作為證明：如果一次隨機的嘗試以任何大於零的機率成功，那麼成功就是可能的，僅此而已。
這種非構造性的風格，讓這個論證與數學中一些最優雅的結果同屬一個家族。康托爾的對角論證同樣證明了某個東西的存在，也就是任何列表中都缺少的一個數，靠的是純粹的邏輯力量，而不是明確的構造。兩者共有那種安靜、幾乎令人不安的力量：結論無懈可擊，即使它從未讓你看到它所承諾的東西。這裡的隨機性建立在機率直觀入門所涵蓋的同樣基礎上，那裡從頭建立了期望值的概念，也就是第三步的引擎。
艾狄胥問題與它們的 AI 時刻
艾狄胥不只證明定理。他還提出了問題，數以百計，往往附上小額的獎金，從一道棘手練習題的幾美元，到他相信真正深刻的問題的數千美元不等。其中許多問題至今仍未解決，並已被仔細地編目，維護在 erdosproblems.com。
其中的禪意
機率方法之美，與一場好的魔術同理：你看著每一個步驟，找不到你被騙的地方，然而結果仍然讓人覺得不可能。這裡沒有障眼法。期望值確實小於一，而一個整數低於它自己的平均值，就必然在某處降到零。確定性是完全的，構造是缺席的，而這兩件事同時為真。
這就是艾狄胥留下的長久教訓。存在與構造不是同一回事。有時候，知道一個完美的物件就在那裡，最乾淨的方式，是證明平均的物件幾乎是完美的，然後讓這個差距去完成其餘的部分。想看另一個以單一一行串起看似無關想法的結果，歐拉恆等式提供了相反的一種美：艾狄胥從計數中變出存在，歐拉則釘住一個確切而必然的數。
常見問題
- 機率方法是什麼？
- 這是一種證明具有某種性質的物件存在、卻不直接把該物件造出來的方法。你建立這個東西的一個隨機版本，證明它具有你想要的性質的機率大於零，然後推論至少有一個這樣的物件必定存在。保羅·艾狄胥開創了這項技巧，如今它是組合學與資訊科學的核心工具。
- 艾狄胥用它證明了什麼？
- 他在 1947 年的里程碑成果，給出拉姆齊數的一個下界：他證明對角拉姆齊數 R(k,k) 大於 2^(k/2)。白話來說，存在一種用兩種顏色為大型網路中的連線上色的方式，使得沒有任何大型群體的連線全是同一種顏色。他證明了這些上色方式存在，卻從未拿出任何一個，只靠計數。
- 沒有把它造出來，怎麼證明某個東西存在？
- 靠平均值。如果你隨機挑選一個物件，計算它的缺陷的期望個數，而這個期望值小於 1，那麼這一堆物件中，至少有一個的缺陷數為零。隨機挑選的缺陷個數平均小於一，就保證集合中某處有一個完美的例子，即使論證從未指出是哪一個。
- 拉姆齊數是什麼？
- 拉姆齊數 R(k,k) 是無論你如何安排，都必然會出現秩序的最小群體大小。具體而言，R(k,k) 是最小的人數，使得無論你如何把每一對人分成朋友或陌生人，都保證存在一組 k 個人，他們彼此全是朋友，或彼此全是陌生人。拉姆齊定理說這些數存在；艾狄胥的方法則說明它們成長得非常快。
- 機率方法在今天為什麼重要？
- 它把隨機性變成一種證明技巧，如今這個想法貫穿組合學、演算法設計、編碼理論與理論資訊科學。許多關於網路與演算法的結果，至今仍是靠證明某個隨機構造以正的機率成功來得到的。這個方法也是為什麼艾狄胥自己提出的問題，有很大一部分至今仍是活躍的研究目標。
動手練一練
喜歡這樣一步步想通嗎？
Math Zen 把這種直覺變成每天的練習，用自適應題目涵蓋 24 個數學主題。
Math Zen 暂未在中国大陆的应用商店上架。
Not available in app stores in mainland China.
