\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\showsolutionstrue
\begin{document}
\handout{practice-psfinal-sol}{Final Practice Problem Set - Solutions}{May 15, 2001}

\textbf{You do not have to turn in the solutions to this Problem Set.
It is designed to help you study for the final.}

\textbf{Final Exam:} Covers the entire course. The final will be held
Thursday, May 24, 2001 from 1:30 p.m. to 4:30 p.m. in Rockwell.



\medskip
\begin{problems}

%% Originally from tutorial 12!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Let $R$ and $T$ be independent random variables, and $f$ and $g$
be any functions on the real numbers, i.e. $f,g : \reals \to \reals$.
Prove that $f(R)$ and $g(T)$ are independent random variables.

\solution{The event $f(R) = a$ is the disjoint union of all the events $\set{R
= r}$ for $r \in f^{-1}(a)$, so
\[
\prob{f(R) = a} = \sum_{r \in f^{-1}(a)} \prob{R = r}.
\]
Similarly for the event $\set{g(T) = b}$.  Also, the event $\set{f(R) = a
\mbox{ and } g(T) = b}$ is the disjoint unon of the events $\set{R =
r\mbox{ and }T = t}$ for $(r,t) \in f^{-1}(a) \times g^{-1}(b)$.  Hence,
\begin{eqnarray*}
\lefteqn{\prob{f(R) = a \mbox{ and } g(T) = b}}\\
& = & \sum_{(r,t) \in f^{-1}(a) \times g^{-1}(b)}
                \prob{R = r \mbox{ and } T = t}\\
& = & \sum_{(r,t) \in f^{-1}(a) \times g^{-1}(b)} \prob{R = r} \prob{T = t}
            \hspace{0.5in}\mbox{[because $R,T$ independent]}\\
& = & \sum_{t \in g^{-1}(b)} \sum_{r \in f^{-1}(a)} \prob{R = r} \prob{T =
               t}\\
& = & \sum_{t \in g^{-1}(b)} \prob{T = t} (\sum_{r \in f^{-1}(a)} \prob{R = r})\\
& = & \sum_{t \in g^{-1}(b)} \prob{T = t} (\prob{f(R) = a})\\
& = & \prob{f(R) = a} \sum_{t \in g^{-1}(b)} \prob{T = t}\\
& = & \prob{f(R) = a} \prob{g(T) = b}
\end{eqnarray*}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%  Fall 2000  PS 11   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem Several statements involving probability
are listed below.  Assume that $A$ and $B$ are events, $S$ and $T$ are
random variables, and the underlying sample space is countable.
Furthermore, assume that all expectations exist.  For each statement,
describe restrictions on $A$, $B$, $S$, and $T$ sufficient to ensure
that the statement is true.  Make your restrictions as minimal as you
can.  No proofs are necessary.

\begin{problemparts}
%\begin{enumerate}

\problempart $\Pr(A \cup B) = \Pr(A) + \Pr(B)$
%\item[\textbf{(a)}] $\Pr(A \cup B) = \Pr(A) + \Pr(B)$

\solution{
\textbf{Solution:}\\
This statement is true provided that the event $A \cap B$
has probability zero.}

\problempart $\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)$
%\item[\textbf{(b)}] $\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)$

\solution{
\textbf{Solution:}\\
This statement is always true.
}

\problempart $\Pr(A \cap B) = \Pr(A) \cdot \Pr(B)$
%\item[\textbf{(c)}] $\Pr(A \cap B) = \Pr(A) \cdot \Pr(B)$

\solution{
\textbf{Solution:}\\
This statement is true provided that events $A$ and $B$ are independent.
}
\problempart $\Pr(A \cap B) \leq \Pr(A)$
%\item[\textbf{(d)}] $\Pr(A \cap B) < \Pr(A)$

