SECTION 06 / 10

Union bound and event relationships

On this page 5 headings

Learning goal: Combine failure probabilities and compare related events.

The idea

Several events: add their probabilities to bound the chance that at least one happens.
Related events: if A can happen only when B happens, then A cannot be more likely than B.

① Union bound

P (A \cup B) = P (A) + P (B) - \geq 0 P (A \cap B) \leq P (A) + P (B)

P (A_{1} \cup A_{2} \cup \dots \cup A_{n}) \leq i = 1 \sum n P (A_{i}) .

$A \cup B$ ("A or B") means at least one of them happens.
We drop the overlap term because it is often hard to compute in randomized algorithms.
Dropping it can only make the answer bigger, so we still get a valid upper bound.
It is tight (no loss) when events don't overlap, and loose when they overlap a lot.

Worked example: die

A = "even" = {2,4,6}, B = "at least 5" = {5,6}.

Exact: $A \cup B = {2, 4, 5, 6}$ , so $P = 4/6 \approx 0.667$ .
Union bound: $3/6 + 2/6 = 5/6 \approx 0.833$ .
That is bigger, because {6} was counted twice.

Suppose each of 1,000 checks fails with probability at most 0.00001.
The chance that any check fails is at most $1000 \times 0.00001 = 0.01$ .
You never need to know how the failures are related.
In Lesson 9 and beyond, the "checks" are the ~ $n^{2} /2$ pairs of points, and this is exactly how the log n appears in JL.

② If A ⇒ B then P(A) ≤ P(B)

"A ⇒ B" (A implies B): whenever A happens, B has happened too.
So every outcome in A is also in B, which makes B the bigger set (superset).
This follows directly from set inclusion.
Therefore $P (A) \leq P (B)$ .
The converse fails: B can happen without A.

How this gets used: to bound a complicated bad event A, find a simpler event B that must happen whenever A does, and bound B instead.
When the two events are actually equal (A ⇔ B), their probabilities are equal.
Lesson 9 uses that.

Three servers each fail today with probability 2 %. Upper bound on "at least one fails"?

2 % + 2 % + 2 % = 6 %.

A = "score ≥ 90", B = "score ≥ 75". Which is bigger, P(A) or P(B)?

A ⇒ B, so P(A) ≤ P(B).

YOUR STUDY PROGRESS

Finished this section? Save your progress.