機率不等式與集中不等式

第一動差法(first moment method)

這裡有一個看似簡單卻威力強大的問題:你要如何證明某個精巧的物件——一個沒有大團的圖、一個沒有單色線的著色、一道謎題的解——不存在,或反過來幾乎必然存在,而從不真的把它建構出來?第一動差法靠著「平均地數」來辦到這件事。它把一個計數的期望,連結到這個計數能否為零。

這個想法立基於對非負整數計數 N(比方「壞」組態的數目)的一行觀察:若平均計數很小,計數通常為零。形式上,由馬可夫不等式,P(N >= 1) <= E[N]。所以若 E[N] < 1,則 P(N >= 1) < 1,這表示 P(N = 0) > 0——必定存在一個完全沒有壞組態的結果。要算 E[N],你把 N 寫成一群指示變數之和,每個潛在的壞組態一個,再用期望值的線性:E[N] = 對(每個組態為壞的機率)求和。線性是魔法所在——它完全不需要獨立。

這是組合學中機率方法的基石。要證明某物存在,就證明一個隨機建構以正機率產生它(E[壞計數] < 1,故存在一個無壞的結果)。要證明某事件罕見,就證明它的期望計數趨於 0,迫使機率趨於 0。誠實的侷限:小的期望保證計數「常常」為零,卻不能保證它「總是」為正——對反方向(以高機率證明 N >= 1)而言,大的 E[N] 並不足夠,因為計數可能偶爾很大而通常為零。這個缺口正是第二動差法所修補的。

要證明完全圖的邊有一種隨機 2-著色能避開大小為 k 的單色團,令 N 數單色 k-團。由線性,E[N] = (k-子集數) 乘以 2 / 2^(k choose 2)。若此值小於 1,則 P(N = 0) > 0,所以必定存在一種沒有這種團的著色——無需真的展示出任何一個就證明了。

若壞東西的平均計數低於 1,就必定存在一個無壞的結果。

大的 E[N] 並不能證明 N 典型上 >= 1——計數可能通常為零、罕見地巨大。要從另一個方向證明存在,你需要第二動差法。

又称
expectation methodfirst-moment argument一階動差法期望值法