Chung–Erdős inequality
# 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 $A_{1},\ldots ,A_{n}$ be events. Assume that $\Pr[A_{i}]>0$ for some $i$. Then

    $\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)).

