Hoeffding 不等式與和的集中性

從單一變數走向一整個和

在上一篇講中，你把 Chernoff 界磨利了：不用平均數（馬可夫）或變異數（柴比雪夫）去框尾巴，而是把整個動差生成函數餵進馬可夫不等式，得到一條「以指數速度」下墜的尾巴。Chernoff 的食譜是「對旋鈕 t 做最佳化，看著界限崩塌」。Hoeffding 不等式正是這套食譜全額兌現的那一刻。它接過一個由許多獨立、有界的隨機變數構成的和，回送給你一條乾淨的指數尾巴——不需要任何分配的細節，只要知道每個變數活在什麼範圍裡。

想想統計學裡最平凡的東西：一個和，或它的表親平均數。設 X_1, X_2, ..., X_n 互相獨立，令 S = X_1 + ... + X_n 是它們的和。大數弱定律早已告訴你，那個「平均數」S/n 會穩定地趨向它的平均——但它對速度語焉不詳，只承諾偏離的機率「最終」會趨於零。Hoeffding 把這個缺口補上，給你一個真的能用的數字：對你任選的任何偏離量 t，它都給出 P(S - E[S] >= t) 一個具體、指數級小的上限。它把「最終會集中」變成「會集中到『這麼』緊、『這麼』快」。

不等式本身

Hoeffding 唯一需要的假設來了，而且便宜得驚人：每個 X_i 都是有界的，住在某個區間 [a_i, b_i] 之內。你不需要知道它的平均、變異數、形狀——只要知道它跑不出那個範圍。在這唯一條件下，Hoeffding 不等式說：P(S - E[S] >= t) <= exp(-2 t^2 / sum_i (b_i - a_i)^2)。每個變數的全部個性都被壓縮進一個數字——它的範圍寬度 (b_i - a_i)。範圍寬的變數提供了很多可以亂跑的空間；被緊緊框住的變數幾乎不提供。

把指數慢慢讀，因為意義全在裡面。偏離量 t 是「平方」地坐在分子上，所以這個界對你跑多遠極度敏感——把偏離量加倍，指數離零的距離就只剩四分之一，把機率壓得粉碎。分母上坐的是總平方範圍。若每個變數都共用同一個寬度為 c 的範圍，那分母就成了 n * c^2，界限便是 exp(-2 t^2 / (n c^2))。要把「平均數」的偏離固定住，你設 t = n*epsilon，指數就變成 -2 n epsilon^2 / c^2——這個界限「本身」就隨 n 指數縮小。這正是大數弱定律所缺的那顆量化心臟。

Hoeffding (one-sided), X_i independent, a_i <= X_i <= b_i :

    P( S - E[S] >= t )  <=  exp( -2 t^2 / sum_i (b_i - a_i)^2 )

For the average of n equal-range variables (width c), with t = n*eps:

    P( S/n - mean >= eps )  <=  exp( -2 n eps^2 / c^2 )

Two-sided (both tails):  multiply the right-hand side by 2.

  eps^2  on top  -> tiny deviations are cheap, big ones vanish fast
  n      on top  -> more data => exponentially tighter
  c^2    below   -> wider variables => looser bound

Hoeffding 不等式，指數中的每一塊都標上它所控制的東西。

一個小小的民調實作

讓我們用最熟悉的有界變數把它落實：一個是非題的答案。每位受訪者給出一個指示隨機變數 X_i，「是」為 1、「否」為 0，因此 a_i = 0、b_i = 1，範圍寬度恰好是 1。平均數 S/n 就是觀測到的「是」票比例，它的平均則是真實的母體比例 p。我們想知道：用 n = 1000 人，我們的民調偏差超過 5 個百分點（epsilon = 0.05）的可能性有多大？

辨認範圍。每個 X_i 在 [0, 1] 內，所以 c = b_i - a_i = 1，分母總和為 n * c^2 = 1000。
選定平均數的偏離量：epsilon = 0.05，因此和的偏離量為 t = n*epsilon = 1000 * 0.05 = 50。
代入指數：-2 t^2 / (n c^2) = -2 * (50)^2 / 1000 = -2 * 2500 / 1000 = -5。
單尾：P(S/n - p >= 0.05) <= e^(-5) ≈ 0.0067。雙尾（任一方向偏離 5 個百分點）：乘以 2，約 0.013。

