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?


1 Answer 1


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


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




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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .