從取平均到計數
上一篇透過取平均讓存在性變得廉價：若某量的期望值至多為 c，那麼必有某個結果達到至多 c，因為沒有任何隨機變數能處處嚴格高於自身的均值。一階動差法就是這個想法針對計數的紀律化形式。你建造一個非負、取整數值的計數 X——同色三角形的個數、壞邊的個數、某固定子圖的拷貝數——然後直接從 E[X] 讀出存在或不存在。整套方法都立基於一條初等不等式與一條你早在第一冊就握有的恆等式。
那條不等式是特化到整數的 馬可夫不等式：對非負整數 X，事件 X >= 1 即事件 X != 0，而 P(X >= 1) <= E[X]。其逆否命題正是引擎：若 E[X] < 1，則 P(X = 0) > 0，於是必存在一個 X = 0 的結果。這就是整條一階動差原理——欲證某個沒有壞部件的物件存在，就在一個隨機物件中計數壞部件，並證明其平均計數低於一。讓 E[X] 可算的那條恆等式是 期望的線性性：把 X 寫成指示函數之和 X = sum over i of 1_{A_i}，於是 E[X] = sum over i of P(A_i)，無需任何獨立性。
一階動差實戰：拉姆齊，繼以刪除法
最乾淨的範例是拉姆齊數下界。把 N 個頂點的完全圖每條邊獨立地以機率 1/2 塗成紅或藍。令 X 計數 k 個頂點之完全圖的同色拷貝。由線性性，E[X] = C(N, k) 乘以 2 乘以 2^(-C(k,2))，因為 C(N,k) 個候選 k-集中，每一個為全紅或全藍的機率是 2 乘以 2^(-C(k,2))。若此期望低於 1，則某種著色滿足 X = 0——一種沒有同色 k-團的著色——這就是說拉姆齊數 R(k,k) > N。對 N 最佳化便得 R(k,k) > (1 + o(1)) (k / (e sqrt 2)) 2^(k/2)，這是 1947 年的下界，而令人驚異的是，至今沒有任何明確構造在領頭常數上超越它。
赤裸的一階動差往往略嫌粗糙：E[X] 稍稍高於 1，於是你無法在任何地方斷言 X = 0。刪除法（又稱更動法）以第二步動作來搭救你。選取隨機物件，接受它有少數壞部件，然後針對每個壞部件精準地移除一個頂點或一個元素，把它們全數摧毀。存活下來的是一個乾淨物件，其大小等於原大小減去刪除次數，而你以 E[X] 界住期望刪除次數。刪除法因此能證明一個大型乾淨結構的存在，即使要求一個完整大小、毫無瑕疵的結構已是奢望。
- 抽樣隨機物件（一個 2-著色、一個隨機圖、一個隨機子集），並令 X 計數壞部件。
- 以線性性把 E[X] 算成 sum of P(壞部件 i 出現)——不需獨立性。
- 每個壞部件刪去一個元素；存活的物件是乾淨的，其期望大小至少為（初始大小）減去 E[X]。
- 必有某結果達到期望，故存在該大小的乾淨物件——選取初始大小，使存活大小盡可能地大。
二階動差法：從正期望到正機率
現在假設 E[X] 很大，而你想斷言的不只是 X 可以為正，而是 X > 0 以高機率成立——例如，一個隨機圖幾乎必然包含某給定子圖。光是均值大並不足夠：彩券有正的期望報酬，卻幾乎總是分文不付，因為它的全部質量是「一筆巨額的微小機會」。對策是控制離散程度。二階動差法藉由方差排除這種彩券式行為，做法是把 柴比雪夫不等式套用在事件 X = 0 上。
關鍵估計很短：若 X = 0，則 X 偏離其均值整整 E[X]，故由柴比雪夫 P(X = 0) <= P(|X - E[X]| >= E[X]) <= Var(X) / E[X]^2。於是只要方差相對於均值平方很小——亦即 Var(X) = o(E[X]^2)——X 消失的機率便趨於零，X > 0 以高機率成立。比值 Var(X) / E[X]^2 就是全部關鍵；它正是變異係數的平方，是「計數圍繞其平均有多集中」這件事的無量綱度量。
X = sum_i 1_{A_i} a count of indicator events
E[X] = sum_i P(A_i) (linearity, no independence)
Var(X) = sum_i Var(1_{A_i}) + sum_{i != j} Cov(1_{A_i}, 1_{A_j})
P(X = 0) <= Var(X) / E[X]^2 (second moment / Chebyshev)
=> if Var(X) = o(E[X]^2) then X > 0 with high probability計算 Var(X) 之處，相依性終於要你付出代價。把 X 寫成指示函數之和並展開，由你在第一冊見過的協方差雙線性性，Var(X) = sum of Var(1_{A_i}) 加上 sum over ordered pairs i != j of Cov(1_{A_i}, 1_{A_j})。對角項無害；非對角的協方差項才是全部的難處，而它們恰恰在兩個壞部件傾向同時出現時為正。二階動差法之所以有效，正是當這些相關性很弱——當得知一個事件已發生幾乎不抬高另一個事件的機會——這也是為何它是稀疏、近乎獨立的隨機結構的天然搭檔。
兩種動差合用：隨機圖中的門檻
當你研究一個性質如何隨參數增大而開啟時，這兩種方法便合為單一儀器。在 愛多斯-雷尼隨機圖 G(n, p) 中，C(n,2) 條邊各以機率 p 獨立存在，我們追問：對哪些 p，固定子圖 H 會出現？令 X = G(n, p) 中 H 的拷貝數。一階動差給出上半：若 E[X] -> 0，則由馬可夫 X = 0 以高機率成立，故 H 幾乎必然缺席。二階動差給出下半：若 E[X] -> infinity 且 Var(X) = o(E[X]^2)，則 X > 0 以高機率成立，故 H 幾乎必然出現。p 的交越值就是門檻。
對一個平衡子圖 H，設其有 v 個頂點與 e 條邊，則 E[X] 約為 n^v p^e 量級，在 p = n^(-v/e) 附近跨過 1。微妙之處在於：門檻並非由 H 本身、而是由它最稠密的子圖所主宰：真正要緊的指數是 e(H') / v(H') 在子圖 H' 上的最大值，即最大子圖密度 m(H)，門檻落在 p = n^(-1/m(H))。理由恰恰是上面的協方差計算——共享一塊稠密公共部件的 H 拷貝，正是那些可能炸開 Var(X) 的強相關對，而最稠密子圖正是這個危險最大之處。這是單調性質門檻的典範範例。
Paley-Zygmund、期望門檻，以及前路所向
柴比雪夫是通往下界的教科書路線，但有一件更銳利、往往也更順手、用同樣兩種原料的工具。Paley-Zygmund 不等式說，對非負的 X 與任意 0 <= t <= 1，P(X >= t E[X]) >= (1 - t)^2 乘以 E[X]^2 / E[X^2]。令 t -> 0 得 P(X > 0) >= E[X]^2 / E[X^2]，這是一個直接以前兩階動差表出的、關於正性機率的乾淨下界。當二階動差與一階動差的平方可比時，此機率便有離零的下界——而其加強版可還原二階動差法的高機率結論。它是下一階梯諸集中不等式的天然反集中夥伴。
兩種方法都引出一個揮之不去的問題：一階動差作為門檻的預測者有多緊？一階動差給出性質出現的必要條件——E[X] 至少不能消失——而「此必要條件本質上也充分」這個啟發式，正是 Kahn 與 Kalai 著名的期望門檻猜想的內容。它斷定：任何遞增性質的真實門檻，都落在那個易算的期望門檻的一個對數因子之內。此問懸而未決達二十年，終於獲證（Park-Pham 定理，2022），這是個驚人的確認：一階動差的直覺鮮少大錯。但要誠實：那道間隙確實是一個對數因子，而非零。
當事件稀疏卻並非可忽略地相關時，二階動差就太鈍了——非對角的協方差堆積起來，界便瓦解。本階梯其餘各篇恰恰是這些升級。當相依是局部的，洛瓦茲局部引理（下一篇）即使在聯集界與一階動差雙雙失靈時，仍能保證正機率。當你想要的是 X 的尖銳尾端控制、而不只是 P(X = 0)，Janson 不等式與 Azuma 的鞅方法便接手。而當你想要一個稀疏計數的完整極限分布——譬如一個 卜瓦松極限——那就是最後一篇的 Stein-Chen 方法。兩種動差正是這一切所立基的根本。