        \problemdata       % Takes 5 *mandatory* arguments
        {hat-checks}             % latex-friendly label for the prob.
        {expectation}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 cp11m-3} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).



\begin{problem}
There is a dinner party where $N$ men check their hats.  The hats
are mixed up during dinner, so that afterward each man receives a
random hat.  In particular, each man gets his own hat with probability
$1/N$.  What is the expected number of men who get their own hat?

\solution{Also from the Course Notes.

Let the random variable $R$ be the number of men that get
their own hat. The trick is to express $R$ as a sum of indicator
variables.  In particular, let $R_i$ be an indicator for the event
that the $i$th man gets his own hat. That is, $R_i = 1$ is the event
that he gets his own hat, and $R_i = 0$ is the event that he gets the
wrong hat.  The number of men that get their own hat is the sum of
these indicators:
\[
R = R_1 + R_2 + \cdots + R_N.
\]

These indicator variables are {\em not} mutually independent.  For
example, if $N-1$ men all get their own hats, then the last man is
certain to receive his own hat. But linearity of expectation, doesn't
require indicator variables are independent, because no matter what,
we can take the expected value of both sides of the equation above and
apply linearity of expectation:
\begin{equation*}
\expect{R} =  \expect{R_1 + R_2 + \cdots + R_N} 
           =  \expect{R_1} + \expect{R_2} + \cdots + \expect{R_N}.
\end{equation*}
The expected value of an indicator variable is always the probability
that the indicator is 1. In this case, the quantity $\pr{R_i = 1}$ is
the probability that the $i$th man gets his own hat, which is just
$1/N$.  We can now compute the expected number of men that get their
own hat:
\[\begin{array}{rcccccccccc}
\expect{R} &=&  \expect{R_1} &+& \expect{R_2} &+& \cdots &+& \expect{R_N} \\
           &=&  \cfrac{1}{N} &+& \cfrac{1}{N} &+& \cdots &+& \cfrac{1}{N} &=& 1.
\end{array}\]

We should expect exactly one man to get the right hat!
}
\end{problem}
