Consider the matching rounds problem introduced in Example 3.15. Let Rn be the number of rounds needed when there are initially n people. Use the martingale stopping theorem to show that E[Rn] = n.

Hint: Let Xi denote the number of people who have matches in round i, and use the martingale Zn =

n i=1(Xi − E[Xi |Hi−1]), n ≥ 1.