\solution{
\textbf{Solution:}\\
This statement is always true.
}
\problempart $\Pr(A \cap B) < \Pr(A)$
%\item[\textbf{(d)}] $\Pr(A \cap B) < \Pr(A)$

\solution{
\textbf{Solution:}\\
This statement is true provided $\Pr(A \cap \overline{B}) > 0$.
}

\problempart $\Ex(S + T) = \Ex(S) + \Ex(T)$
%\item[\textbf{(e)}] $\expect(S + T) = \expect(S) + \expect(T)$

\solution{
\textbf{Solution:}\\
This statement is always true.
}

\problempart $\Ex(S \cdot T) = \Ex(S) \cdot \Ex(T)$
%\item[\textbf{(f)}] $\expect(S \cdot T) = \expect(S) \cdot \expect(T)$

\solution{
\textbf{Solution:}\\
This statement is true provided that random variables $S$
and $T$ are independent.}

\end{problemparts}
%\end{enumerate}   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

% modifed from spring 97 Pset 13, 3

There are $n$ MIT students who are taking 6.042 and 6.003 this term.  To
make it easier on themselves, the professors in charge of these classes
have decided to randomly permute their class lists and then assign
students grades based on their rank in the permutation\footnote{\dots just
as many students have suspected \texttt{:-)}}.  Assume all permutations
are equally likely and that the ranking in each class is independent of
the other.

\bparts

\ppart
What is the expected number of students that have a higher rank
in 6.042 than 6.003?

\solution{\ssl

Let $X_i$ be random variable whose value is 1 if student i has higher rank
in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$ for
6.042 than the probability that student $i$ has higher rank on 6.042,
given that the student has rank $r$ in 6.042, is $(r-1)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the
probability that student $i$ has higher rank in 6.042 is
\[
\sum_{1\leq r \leq n}  \frac{1}{n} \frac{r-1}{n} = \frac{n-1}{2n}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x} = \expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{n-1}{2}.
\]

Another way to solve this problem is to observe that students with higher
rank in one class have lower rank in the other class, so by symmetry, the
expected number of higher- and lower-ranked students in either class is
the same.  The expected number of students with the same rank equals 1 by
linearity of expectation, since probability student ranked the same in
both schools is $1/n$.  These observations now yield same answer as above.

}

\ppart
What is the expected number of students that have a ranking at
least $k$ higher in 6.042 than in 6.003?

\solution{\ssl

This part can be done in the same way as the previous one.  Let $X_i$ be
the random variable whose value is 1 if student $i$ is ranked at least $k$
higher in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$
$(r>k)$ for 6.042 than the probability that student $i$ has at least $k$
higher rank in 6.042 given student ranked $r$ in 6.042 is $(r-k)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the probability
that student $i$ has at least $k$ higher rank in 6.042 is
\[
\sum_{k+1\leq r\leq n} \frac{1}{n} \frac{r-k}{n} = \frac{(n-k)(n-k+1)}{2n^2}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x}=\expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{(n-k)(n-k+1)}{2n}.
\]

}

\eparts

\problem %{\bf (15 points)} 
In the board game Monopoly, the number of
squares that a player advances in a single turn is determined by up to
three rolls of dice as follows.

\begin{itemize}
\item Initially, the player rolls two dice, sums the results, and
advances that many squares.

\item If the same number comes up on both dice---this is called
\emph{rolling a double}---then the player rolls the dice a second time,
sums the results, and advances that many additional squares.

\item If the player rolled on double on the second roll, then the player
rolls the dice a third time, sums the results, and advances that many
additional squares.

\item However, if third roll was a double, then the player ``goes to
jail''.  We will treat this as though he had to reset his position to
where he was just before the first roll, so the total number of squares
advanced by the player in this case is zero.
\end{itemize}

What is the expected number of squares that a player advances in a single
turn?  Assume that the dice are fair and six-sided and that rolls are
mutually independent.

