組合學中的集中性：Azuma 與 Janson

為何僅有平均值還不夠

本階梯前面幾篇計算了組合隨機變數的期望與變異數——G(n,p) 中三角形的個數、最大獨立集的大小、色數。但知道 E[X] 甚至 Var(X) 仍留有落差：平均值與劇烈擺動是相容的，而二階矩法透過切比雪夫不等式只給出多項式強度的控制。對最困難的問題，我們想要的是集中性：X 不僅在平均意義下、而且以指數速度趨於 1 的機率，落在其均值附近一個極窄的窗口內。這就是「色數平均而言約為 k」與「色數以壓倒性機率為 k 或 k+1」之間的差別。

Vol I 給了你獨立變數之和的集中性——Hoeffding 與 Chernoff 界——但組合量通常並非獨立事物之和。三角形個數是一堆強相依指示函數之和；色數則是所有邊的一個糾纏的全域函數。組合集中性的技藝，在於找出藏在那份相依性裡的正確結構。兩種結構主宰本篇。第一是鞅：即使一個複雜的函數，也會一次一個座標地揭露其隨機性，而那個逐步的條件期望就是我們能控制的鞅。第二是單調事件的特殊代數，它讓 Janson 不等式把一個近 Poisson 的啟發式變成貨真價實的指數下尾界。

Azuma 不等式與曝露鞅

引擎是 Azuma 不等式，即 Hoeffding 的鞅推廣。設 M_0, M_1, ..., M_n 是一個增量有界的鞅，對每個 k 有 |M_k - M_(k-1)| <= c_k。則對任意 t > 0，P(|M_n - M_0| >= t) <= 2 * exp(-t^2 / (2 * sum_k c_k^2))。其假設恰有兩條：它必須是真正的鞅（E[M_k given F_(k-1)] = M_(k-1)），且增量必須幾乎必然有界。不需要獨立性——鞅結構本身就一步一步地內建了「公平性」，而其證明，正是把 Hoeffding 式對 E[e^(theta(M_k - M_(k-1)))] 的界條件地施用、再透過塔性質串接起來。

我們如何從色數這類靜態的量中弄出一個鞅？用 Doob 曝露鞅。設 X = f(Z_1, ..., Z_n) 是獨立隨機片段 Z_1, ..., Z_n 的任一函數，定義 M_k = E[X given Z_1, ..., Z_k]，即前 k 個片段曝露之後對 X 的最佳猜測。由構造 M_0 = E[X]、M_n = X，而塔性質使 M_k 成為一個 Doob 鞅。我們製造出了一個從均值出發、終於隨機變數本身的鞅，因此只要能界定增量，Azuma 便能界定 X = M_n 偏離 E[X] = M_0 的程度。在圖上，Z_k 有兩個典範選擇，給出頂點曝露鞅與邊曝露鞅。

McDiarmid 與色數

把曝露鞅一勞永逸地封裝起來，便得到有界差不等式，也稱 McDiarmid 不等式——這才是你實務上真正會去取用的形式。設 X = f(Z_1, ..., Z_n)，其中 Z_k 獨立，且 f 滿足有界差條件：固定其餘座標、只改變任一單一座標 Z_k，至多使 f 改變 c_k。則 Doob 增量被 c_k 界住、Azuma 適用，於是 P(|X - E[X]| >= t) <= 2 * exp(-t^2 / (2 * sum_k c_k^2))。你再也無需提及鞅；只要驗證 f 上一個 Lipschitz 型的條件，便能讀出界。這是組合學中使用頻率最高的集中性工具。

皇冠上的明珠是色數的集中性。令 X = chi(G(n,p))。採用頂點曝露：揭露一個新頂點（連同它到先前頂點的所有邊）至多使色數改變 1，因為這個新頂點至多需要一種額外的顏色。故全部 n 個增量皆滿足 c_k = 1，McDiarmid 給出 sum_k c_k^2 = n，於是得 P(|chi(G(n,p)) - E[chi]| >= t) <= 2 * exp(-t^2 / (2n))。取 t = lambda * sqrt(n) 即知chi 集中在其均值的 O(sqrt(n)) 範圍內。這是 Shamir 與 Spencer 的定理，其了不起之處在於它不需要什麼：我們得到了尖銳的集中性結果，卻幾乎完全不知道 E[chi] 究竟等於多少。

Janson 不等式：子圖計數的下尾

