Paper 1, Section II, F

Probability | Part IA, 2020

Let A1,A2,,AnA_{1}, A_{2}, \ldots, A_{n} be events in some probability space. State and prove the inclusion-exclusion formula for the probability P(i=1nAi)\mathbb{P}\left(\bigcup_{i=1}^{n} A_{i}\right). Show also that

P(i=1nAi)iP(Ai)i<jP(AiAj)\mathbb{P}\left(\bigcup_{i=1}^{n} A_{i}\right) \geqslant \sum_{i} \mathbb{P}\left(A_{i}\right)-\sum_{i<j} \mathbb{P}\left(A_{i} \cap A_{j}\right)

Suppose now that n2n \geqslant 2 and that whenever iji \neq j we have P(AiAj)1/n\mathbb{P}\left(A_{i} \cap A_{j}\right) \leqslant 1 / n. Show that there is a constant cc independent of nn such that i=1nP(Ai)cn\sum_{i=1}^{n} \mathbb{P}\left(A_{i}\right) \leqslant c \sqrt{n}.

Typos? Please submit corrections to this page on GitHub.