# The Matching Rounds Problem--Proof by induction

Can someone please explain how we skipped from line (3) to (4)

This problem deals with the Hats Problem which state that n men throw their hats into the center of a room. The hats are mixed up and each man randomly selects one. Then the expected number of any number of men who select their own hats is always $1$.

Now we suppose that those choosing their own hats leave the room, while the others (those without a match) put their selected hats in the center of the room again, mix them up, and then re-select. This process continues until each individual has his own hat.

The question is: Find $E[R_n]$ where $R_n \Doteq \$ is the number of rounds that are necessary when $n$ individuals are initially present.

Solution: We use induction to prove this:

on average, there will be one match per round. Hence, one might suggest that $E[R_n] = n$. This turns out to be true, and an induction proof will now be given.

Because it is obvious that $E[R_1] = 1$, assume that $E[R_k] = k \ for \ k = 1, . . . , n − 1$.

To compute $E[R_n]$, we start by conditioning on $X_n$, the number of matches that occur in the first round. This gives

$E[R_n] = \sum_{i=0}^n E[R_n|X_n = i]P[X_n = i]$

Now, given a total of $i$ matches in the initial round, the number of rounds needed will equal $1$ plus the number of rounds that are required when $n − i$ persons are to be matched with their hats. Therefore,

$E[R_n] = \sum_{i=0}^n (1 + E[R_{n−i}])P[X_n = i]$ $= 1 + E[R_n]P[X_n = 0] + \sum_{i=0}^n E[R_n−i]P[X_n = i]$ $= 1 + E[R_n]P[X_n = 0] + \sum_{i=0}^n (n − i)P[X_n = i]$ $(3)$

This is where I get stuck. by the induction hypothesis we can get $= 1 + E[R_n]P[X_n = 0] + n(1 − P[X_n = 0]) − E[X_n]$ $(4)$

in the end we get: $E[R_n]= E[R_n]P[X_n = 0] + n(1 − P[X_n = 0])$

Question 2: by the way, what is $P[X_n = 0]?$

Question 2: Why can't we just say: $E[R_n] = E[R_{n-1}+R_{n^{th}}]$ where $R_{n^{th}}$ is the nth case which equal $1$ by hats problem expectation.

Hence $E[R_n] = E[R_{n-1}]+E[R_{n^{th}}]$ by inductive hypothesis: $E[R_n] = n-1+E[R_{n^{th}}]$

$E[R_n] = n-1+1 = n$ what's wrong with that?

It would be easier to follow if you transcribed the calculation correctly:

\begin{align*} E[R_n]&=\sum_{i=0}^n(1+E[R_{n-i}])P[X_n=i]\\ &=1+E[R_n]P[X_n=0]+\sum_{i=1}^nE[R_{n-i}]P[X_n=i]\\ &=1+E[R_n]P[X_n=0]+\sum_{i=1}^n(n-i)P[X_n=i]\;. \end{align*}

The last step above is where you use the induction hypothesis that $E[R_k]=k$ for $k<n$. Now expand that last summation:

\begin{align*} \sum_{i=1}^n(n-i)P[X_n=i]&=n\sum_{i=1}^nP[X_n=i]-\sum_{i=1}^niP[X_n=i]\\ &=n\left(\sum_{i=0}^nP[X_n=i]-P[X_n=0]\right)-\sum_{i=0}^niP[X_n=i]\\ &=n(1-P[X_n=0])-E[X_n]\;, \end{align*}

since the probabilities of the possible values of $X_n$ sum to $1$, and the last summation is by definition $E[X_n]$. You now have

$$E[R_n]=1+E[R_n]P[X_n=0]+n(1-P[X_n=0])-E[X_n]\;,$$

and you've already shown that $E[X_n]=1$, so

$$E[R_n]=E[R_n]P[X_n=0]+n(1-P[X_n=0])\;.$$

Thus,

$$E[R_n](1-P[X_n=0])=n(1-P[X_n=0])\;,$$

and $E[R_n]=n$ (since clearly $P[X_n=0]\ne 1$).

The probability that no one gets his hat back is a bit messy to compute, but it's approximately $\frac1e$; for more information you should read about derangements.

Your proposed alternative calculation mixes two very different things: $E[R_{n-1}$ is an expected number of rounds, while your $E[R_{n^{th}}]$ is just another name for $E[X_n]$, an expected number of people getting the right hats. You can't expect to add rounds and hats and get rounds.