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}] \ .\]