霍夫丁不等式（Hoeffding's inequality）
/ HUF-ding /
假設你把 n 個獨立的量測平均起來，每一個都保證落在某個已知範圍——比方一份民調，每個回答非 0 即 1。你的平均離真正的均值有多近，你又能多有信心？霍夫丁不等式給出一個乾淨、不依賴分布的答案：平均值離真值很遠的機率呈指數級微小，而你不必知道每個變數的形狀，只要知道它所處的區間。
敘述如下：令 X_1, ..., X_n 獨立，每個 X_i 被限制在區間 [a_i, b_i] 內，並令 S = X_1 + ... + X_n，均值為 E[S]。則 P(S - E[S] >= t) <= exp( -2 t^2 / 對 (b_i - a_i)^2 求和 )。下尾也有對稱的界，所以雙側偏離的機率至多是它的兩倍。在常見情形中，每個變數落在 [0, 1] 且你看的是平均而非總和，這就變成著名的 P(|平均 - 真均值| >= epsilon) <= 2 exp(-2 n epsilon^2)。其證明是柴諾夫方法再加上「霍夫丁引理」，後者說有界變數的 MGF 不大於範圍相符的高斯分布之 MGF。
這是統計學習理論與樣本數計算的骨幹：它告訴你需要多少樣本 n，才能讓你的經驗估計以 1 - delta 的信心落在真值的 epsilon 之內——解 2 exp(-2 n epsilon^2) <= delta 即可。關鍵假設是獨立與有界。誠實的侷限：霍夫丁忽略了變異數，即使變數通常很小，也按整個範圍 (b - a)^2 向你收費。當真實變異數遠小於範圍時，伯恩斯坦不等式給出更銳利的界。
你訪問 n 個人，每人回答 0 或 1（故範圍為 1）。若要以 95% 信心落在真實比例的 epsilon = 0.03 之內，令 2 exp(-2 n (0.03)^2) <= 0.05，得 n >= ln(40) / (2 (0.03)^2) ≈ 2050。約 2050 名受訪者就夠了，無論未知的真實比例為何。
對有界的獨立項，平均的偏離機率呈指數級微小——並告訴你所需的樣本數。
霍夫丁需要有界與獨立，且它只用範圍而非變異數——所以當變數通常很小時可能浪費。對低變異數的情形，宜用伯恩斯坦。