 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ia/paper-2/10f/b/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

Conditional on label

1

still having frequency one, it is avoided at step

i + 1

(i + 1/2) / (i + 1)

. Consequently

P (N_{1} (X) = 1) = \frac{\prod _{i = 1}^{n - 1} ( i + 1/2 )}{n !} .

The 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

P (N_{X_{n}} (X) = 1) = \frac{1 + \frac{1}{2} E M _{n - 1}}{n} .

 New to topics? Read the docs here!