Chung–Erdős inequality explained

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 … \vee} A _{n] \geq (\left(\sum ^{n} _{i =1} \Pr[A ^{2} _{i]\right)})/(\sum ^{n} _{j =1} \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

A _{i} which occur.

Notes and References

1. Chung. K. L.. Erdös. P.. 1952-01-01. On the application of the Borel–Cantelli lemma. Transactions of the American Mathematical Society. 72. 1. 179–186. 10.1090/S0002-9947-1952-0045327-5. 0002-9947. free.
2. Book: Petrov, Valentin Vladimirovich. Limit theorems of probability theory : sequences of independent random variables. 1995-01-01. Clarendon Press. 301554906.