Chung–Erdős inequality

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 ${\displaystyle A_{1},\ldots ,A_{n}}$ be events. Assume that ${\displaystyle \Pr[A_{i}]>0}$ for some ${\displaystyle i}$. Then

${\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,^[1] equation (4)). It was stated in the form given above by Petrov (in,^[2] equation (6.10)). It can be obtained by applying the Paley–Zygmund inequality to the number of ${\displaystyle A_{i}}$ which occur.