%%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%[[[expectation, variance, Chebyshev]]]
% Spring 00, problem set 10.5, problem 4
% Fall 01, problem set 12, problem 2
\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.  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{
\medskip
\textbf{Solution:}

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

}

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

\solution{
\medskip
\textbf{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 21 do not apply.

}

\end{problemparts}
\end{problem}