Chung–Erdős inequality
From HandWiki
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 [math]\displaystyle{ A_1,\ldots,A_n }[/math] be events. Assume that [math]\displaystyle{ \Pr[A_i]\gt 0 }[/math] for some [math]\displaystyle{ i }[/math]. Then
- [math]\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] }. }[/math]
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)).
References
- ↑ 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. doi:10.1090/S0002-9947-1952-0045327-5. ISSN 0002-9947.
- ↑ Petrov, Valentin Vladimirovich (1995-01-01). Limit theorems of probability theory : sequences of independent random variables. Clarendon Press. OCLC 301554906.
 |  |
