切比雪夫不等式（Chebyshev's inequality）
/ CHEB-ih-shev /
想像兩間工廠以相同平均長度製造螺栓。一間馬虎，長度大幅波動；另一間穩定。若你隨手抓一支螺栓，穩定工廠的那支更可能接近目標。切比雪夫不等式把這個直覺變成保證：一個量越緊密地聚集在它的平均附近——變異數越小——它偏離得遠的機率就越低。
精確地說：對任意均值為 mu、變異數為 sigma^2 的隨機變數 X，與任意 t > 0，Pr[ |X - mu| >= t ] <= sigma^2 / t^2。令 t = k sigma 得到好記的形式 Pr[ |X - mu| >= k sigma ] <= 1/k^2——對任何分布而言，偏離平均超過 k 個標準差的情形，最多只占 1/k^2 的時間。證明其實就是偽裝的馬可夫：把馬可夫不等式用在非負變數 (X - mu)^2 上（其均值恰為 sigma^2），門檻取 t^2；Pr[(X - mu)^2 >= t^2] <= sigma^2 / t^2，而 (X - mu)^2 >= t^2 與 |X - mu| >= t 是同一個事件。因為它用了變異數，切比雪夫以 1/k^2 縮小，遠快於馬可夫的 1/k。
當你能計算或界定變異數時，切比雪夫是自然的下一個工具——例如當你的量是兩兩獨立（不必完全獨立）指示變數之和，變異數可以漂亮地相加。它支撐了通用雜湊碰撞數的分析與許多抽樣估計。誠實的提醒：它對稱且不依賴分布，所以保守；當你的變數是許多獨立片段之和時，切爾諾夫會利用那個結構，給出隨 k 指數縮小的界，大幅勝過切比雪夫的多項式 1/k^2。
假設某估計值均值為 100、標準差為 5。切比雪夫保證該估計落在 3 個標準差內，也就是 85 到 115 之間，至少 1 - 1/3^2 = 8/9 的時間——超過 88%——而且對分布的形狀不作任何假設。
Pr[偏離至少 k 個標準差] <= 1/k^2——變異數買到比馬可夫更銳利的尾界。
切比雪夫要求變異數存在且有限；它也是雙邊且不依賴分布，因此常常寬鬆。對於許多獨立變數之和，切爾諾夫的指數尾界遠比切比雪夫的 1/k^2 緊。