$n$ people play a game of exchanging hats, with the following two rules:
--They throw their hats in to a pile and everyone chooses one uniformly at random, those who got back their own hat are out of the game.
--This is repeated until everyone has its own hat back.
Let $R$ denote the number of rounds the game takes to finish. $R = 1$ means that everyone got their own hat back at the first drawing. Calculate the expected number of rounds $E[R]$.
I think the key is to find a martingale $S_n$ with respect to a random sequence $X_n$, such that $E(S_n|X_1, X_2,...,X_{n-1})=S_{n-1}$. Thus we could regard $R$ as a stopping time, and there's a normal way to solve $E[R]$. However I cannot figure out what can be the martingale $S_n$ in this question, and what can be the $\{X_n\}$ .
Any help would be appreciate!
The expected number is n.
The question was solved using an induction method in
The Matching Rounds Problem--Proof by induction