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?
Best Answer
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.