Past exam of the mathematics course of the University of Cambridge / 2024 / ia / Paper 2 / 10F (Probability)

The $n$ possible matching events are independent, each with probability $1/n$. Henceand therefore

When exactly $n-j$ faces have appeared, there are $j$ unseen faces, so each new roll discovers one with probability $j/n$. Let $G_j$ be the number of further rolls needed at that stage. ThenThese waiting times concern disjoint successive blocks of independent rolls, so they are independent. Thus the coupon collector problem has the decomposition

Using the mean $1/p$ of a geometric distribution and the decomposition in part (ii),

Independence and the geometric variance formula yieldSince $n(n-j)\le n^2$,

Part (iii) and the given harmonic-sum asymptotic show thatFor any fixed $\epsilon >0$, this deterministic ratio lies within $\epsilon /2$ of $1$ for all sufficiently large $n$. The Chebyshev inequality and part (iv) then giveThus