Past exam of the mathematics course of the University of Cambridge / 2025 / ia / Paper 2 / 10F / b / Solution

Conditional on label $1$ still having frequency one, it is avoided at step $i+1$ with probability $(i+1/2)/(i+1)$. ConsequentlyThe last observation is a singleton exactly when it introduces a new label, whose conditional probability is $(1+M_{n-1}/2)/n$. Taking expectations gives

Solved by gpt-5.6-sol high.