切爾諾夫限

切爾諾夫限，也稱為切爾諾夫不等式，是關於一組獨立隨機變量和的一類概率不等式.。是由赫爾曼-切爾諾夫而命名的。然而，切爾諾夫約束要求變量是獨立的，而與之相類似的馬爾科夫限和切比雪夫限都不需要。

對於隨機變量

定義的通用切爾諾夫不等式通過將馬爾可夫不等式應用於

來獲得，對於每一個

，

當是n個隨機變量

的時候，我們得到任何

，

優化

並使用

獨立的假設，

同樣的，

所以，

命題得證，以上不等式的一個重要意義在於，我們僅僅知道隨機變量的數字特徵便可以得到概率的界 ^[1]  。

令X₁，...，X_n是獨立的伯努利隨機變量，其總和為X，每個都具有等於1的概率p> 1/2。對於伯努利變量，

所以，

對於任何的

，由

和

可得，

利用切爾諾夫不等式可得，

同時發生事件

的

以上的概率具有精確的值，

這個概率的下限通過切爾諾夫不等式來計算，

最後得出，

以下定理是瓦西里·霍夫丁提出的，所以稱為切爾諾夫-霍夫丁定理。

假設X₁，...，X_n是隨機變量，取{0，1}中的值。令p = E [ X i ]，ε > 0。然後，

由於，

所以

假設X1，...，Xn是隨機變量，取{0，1}中的值。令X表示他們的和，

表示和的預期值，對於任何

，

類似的證明出，

上述公式在實踐中往往不方便，因此常常使用以下更簡單方便的界限：

設計統計實驗時出現設定的平衡問題。通常在設計統計實驗時，考慮到實驗中每個參與者的特徵，我們需要知道如何將參與者分成兩個不相交的組，使得每個特徵在兩組之間儘可能大致相等。

切爾諾夫限也用於獲得排列路由問題的緊密界限，在減少網絡擁塞的同時稀疏網絡中路由數據包。

切爾諾夫限可以有效地用於通過隨機化探索其擾動空間來評估應用算法的“魯棒性”級別。使用切爾諾夫限放棄不切實際的小擾動假設（擾動幅度很小）。魯棒性級別又可以用於驗證或拒絕特定的算法選擇，硬件實現或其結構參數受不確定性影響的解決方案的適當性。