機率方法

第一動差法(the first moment method)

第一動差法是基本機率方法的主力精煉版,它利用計數隨機變數的期望值來證明存在性或不存在性。它回答形如「是否存在沒有壞子結構的組態?」以及「某隨機量通常是否很大?」的問題,做法是計算單一數值——第一動差 E[X],其中 X 計數那些討厭的子結構。它之所以稱為第一動差法,是因為它只用 E[X](第一動差),不涉及變異數或更高階動差的任何資訊。

僅憑期望值便有兩個互補的推論。其一,若 X 是計數壞事件的非負整數值隨機變數且 E[X] < 1,則 P(X = 0) > 0,因為 E[X] >= 1 * P(X >= 1) 意味著 P(X >= 1) <= E[X] < 1;故存在沒有壞子結構的組態。這其實就是披著期望外衣的聯集界,因為由線性性 E[X] = 各個壞事件機率之和,與這些事件之間是否相依無關——期望的線性性不需要獨立性,這正是其力量的祕密。其二,同樣的單邊控制給出存在一個至少等於平均值的值:樣本空間中總有一點使 X >= E[X](也有一點使 X <= E[X]),所以要證明某物件的 X 很大,只需證明平均值很大。

期望線性性在沒有獨立性時依然成立,這是關鍵特性:即使壞事件的指示函數彼此高度相關,E[指示函數之和] = E[各指示函數]之和 仍嚴格成立。這使該方法能毫不費力地處理重疊的團、相交的集合或相關的邊。誠實的限制是第一動差是單邊的:E[X] 小強制 P(X = 0) > 0,但 E[X] 大本身並不強制 P(X > 0) > 0,因為所有質量可能集中在一個取值巨大的罕見事件上。要證明某計數以高機率為正,你必須控制變異數——那是第二動差法的工作。

在隨機圖 G(n,p) 中,令 X 計數三角形的個數。C(n,3) 個三元組中每一個成為三角形的機率為 p^3,故由線性性 E[X] = C(n,3) p^3 ~ (np)^3 / 6,完全不必擔心三角形之間共用邊。若 p = c/n 且 c < 1,則 E[X] -> c^3/6 保持有界;若改為 np -> 0,則 E[X] -> 0,於是 P(X >= 1) <= E[X] -> 0,圖以趨於 1 的機率不含三角形。

期望的線性性不需要獨立性——即使各項重疊,第一動差仍可逐項計算。

E[X] -> 0 證明 X 以高機率為 0,但 E[X] -> 無窮並不證明 X 以高機率 >= 1:質量可能集中在取值巨大的罕見結果上。證明正性需要第二動差。

又称
the expectation methodMarkov's inequality argument期望值法