Azuma 鞅方法（Azuma martingale method）
/ ah-ZOO-mah /
Azuma 鞅方法是 McDiarmid 與多數函數集中結果底下的引擎室：一種為「逐次揭露一塊資訊」的量證明集中的方法。其想法是不直接思考一個複雜的隨機變數，而是追蹤當你對越來越多底層隨機性取條件時，其條件期望如何演變。每塊新揭露的資訊以一個鞅增量推動該條件期望，若這些增量有界，則總漂移受到尖銳控制。
Azuma-Hoeffding 不等式：若 (M_0, M_1, ..., M_n) 是鞅（E[M_k | F_{k-1}] = M_{k-1}），其增量有界，幾乎必然 |M_k - M_{k-1}| <= c_k，則 P(M_n - M_0 >= t) <= exp(-t^2 / (2 sum_k c_k^2))，雙邊帶因子 2。證明是 Hoeffding 論證的條件版本：每個增量是有界、條件均值為零的變數，故其條件動差母函數滿足 E[exp(lambda(M_k - M_{k-1})) | F_{k-1}] <= exp(lambda^2 c_k^2 / 2)（條件次高斯界），這些經由塔性質相乘，把 M_n - M_0 的動差母函數界定為 exp(lambda^2 sum c_k^2 / 2)。然後 Chernoff。要集中一個函數 f(X_1,...,X_n)，可建構杜布鞅 M_k = E[f | X_1, ..., X_k]，它隨輸入逐一揭露而從 M_0 = E[f] 插值到 M_n = f；f 的有界差分直接轉化為有界鞅增量，從而回到 McDiarmid。
此方法的威力在於它從不需要 X_i 在「變數之和」意義上獨立——它只需要濾過（遞增的 σ-代數序列）與有界增量，因此能集中馬可夫鏈的路徑泛函、線上演算法，以及隨機圖上的探索過程（頂點與邊揭露鞅）。誠實的提醒與 McDiarmid 相同：Azuma 只用最壞情形增量界 c_k，故對小的條件變異數視而不見。更尖銳的 Freedman 不等式是 Bernstein 的鞅類比——它以可預測二次變差 sum E[(M_k - M_{k-1})^2 | F_{k-1}] 取代 sum c_k^2，為鞅找回變異數感知的速率，正是增量通常小卻偶爾大時所用者。
逐一揭露 Erdos-Renyi 圖 G(n, p) 的 n^2 條潛在邊，令 f 為色數。增刪一條邊至多使色數改變 1，故邊揭露杜布鞅的增量 c_k = 1，Azuma 給出 P(|chi - E[chi]| >= t) <= 2 exp(-t^2 / (2 binom(n,2)))，因此 chi 集中在其均值的 O(n) 範圍內——即便 E[chi] 本身難以計算。
杜布鞅能集中你甚至算不出均值的量。
Azuma 以最壞情形界定增量（c_k），故忽略條件變異數——當增量通常很小時，改用 Freedman 不等式（鞅版 Bernstein）。鞅的增量須幾乎必然有界；僅以機率有界並不足夠。