所以只用一千人，偏離五個百分點以上的機率就低於約 1.3%——而且注意，我們從頭到尾都不需要知道 p。這個「與 p 無關」的保證，正是這套論證能撐起真實民調誤差範圍、A/B 測試的停止規則，以及機器學習泛化界的原因：你在不知道想估計的答案的情況下，就把最壞情形框住了。想要更緊的保證？因為 n 坐在指數裡，把它翻四倍到 n = 4000，指數就跑到 -20、尾巴跑到 e^(-20)，一個小到近乎無法想像的數。在這個範疇裡，可靠度很「便宜」——這就是指數集中性的禮物。

為什麼要有界？次高斯與引擎內部

為什麼有界就能撐起這一切？藏在引擎蓋下的引擎，是上一篇那套 Chernoff 機制，逐塊套用到每一個部分。關鍵事實（Hoeffding 引理）是：住在 [a, b] 裡的有界變數是次高斯的——它的動差生成函數被一個變異數來自範圍的高斯所控制。一個次高斯隨機變數，就是尾巴衰減至少和常態一樣快的變數。接著獨立性讓各個 MGF 相「乘」，範圍寬度在指數裡相「加」，再由那一次對 t 的 Chernoff 最佳化把界封住。有界，不過是「次高斯」最乾淨的充分條件。

這也誠實地告訴你 Hoeffding 在哪裡「止步」。若某變數無界、又是重尾——收入、保險理賠，任何由一個罕見的巨大值主宰的東西——那麼 MGF 可能根本不存在，次高斯性失效，Hoeffding 就是用不上。（回想Chernoff 界至少需要 MGF 存在，而有些分配根本沒有 MGF，儘管特徵函數永遠存在。）遇上這種情形，你會改用只需變異數的工具，例如柴比雪夫，或改用中央極限定理——但中央極限定理本身需要「有限變異數」，對柯西分配更是出了名地失效。天下沒有白吃的午餐：更強的結論要拿更強的假設來換。

當獨立性彎曲時：Azuma 與鞅

Hoeffding 唯一的硬性要求是獨立——各部分不能互相牽動。但許多真實過程並不是乾淨的獨立部分之和：一個一步步累積的量，每一步都依賴至今的歷史。了不起的是，只要那個進行中的過程是一個鞅（martingale），你仍然能得到一條 Hoeffding 形狀的指數尾巴。鞅是這樣一種序列：它是「公平的」，意思是給定至今的一切，下一步變化的期望值為零（一場公平賭局裡的財富，平均而言既不上漂也不下漂）。

Azuma-Hoeffding 不等式說：若一個鞅的步伐有界（每個增量住在寬度為 c_i 的範圍裡），那麼同一條指數尾巴依然成立，P(偏離 >= t) <= exp(-2 t^2 / sum_i c_i^2)。形狀一模一樣，只是把「獨立變數」換成「有界的鞅增量」。正是這一項推廣，讓集中性論證遠遠超出簡單的和，伸進演算法、隨機圖，以及任何「每步只改變一點點、且沒有任何一步主宰全局」的量。Hoeffding 是那道門；Azuma 是它通往的那條長廊。

退一步，把整個階段看成一道樓梯。馬可夫只用平均；柴比雪夫加上變異數、給出大數弱定律；Chernoff 餵進完整的 MGF 換來指數尾巴；Hoeffding 把它變成對「有界變數之和」乾淨且不依賴分配的界；Azuma 再把獨立性放寬成「有界增量的鞅」。每一階都保留同一副「對巧妙變換施以馬可夫」的骨架，卻換到更銳利或更寬廣的結論。接下來，最後一篇講會用指數的銳利度去換取純粹的廣度——謙遜的聯集界與 Borel-Cantelli 引理，它們能一次掌控無窮多個事件。