Section 3.3

Complements and 'At Least One'

Probabilities through the complement or inclusion-exclusion: at least one success in n trials (including de Mere), birthday-type coincidences, all values distinct, at least one couple paired.

Toolkit

When “at least one” or “all distinct” is hard to count directly, pass to the complement, $\mathbb{P}(\text{at least one}) = 1-\mathbb{P}(\text{none})$ , or expand via inclusion–exclusion over the bad events $A_1,\dots,A_n$ :

\mathbb{P}\Big(\bigcup_i A_i\Big)=\sum_i \mathbb{P}(A_i)-\sum_{i<j}\mathbb{P}(A_i\cap A_j)+\cdots

For $n$ independent trials with success probability $p$ , $\mathbb{P}(\text{at least one success})=1-(1-p)^n$ ; requiring confidence $c$ gives $n\ge \log(1-c)/\log(1-p)$ . For sequential matching problems (birthdays, collisions), compute $\mathbb{P}(\text{all distinct so far})$ as a falling-factorial product and track it step by step; stopping/record problems often reduce to comparing consecutive ratios of such probabilities, or to a tail-sum $\mathbb{E}[N]=\sum_k \mathbb{P}(N>k)$ .

Problems