Lesson 1

In many applications, we have a set of “bad” events \(A_{1}, \dotsc, A_{n}\) and we want to show that it is possible that none of them occur. To do this, we show that \[\Pr\left[ \bigcap_{i \in [n]}\overline{A}_{i}\right]>0 \ .\] There are two simple ways to estimate such a probability:

1. Using the union bound: if the sum of the probabilities of all bad events is less than one, then with nonzero probability none of them occur: \[\Pr\left[ \bigcap_{i \in [n]}\overline{A}_{i}\right]=1-\Pr\left[ \bigcup_{i \in [n]}A_{i}\right] \ge 1-\sum_{i \in [n]}\Pr[A_{i}] \ .\]
2. If \(A_{1}, \dotsc, A_{n}\) are mutually independent, then \[\Pr\left[ \bigcap_{i \in [n]}\overline{A}_{i}\right] = \prod_{i \in [n]}\Pr[\overline{A}_{i}] \ .\]