In probability theory, the Chung–Erdős inequality provides a lower bound on the probability that one out of many (possibly dependent) events occurs. The lower bound is expressed in terms of the probabilities for pairs of events. Formally, let A 1 , … , A n {\displaystyle A_{1},\ldots ,A_{n}} be events. Assume that Pr [ A i ] > 0 {\displaystyle \Pr[A_{i}]>0} for some i {\displaystyle i} . Then
Pr [ A 1 ∨ ⋯ ∨ A n ] ≥ ( ∑ i = 1 n Pr [ A i ] ) 2 ∑ i = 1 n ∑ j = 1 n Pr [ A i ∧ A j ] . {\displaystyle \Pr[A_{1}\vee \cdots \vee A_{n}]\geq {\frac {\left(\sum _{i=1}^{n}\Pr[A_{i}]\right)^{2}}{\sum _{i=1}^{n}\sum _{j=1}^{n}\Pr[A_{i}\wedge A_{j}]}}.}
The inequality was first derived by Kai Lai Chung and Paul Erdős (in, equation (4)). It was stated in the form given above by Petrov (in, equation (6.10)). It can be obtained by applying the Paley–Zygmund inequality to the number of A i {\displaystyle A_{i}} which occur.
References