Events are a subset of the [[Sample Space]] (continuous or discrete), i.e. a collection of possible outcomes. Probabilities can be assigned to events. ![[probability-events.png]] ## Subsets If $A \subset B$ ($A$ is a subset of $B$), then the probability of $A$ must be $\le$ $B$. $ \mathbf P(B) = \mathbf P(A)+\underbrace{\mathbf P(B \cap A^c)}_{\ge 0} \implies \mathbf P(B) \ge \mathbf P(A) $ ## Union Bound The union of 2 events has to be $\le$ the sum of both, because the maximum of covered area by a union is when the events are disjoint. $ \begin{align} \mathbf P(A \cup B) &= \mathbf P(A) + \mathbf P(B)-\overbrace{\mathbf P(A \cap B)}^{\ge 0} \\[4pt] \mathbf P(A \cup B) &\le \mathbf P(A) + \mathbf P(B) \end{align} $ ![[union-bound.png |center|400]] ## Bonferroni Inequality The intersection of two events has to be greater than the sum of their probabilities $-1$. $ \mathbf P(A_1 \cap A_2) \ge \mathbf P(A_1)+ \mathbf P(A_2)-1 $ We make the proof by looking at the complement, and transform it according to De Morgan’s law. $ \begin{align} \mathbf P((A_1 \cap A_2)^C) = \mathbf P(A_1^C \cup A_2^C) &\le \mathbf P(A_1^C)+ \mathbf P(A_2^C) \tag{1}\\[4pt] 1-\mathbf P(A_1 \cap A_2) &\le 1- \mathbf P(A_1)+1- \mathbf P(A_2) \tag{2}\\[4pt] -\mathbf P(A_1 \cap A_2) &\le 1- \mathbf P(A_1)-\mathbf P(A_2) \tag{3}\\[4pt] \mathbf P(A_1 \cap A_2) &\le \mathbf P(A_1)+\mathbf P(A_2)-1 \tag{4}\\[4pt] \end{align} $ where: - (1) Applied union bound to state the inequality. - (2) Expressed the complement as $1- \mathbf P(\cdot)$. We can generalize this statements to the intersection of $n$ events. $ \mathbf P(A_1 \cap \dots \cap A_n) \ge \mathbf P(A_1)+ \dots + \mathbf P(A_n)-(n-1) $