切爾諾夫界（Chernoff bound）
/ CHER-noff /
若你擲一枚公正硬幣十次，出現九次正面並不令人驚訝。但擲一萬次卻得到 60% 正面就會令人瞠目——你平均的獨立擲幣越多，平均就越頑固地黏在二分之一上。切爾諾夫界把這種「人多勢眾」變精確：許多獨立隨機片段之和，極不可能（以指數小的機率）遠離它的期望值。
精確地說：令 X = X_1 + ... + X_n 為各自落在 [0,1] 的獨立隨機變數之和（常是獨立的 0/1 指示變數），均值 mu = E[X]。則對任意偏離比例 delta > 0，Pr[X >= (1 + delta) mu] 與 Pr[X <= (1 - delta) mu] 各自至多為一個指數小的量，對中等的 delta 大致是 exp(-mu delta^2 / 3)。關鍵字是指數：失敗機率以 e 的某個 mu 的負次方縮小，而非多項式。證明的巧思是：把馬可夫不等式不是用在 X 上，而是用在 e^(sX) 上（s > 0 巧妙選取）；因為 X_i 獨立，乘積 e^(sX) 的期望可分解成每個變數小項之積，再對 s 最佳化便得到指數界。獨立性正是讓那個分解合法的條件，也是整部引擎。
切爾諾夫是隨機分析的重砲。它解釋了為何隨機負載平衡器能讓每個桶都接近平均、為何把一個蒙地卡羅測試重複 k 次能讓錯誤指數下降、為何隨機抽樣估計會集中、為何近似演算法中的隨機捨入有效。它之所以重要，是因為它把「期望值」轉成「幾乎確定接近期望值」，這正是高機率保證所需。誠實的提醒：它要求獨立性（或近乎獨立）。對相依變數你必須退回切比雪夫或專門的鞅界（Azuma），而那些較弱；又指數中的常數隨你用的形式而異，請引用你所指的版本。
把 n 顆球均勻隨機丟進 n 個桶。任一桶的期望負載為 1，而切爾諾夫顯示某固定桶拿到超過約 3 log n / log log n 顆球的機率極小；接著對全部 n 個桶作聯集界，就證明了以高機率最忙的桶只裝 O(log n / log log n) 顆球。
獨立變數之和以指數般的緊度集中在它們的平均附近。
切爾諾夫的指數威力完全源自獨立性；拿掉它，這個界就失效。它正是為何「期望 O(...)」能升級為「以高機率 O(...)」的原因，但僅限於（近乎）獨立片段之和。