Union bound

cosmos 16th January 2018 at 12:23pm
Probability theory

if A1A_1 and A2A_2 are two events, then P(A1A2)P(A1)+P(A2)P(A_1 | A_2) \leq P(A_1) + P(A_2). A1A2A_1 \cup A_2 and A1A2A_1 \vee A_2 both denote the union of the events A1A_1 and A2A_2, i.e., the event that A1A_1 or A2A_2 holds, or both.) More generally,

P(A1...An)i=1nP(Ai)P(A_1 \cup ... \cup A_n) \leq \sum\limits_{i=1}^n P(A_i)