When is the union bound tight?

ProofFoundation⏱ 15 minProbabilityunion boundtightnessinclusion-exclusion

Theory: Probability Spaces and Random Variables →

Problem

Show that the union bound $\P(\bigcup_iA_i)\le\sum_i\P(A_i)$ holds with equality if and only if the $A_i$ are pairwise disjoint up to null sets. Then give an example with $n$ events, each of probability $1/n$ , where the union bound gives $1$ but the true probability is $1/n$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Markov and Chebyshev are attained	High-Dim Probability	Proof	Foundation	15 min
Pairwise independence does not imply independence	Probability	Proof	Foundation	15 min
Generalisation for a finite class	Learning Theory	Proof	Beginner	30 min
Tightness of the descent lemma	Foundations	Proof	Beginner	15 min
From an exponential tail bound to almost sure convergence	Probability	Proof	Intermediate	30 min