\solution{\ssl
Here is one approach to the problem.

It's convenient to assume the dice are \emph{always} rolled three times,
with the player simply ignoring results of any roll which was preceded by
a non-double roll.

Let the random variable $R_i$ be the sum of the two dice on the $i$th
roll, and let $I_i$ be an indicator for the event that the $i$th roll was
a double.

We can express the random variable $R$, the number of squares advanced by
the player, as follows:
\[
R = R_1 + I_1 R_2 + I_1 I_2 R_3 - I_1 I_2 I_3 (R_1 + R_2 + R_3)
\]

Since the dice rolls are independent, we know that $R_i$'s and $I_j$'s at
different rolls are independent.  We can take expectations of both sides
and reason as follows:
\begin{eqnarray*}
\expect{R}      & = &   \expect{R_1}
                 + \expect{I_1 R_2}
                 + \expect{I_1 I_2 R_3} \\
        & & \mbox{}
                 - \expect{I_1 I_2 I_3 R_1}
                 - \expect{I_1 I_2 I_3 R_2}
                 - \expect{I_1 I_2 I_3 R_3} \\
        & = &   \expect{R_1}
                 + \expect{I_1} \cdot \expect{R_2}
                 + \expect{I_1} \cdot \expect{I_2} \cdot \expect{R_3} \\
&&\mbox{}        - \expect{I_2} \cdot \expect{I_3} \cdot \expect{I_1 R_1} \\
&&\mbox{}        - \expect{I_1} \cdot \expect{I_3} \cdot \expect{I_2 R_2} \\
&&\mbox{}        - \expect{I_1} \cdot \expect{I_2} \cdot \expect{I_3 R_3}
\end{eqnarray*}

Note that the expectation of $R_i$ is $7$, and the expectation of $I_i$ is
$1/6$.  Finally, note that $\expect{I_i R_i} = 7/6$ by direct calculation.
Substituting into the formula above gives:
\begin{eqnarray*}
\expect{R}      & = &   \frac{595}{72}.
\end{eqnarray*}

}


\problem %{\bf (15 points)} 
Each bag of Doritos contains a cool
sticker.  There are $n$ different kinds of sticker, and I want to
collect at least one sticker of each kind.  (Assume that sticker kinds
in Dorito bags are uniformly random and mutually independent.)

\begin{problemparts}
\problempart Suppose that I have already collected $k$ kinds of
sticker.  What is the expected number of additional bags of Doritos
that I must eat to collect one additional kind of sticker?

\solution{\ssl
The probability that I must eat $i$ or more bags is:
\begin{eqnarray*}
\lefteqn{\expect{\text{number of bags to get new kind}}}\\
        & = &   \sum_{i=0}^{\infty} \prob{\text{number of bags to get new kind} > i} \\
        & = &   \sum_{i=0}^{\infty} \prob{\text{number of old kinds in first $i$ bags}} \\
        & = &   \sum_{i=0}^{\infty} \left(\frac{k}{n} \right)^i \\
        & = &   \frac{n}{n-k}
\end{eqnarray*}
}

\problempart What is the expected number of bags of Doritos that I
must eat to collect at least one sticker of each kind?

\solution{\ssl
We sum the expected number of bags to get the first kind,
the expected number to get the second kind, and so forth.
\begin{eqnarray*}
\lefteqn{\expect{\text{number of bags to get all kinds}}}\\
        & = &   \sum_{k=0}^{n-1} \frac{n}{n-k} \ = \   n \cdot
        \sum_{k=0}^{n-1} \frac{1}{n-k} \\
        & = &  n \cdot \sum_{j=1}^{n} \frac{1}{j} 
        \ = \   n H_n.
\end{eqnarray*}
}

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Compute the expected value for each of the
following random variables.  (Assume that all dice are fair and
six-sided and that dice rolls are mutually independent.)

\begin{problemparts}
\problempart The sum of the rolls of three dice.

