Lesson 1

The probability of the union of two or more events is found in the same way as the size of the union: \[\begin{align*}\Pr[A \cup B]&=\Pr[A]+\Pr[B]-\Pr[A \cap B] \ ,\\ \Pr\left[\bigcup_{i=1}^{n}A_{i}\right]&=\sum_{\varnothing \neq I \subseteq \{1, 2, \dotsc, n\}}(-1)^{|I|+1}\Pr\left[\bigcap_{i \in I}A_{i}\right] \ .\end{align*}\] Surprisingly often, the following union bound is useful: \[\Pr\left[\bigcup_{i \in I}A_{i}\right] \le \sum_{i \in I}\Pr[A_{i}] \ .\]