Azuma 是對稱而普適的；它不知道「完全沒有三角形」是特殊的。對典範的組合問題——G(n,p) 不含固定子圖 H 的任何副本的機率是多少？——二階矩法能證明在閾值以上計數以高機率為正，但只給多項式的控制。Janson 不等式正是把這升級為尖銳指數下尾界的工具。架好標準框架：令 {A_i}_(i in I) 為一族事件，每個 A_i 表示「H 的某個特定副本存在」，並令 X = sum_i 1_(A_i) 為副本數。當 A_i 與 A_j 相依（其邊集重疊）時記 i ~ j，並定義 mu = E[X] = sum_i P(A_i) 以及 Delta = sum_(i ~ j) P(A_i and A_j)，即成對重疊的總和。

Janson's inequality  (events A_i increasing in the same independent coords):

  mu    = sum_i  P(A_i)                     (mean number of copies)
  Delta = sum_{i ~ j, i < j}  P(A_i & A_j)  (ordered-pair dependency sum)

  P( X = 0 ) = P( no A_i occurs )  <=  exp( - mu + Delta )

Generalized Janson (lower tail, 0 <= t <= mu):

  P( X <= mu - t )  <=  exp( - t^2 / ( 2 (mu + Delta) ) )

  regime Delta = o(mu)  (sparse / few overlaps)  =>  P(X = 0) ~ e^{-mu}
  regime Delta >> mu    (heavy overlaps)         =>  use Delta-corrected
                                                    bound  e^{-mu^2/(2 Delta)}

Janson 用 e^(-mu+Delta) 界定零副本的機率；當重疊可忽略時，這還原了 Poisson 啟發式 P(X=0) ~ e^(-mu)。

圖像很乾淨。若這些事件獨立，我們會有 P(X = 0) = prod_i (1 - P(A_i)) <= exp(-sum_i P(A_i)) = e^(-mu)，即稀有事件精確的 Poisson 近似。Janson 說相依性只讓你付出修正因子 e^(Delta)：P(X = 0) <= e^(-mu + Delta)。因此只要重疊項 Delta 相對於 mu 很小，答案本質上就是獨立情形的 e^(-mu)，如今是一個嚴格的界而非啟發式。這正是二階矩搆不著的下尾：它把「X 通常為正」轉化為「X 為零的機率至多 e^(-mu(1 - o(1)))」，指數地小。

兩點誠實話界定其適用範圍。其一，Janson 要求 A_i 是同一組獨立座標上的遞增事件——G(n,p) 中的存在邊——如此證明才能用上 FKG／Harris 正相關，即遞增事件彼此相助；它不是處理任意相依事件的工具。其二，界 e^(-mu+Delta) 只在 Delta = O(mu) 時有用；一旦 Delta 壓過 mu 它便空洞，此時你改用廣義 Janson 界 e^(-mu^2/(2*Delta))，它在重度重疊區仍有意義。判斷你身處哪個區間——把子圖計數變異數項 Delta 與 mu 相比——正是整個技藝所在。

選擇你的工具，以及本階梯的去向

這兩個工具回答的是不同形狀的問題，把它們匹配好，正是本篇的實用課題。

X 是否為許多獨立座標的一個全域 Lipschitz 函數（色數、最大獨立集、最長遞增子序列）？取用曝露鞅與 McDiarmid——你能免費得到圍繞均值的雙側集中性，即使不知道均值。
你是否特別需要某種小型子結構計數的下尾——看到比期望更少、甚至完全沒有副本的機率？取用 Janson；它在對稱的 Azuma 界太弱之處恰好尖銳，捕捉到「無副本」的 e^(-mu) 衰減。
在信任 Janson 之前先核對重疊預算：計算 mu 與 Delta。若 Delta = o(mu)，答案是乾淨的 Poisson e^(-mu)；若 Delta >> mu 則改用廣義形式 e^(-mu^2/(2 Delta))。
若 McDiarmid 的 sum_k c_k^2 被少數稀有的壞座標主宰，升級到 Talagrand 的凸距離不等式，它只對實際發生的增量收費——本階梯中 Azuma 更銳利的後繼者。

把這兩者擺在本階梯其餘部分旁邊。一階矩與二階矩法定位一個性質在何處開啟；Azuma 與 Janson 隨後證明它尖銳地開啟，失敗機率指數地小。第 3 篇的 Lovász 局部引理攻擊的是互補的問題——在稀疏相依條件下同時避開許多壞事件——那裡 Janson 的遞增事件假設並不適用。而 Janson 萃取出的下尾常數 e^(-mu)，正是本階梯最後一篇將從根本原理解釋的 Poisson 印記：當許多稀有、弱相依的事件結合，計數近似 Poisson，而 Stein 方法把「近似」轉化為對到 Poisson 律距離的定量界。集中性告訴你一個量幾乎不動；Stein 方法則告訴你那殘留的微小擺動的確切形狀。