\solution{
The expected value of one die roll is
\begin{eqnarray*}
1 \cdot \frac{1}{6} +
2 \cdot \frac{1}{6} +
3 \cdot \frac{1}{6} +
4 \cdot \frac{1}{6} +
5 \cdot \frac{1}{6} +
6 \cdot \frac{1}{6}
        & = & \frac{7}{2}.
\end{eqnarray*}

By linearity of expectation, the sum three rolls is
\begin{eqnarray*}
\frac{7}{2} + \frac{7}{2} + \frac{7}{2} & = & \frac{21}{2}.
\end{eqnarray*}
}

\problempart The product of the rolls of three dice.

\solution{For independent random variables, the expectation of the
product is the product of the expectations.  Therefore, the expected
product is
\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} \cdot \frac{7}{2} & = & \frac{343}{8}.
\end{eqnarray*}
}

\problempart The sum of the rolls of a number of dice that is given by
the roll of a single die.  (For example, if you roll a 3 on the single
die, then you take the sum of 3 dice rolls; if you roll a 5 on the
single die, then you take the sum of 5 dice rolls.)

\solution{By Wald's Theorem, the answer is the expected number of dice
rolled multiplied by the expected roll of one die, which is
\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} & = & \frac{49}{4}.
\end{eqnarray*}
}

\problempart Suppose now that the dice rolls are not guaranteed to be
mutually independent.  Which of your answers above must still be
correct?

\solution{The first answer remains valid because linearity of
expectation does not require independence.  Neither of the remaining
answers is necessarily correct, however; both make use of
independence.}
\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem9 spring98; from fall 96 pset12 problem5

