機率方法

第二動差法(second moment method)

第二動差法是把單邊的第一動差法升級為雙邊陳述的工具:它證明一個非負計數隨機變數不僅在期望意義下很大,而且以高機率確實為正——並且常常集中在其平均值附近。它是隨機圖中門檻下界以及證明所求子結構通常存在(而非僅平均存在)的標準途徑。第一動差在 E[X] 小時證明 P(X = 0) 小,第二動差則在 E[X] 大時證明 P(X = 0) 小,前提是變異數受到良好控制。

其引擎是對計數 X 套用切比雪夫不等式。最簡潔的推論是界 P(X = 0) <= Var(X) / (E[X])^2。所以若變異數的階小於平均值平方——即 Var(X) = o((E[X])^2)——則 P(X = 0) -> 0,X 以趨於 1 的機率為正;事實上 X 會集中:X / E[X] -> 1(依機率)。整個任務歸結為估計變異數。把 X 寫成各子結構指示變數之和,Var(X) = 各共變異數之和,主導項來自彼此重疊(共用頂點或邊)的子結構對。當重疊對相對於 E[X]^2 的貢獻可忽略時,變異數受控,存在性隨之而來。

這正是人們釘住門檻位置的方式。對單調性質,第一動差給出下側(門檻以下期望計數消失,故性質失敗),第二動差給出上側(門檻以上計數集中且為正,故性質成立)。經典應用是固定子圖 H 在 G(n,p) 中的出現:仔細的變異數計算表明門檻由 H 中最稠密的子圖支配。誠實的提醒是:當少數非典型組態使變異數膨脹時,第二動差可能失效;在那些情況下人們會截斷、取條件,或升級為 Janson 不等式,後者對下尾給出指數而非僅僅多項式的控制。

G(n,p) 中三角形的門檻。令 X 計數三角形,E[X] ~ (np)^3/6。變異數由共用一條邊的三角形對主導,貢獻 ~ n^4 p^5。則 Var(X)/E[X]^2 ~ (n^4 p^5)/(n^6 p^6) = 1/(n^2 p) 再加 1/E[X]。兩者恰在 np -> 無窮 時 -> 0,故當 p >> 1/n 時圖以趨於 1 的機率含有三角形——與第一動差下界吻合,把門檻釘在 p ~ 1/n。

Var(X) = o(E[X]^2) 經由 P(X=0) <= Var(X)/E[X]^2 強制 X > 0(並集中)。

當罕見的高值組態主導變異數時,界 P(X=0) <= Var(X)/E[X]^2 可能很弱;此時需改用 Janson 不等式(下尾的指數控制)或截斷。

又稱
variance methodChebyshev argument二階動差法