\problemdata       % Takes 5 *mandatory* arguments
  {hatcheck-variance}      % latex-friendly label for the prob.
  {variance, Chebyshev}    % The topic(s) of the problem content.
  {}                       % Source (if known)
  {S00 ps10.5-4, F00, F01 ps12-2, S02 cp12W-3} % Usage 
  {Nick Matsakis, S02}     % Last revision info (author, date).
\begin{problem}
The hat-check staff has had a long day, and at the end of the party
they decide to return people's hats at random. Suppose that $n$ people
have their hats returned at random. We previously showed that the
expected number of people who get their own hat back is 1,
irrespective of the total number of people. In this problem we will
calculate the variance in the number of people who get their hat back.

Let $X_i = 1$ if the $i$th person gets his or her own hat back and 0
otherwise.  Let $S_n = \sum_{i=1}^n X_i$, so $S_n$ is the total number
of people who get their own hat back. Show that

\begin{problemparts}

\problempart $\expect{X_i^2} = 1/n$.

\solution{
$X_i = 1$ with probability $1/n$ and 0 otherwise. Thus $X_i^2 = 1$
with probability $1/n$ and 0 otherwise. So $\expect{X_i^2} = 1/n$.
}

\problempart $\expect{X_i X_j} = 1/n(n-1)$ for $i \neq j$.

\solution{

The probability that $X_i$ and $X_j$ are both 1 is $1/n \cdot 1/(n-1) =
1/n(n-1)$.  Thus $X_i X_j = 1$ with probability $1/n(n-1)$, and is zero
otherwise.  So $\expect{X_i X_j} = 1/n(n-1)$.

}

\problempart $\expect{S_n^2} = 2$. \hint Use (a) and (b).

\solution{

\begin{eqnarray*}
\expect{S_n^2} & = & \sum_i \expect{X_i^2} + \sum_i \sum_{j \neq i} \expect{X_i X_j} \\
         & = & n \cdot \frac{1}{n} + n(n-1) \cdot \frac{1}{n(n-1)} \\
         & = & 2.
\end{eqnarray*}

}

\problempart $\variance{S_n} = 1$.

\solution{
\begin{eqnarray*}
\variance{S_n} & = & \expect{S_n^2} - \expectsq{S_n} \\ 
       & = & 2 - (n (1/n))^2 \\
       & = & 2 - 1 \\
       & = & 1.
\end{eqnarray*}
}

\problempart Explain why you can not use the variance of sums formula to
calculate $\variance{S_n}$.

\solution{The indicator random variables, $X_i$, are not even pairwise independent.  This can be seen by comparing the marginal and conditional probability of a particular person, Alice, getting her hat back.  The marginal probability, unconditioned on any other events, is $1/n$ as we've computed before.  However, if compute this probability conditioned on the event that a second person, Bob, got his hat back, we find that the probability of Alice getting her hat back is $1/(n-1)$.}

\problempart Using Chebyshev's Inequality, show that $\Pr(S_n \geq 11)
\leq .01$ for any $n \geq 11$.

\solution{
\begin{eqnarray*}
\Pr(S_n \geq 11) &=& \Pr(S_n - \expect{S_n} \geq 11 - \expect{S_n}) \\
                 &=& \Pr(S_n - \expect{S_n} \geq 10) \\
                 &\leq& \frac{\variance{S_n}}{10^2} = .01
\end{eqnarray*}

Note that the $X_i$'s are Bernoulli variables but are \emph{not}
independent, so $S_n$ does not have a Bernoulli distribution and the
Bernoulli estimates from Lecture Notes do not apply.
}

\end{problemparts}
\end{problem}