\ignore{
\problem
% (Wald's theorem)


Consider the following $3$-stage experiment:

In the first stage, I throw a $6$-sided die.  The number of spots that I
get determines how many instances of the second stage to perform.

In the second stage, I throw a $6$-sided die.  This stage is repeated
once for each spot I got in the first stage.  The total number of spots that I
get in this stage determines how many instances of the third stage to perform.

In the third stage, I throw a $6$-sided die.  This stage is repeated
once for each spot I got in all instances of the second stage.

For example, if the outcome of the first stage is $3$, then stage 2
gets played $3$ times.  Suppose the outcomes of the $3$ instances of
stage 2 are $1,3,4$.  Then stage $3$ is played $1+3+4 = 8$ times, and the
score is the sum of $8$ instances of stage $3$.

Assume that all throws are mutually independent.

My score is the total number of spots on all the instances of the
third stage.

What is my expected score?

(Analyze this as carefully as you can, using Wald's theorem.  Try to
be careful about uses of independence.)

\solution {
\textbf{Solution}:

Let $X$ be the random variable whose value is the roll in the first
stage.  Let $Y_1, Y_2, \ldots, Y_X$ be the random variable whose values
are the rolls in the second stage.  Define $Y = Y_1 + \cdots + Y_X$.
Let $Z_1, Z_2, \ldots, Z_Y$ be the random variable whose values are
the rolls in the third stage.  Define $Z = Z_1 + \cdots + Z_Y$.  We
want to find $\expect[Z]$.  Now all the rolls are mutually independent, so
we can use Wald's theorem to get $\expect[Y] = \expect[X]\expect[Y_i] =
(7/2)^2$.  Since $Y$ is determined by rolls that are
independent of the rolls in the third stage,
$Y$ and $Z_i$ are independent.  So we apply Wald`s theorem again to
get $\expect[Z] = \expect[Y]\expect[Z_i] = (7/2)^3.$

The answer is $(7/2)^3$.
}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem11 spring98; from fall 96 pset12 problem8
\problem


Suppose you flip a fair coin 100 times.  The coin flips are all mutually independent.  
What is an upper bound on the probability
that the number of heads is at least 70\ldots
\begin{problemparts}

\problempart
\ldots according to Markov's Inequality?

\solution{
\textbf{Solution}:
The expected number of heads of $50$.  So the probability that the
number of heads is at least $70$ is at most $50/70 = 0.71$.
}

\problempart
\ldots according to Chebyshev's Inequality?

\solution{
\textbf{Solution}:
Let $X_i$ be the random variable whose value is $1$ if the $i$th coin
flip is heads.  Then $\Var[X_i] =  1/2 - (1/2)^2 = 1/4$.  So $\Var[X_1
+ \cdots + X_100] = 100/4 = 25$.
 The variance of the number of heads is $100/4 = 25$, so the standard
deviation is $5$.  So $70$ is four times the standard deviation from
the mean.  Since the distribution is symmetric, the
probability is at most $\frac{1}{2} \cdot \frac{1}{4^2} = \frac{1}{32}$
}

\problempart
\ldots according to Chernoff's Bound?

\solution{
\textbf{Solution}:
We apply Chernoff`s bound with $c = 70/50 = 1.4$.  This gives us that
$\alpha = \ln(1.4) + 1/1.4 - 1 = 0.05076$ and that the probability is at most $e^{-0.05076 \cdot 1.4 \cdot 50} = 0.0286$.
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%  Fall 2000  PS 11.5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\ignore{
\problem
Suppose you are playing the game ``Hearts'' with three of your friends.
In Hearts, all the cards are dealt to the players, in this case the four
of you will each have 13 cards.

\bparts

\ppart

What is the expectation and variance of the number of hearts that you
will have in your hand?

\solution{
\medskip
\textbf{Solution:}

Let $H$ be the number of hearts in your hand, and let $X_i$ be the
indicator variable that is 1 if card $i$ is a heart and is 0 otherwise, so
$H = \sum_{1\leq i\leq 13} X_i$.  Because $X_i$ is an indicator variable,
its expectation is the probability that card $i$ is a heart, namely, 1/4.
So
\[
\expect{H} = \sum_1^{13} 1/4 = 13/4.
\]

To compute variance, we use the definition:
\begin{eqnarray*}
\variance{\sum_{i=1}^{13} X_i} &=&
    \expect{(\sum_{i=1}^{13} X_i)^2} - \expect{\sum_{i=1}^{13} X_i}^2 \\
        &=& \expect{(\sum_{i=1}^{13} X_i)^2} - (13/4)^2 \\
        &=& \mathrm{E}[X_1^2 + X_1X_2 + X_1X_3 + \ldots + X_1X_{13} + \\
        &&   X_2X_1 + X_2^2 + X_2X_3 + \ldots + X_2X_{13} + \\
        &&        \vdots \\
        &&   X_{13}X_1 + X_{13}X_2 + \ldots + X_{13}^2] - (13/4)^2 \\
        &=& \expect{X_1^2} + \expect{X_1X_2} + \expect{X_1X_3} + \ldots + \expect{X_1X_{13}} + \\
        &&  \expect{X_2X_1} + \expect{X_2^2} + \expect{X_2X_3} + \ldots + \expect{X_2X_{13}} + \\
        &&        \vdots \\
        &&   \expect{X_{13}X_1} + \expect{X_{13}X_2} + \ldots + \expect{X_{13}^2} - (13/4)^2.
\end{eqnarray*}
Now we note that $\expect{X_i^2} = \expect{X_i}$ since $X_i$ is an
indicator variable, so $\expect{X_i^2} = 1/4$.  Also, when $i \neq j$,
$X_iX_j = 1$ if cards $i$ and $j$ are both hearts, and 0 otherwise.  The
probability that both cards are hearts is $(1/4)(12/51)$, and thus
$\expect{X_iX_j} = (1/4)(12/51) = 3/51$.  In the summation above, there
are 13 $\expect{X_i^2}$ terms, and $2\binom{13}{2} = 156$ terms of the
form $\expect{X_iX_j}$.  Thus,
\begin{eqnarray*}
 \variance{\sum_{i=1}^{13} X_i} &=& 13 \cdot \frac{1}{4} + 156 \cdot \frac{3}{51} - (\frac{13}{4})^2 \\
                &\approx& 1.863970588.
\end{eqnarray*}

}

\ppart What is the expectation and variance of the number of suits in
your hand?

\solution{
\medskip
\textbf{Solution:}

Similar to the first part: let $N$ denote the number of suits in a hand.
Let $X_s$ be the indicator variable which is 1 if there is a spade in the
hand and 0 otherwise. Define $X_h, X_d, X_c$ analogously for the three
remaining suits: hearts, diamonds, and clubs.  Then $N = X_s + X_h + X_d +
X_c$.

The expectation of each of the indicator variables is the probability
that a hand contains the corresponding suit.  Thus, for $i \in \set{s,h,d,c}$
\[
\expect{X_i} = 1 -  \frac{\binom{52-13}{13}}{\binom{52}{13}} = 0.987209,
\]
because $\binom{52-13}{13}$ is the number of hands that are missing the
particular suit, and $\binom{52}{13}$ is the total number of hands.
\[
\expect{N}=\expect{X_s + X_h + X_d + X_c} = \expect{X_s} + \expect{X_h} +
\expect{X_d} + \expect{X_c} = 4 \cdot 0.987209 = 3.94884.
\]
To compute variance:
\begin{eqnarray*}
 \variance{N} &=& \Pr(N=1)(1 - \expect{N})^2 + \Pr(N=2)(2- \expect{N})^2 + \\
              & & \qquad \Pr(N=3)(3 - \expect{N})^2 + \Pr(N=4)(4 - \expect{N})^2.
\end{eqnarray*}
Now we must calculate each of the probabilities.  First,
\[
\Pr(N=1) = \frac{4} {\binom{52}{13}} = 6.299 \times 10^{-12},
\]
because there are four possible hands of all one suit out of
$\binom{52}{13}$ possible hands of 13 cards.

\[
\Pr(N=2) = \frac{\binom{4}{2}[\binom{26}{13} - 2]}{\binom{52}{13}}
             = 9.827 \times 10^{-5},
\] 
because there are $\binom{4}{2}$ ways to choose which two suits.  There
are $\binom{26}{13}$ ways to choose 13 cards from the 26 possible cards of
those two suits.  Two of those $\binom{26}{13}$ hands actually contain
only one suit.  Thus $\binom{4}{2}(\binom{26}{13} -2)$ is the number of
hands with two suits.

\[
\Pr(N=3) = \frac{\binom{4}{3}[\binom{39}{13} -
\binom{3}{2}\binom{26}{13} + 3]}{\binom{52}{13}} = 0.05097,
\]
because there are $\binom{4}{3}$ ways to choose the three suits.  There
are $\binom{39}{13}$ ways to choose 13 cards from the 39 cards of those
three suits.  But that also includes hands with two suits and one suit.
So, using Inclusion-Exclusion, we subtract the
$\binom{3}{2}\binom{26}{13}$ ways to choose two suits from the three suits
and then choose choose 13 cards from the 26 cards of those suits.  Next,
we add back the three ways to choose hands of one suit among the three.
Finally, we divide by the $\binom{52}{13}$ ways to choose a possible hand
of 13.

Of course, 
\[
\Pr(N=4) = 1 - (\Pr(N=1) +\Pr(N=2) + \Pr(N=3)) = 0.9489.
\]
This allows us to complete the calculation of the variance:
\[
\variance{N}=0.04874.
\]

}


\eparts

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%[[[expectation, variance, Chebyshev]]]
%Spring 00, problem set 10.5, problem 4
\problem 
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

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

\solution{
\medskip
\textbf{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$.

}

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

\solution{
\medskip
\textbf{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)$.

}

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

\solution{
\medskip
\textbf{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*}

}

\ppart $\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*}

}

\ppart  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.

}

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}


\end{document}
