\documentclass[11pt,twoside]{article}
\usepackage{amsmath,graphicx}

\input{macros-course}

\newcommand{\Ex}{\textup{Ex}}
\newcommand{\var}{\textup{Var}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol10-5}
  \newcommand{\handouttitle}{Problem Set 10.5 Solutions}
  \newcommand{\handoutdate}{May 5, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \newcommand{\handoutlabel}{ps10-5}
  \newcommand{\handouttitle}{Problem Set 10.5}
  \newcommand{\handoutdate}{May 2, 2000}
  \newcommand{\duedate}{Never}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\titlebar

\reading{%
  \vspace{-2\baselineskip}
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] \mbox{} \\
    Handout~\ref{exp} on Expectation and Variance. \\
    Self-study problems: Roulette Example in Section~2.1 
	and Gore example in Section 4.3
    
  \item[Reading:] \mbox{} \\
    Lecture Notes 23 and 24 and Handout~\ref{wald} on Wald's Theorem.
  \end{description}
  }

\section*{Problems}

\begin{problems}

\problem Eight men and seven women, all single, happen randomly to have
purchased single seats in the same 15-seat row of a theater.

\bparts

\ppart
What is the probability that the first two seats contain a marriageable
couple, i.e., a single man next to a single woman?

\solution{

Here's one way to do it.  There are $\binom{15}{2} = 105$
possible pairs that could occupy the first two seats, but only $8\cdot7 =
56$ of them are marriageable couples.  So the probability is $56/105 =
8/15$.

}

\ppart What is the expected number of pairs of adjacent seats which
contain marriageable couples?  (For example, if the sequence of men and
women in the seats is
\begin{center}
MMMWMMMMWWWWWWM,
\end{center}
then there are four possible couples sitting in the pairs of adjacent
seats that start at the 3rd, 4th, 7th and 14th seats, respectively.)

\solution{
Let the random variable S be the number of pairs of seats containing a
marriageble couple; we want to find $\expect{S}$.  We can solve this problem
by introducing an indicator random variable $S_i$, where $S_i = 1$ if
there is a marriageable couple in seats $i$ and $i+1$, and $S_i = 0$
otherwise.  So we have $S = \sum_{i=1}^{14} S_i$.

Since each seat is like any other, the probability that seats $i$ and
$i+1$ contain a marriageable couple is the same as in the first
part, $8/15$.  Thus
\[
\expect{S_i} = 1\cdot\Pr(S_i=1) + 0\cdot\Pr(S_i=0) = \frac{8}{15}.
\]
Finally, because expectation is linear,
\[
\expect{S} =  \sum_{i=1}^{14} \expect{S_i}  =  14\cdot \frac{8}{15}.
\]

Note that this approach works despite the fact that the indicator random
variables $S_i$ are not independent.  That's the beauty of linearity of
expectation!

}

\eparts

%\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{

%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{

%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

%Ben Bitdiddle is asked to analyze a game in which a fair coin is tossed
%until the first time a head turns up.  If this head occurs on the $n$th
%toss, and $n$ is odd, then he wins $\$2^n/n$, but if $n$ is even, he loses
%$\$2^n/n$.  Ben observes that the expected dollar win from this game is
%the value of the series:
%\[
%(1/2) \cdot 2 - (1/4) \cdot 2 + (1/8) \cdot 8/3 + \cdots \pm (1/2^n) \cdot 2^n/n
% = 1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n.
%\]
%This is the \emph{alternating harmonic series}---a series which is known
%to converge to a definite real number $r>0$.  Ben concludes that since $r
%>0$, it's to his advantage to play this game.  As usual, Ben's
%shoot-from-the-hip analysis is off the mark.  Explain.

%\solution{
%This series is convergent, but not \emph{absolutely} convergent.  The
%definition of expectation requires absolute convergence, so the
%expectation in this case is not defined.  The fact that the expectation is
%undefined is no mere formality.  The number $r$ is not relevant to the
%behavior of the game.  Indeed, we showed in a tutorial problem that by
%reordering its terms, the series can be made to converge to any real value
%or diverge to $\pm\infty$.
%}


%\problem 

%In the Monte Carlo version of roulette there is only one green
%slot---which is numbered 0---as opposed to the Las Vegas version, which
%has 2 green slots numbered $0$ and $00$.  If you bet on red (or,
%symmetrically, on black) and 0 comes up, one or more of these three
%options may be offered:
%\begin{enumerate}
%\item[(a)] You get $1/2$ of your bet back, and the casino gets the other
%half.

%\item[(b)] Your bet is put ``in prison.''  If red comes up on the next
%turn, you get your bet back (but don't win any money).  If black or 0
%comes up, you lose your bet.

%\item[(c)] Your bet is put in prison as before.  If red comes up on the
%next turn, you get your bet back, and if black comes up on the next turn,
%then you lose your bet.  If a 0 comes up on the next turn, then your bet
%is put into ``double prison.''  If your bet is in double prison, and if
%red comes up on the next turn, then your bet is moved back to ordinary
%prison and the game proceeds as before.  If your bet is in double prison,
%and if black or 0 come up on the next turn, then you lose your bet.

%%(FIGURE).

%\end{enumerate}
%Note that all three of these options are better than Las Vegas roulette,
%in which you simply lose your entire bet if 0 or 00 comes up.  But it
%is not clear which is the best choice.  Find the expectation of a
%one dollar bet on red under each option.  Which is best?

%\solution{

%Under option~(a), if red turns up you win 1 dollar, if black turns up
%you lose one dollar, and if 0 turns up, you lose 1/2 dollar.  Thus, the
%expected winnings are 
%\[
%1(\frac{18}{37}) + (-1)\frac{18}{37} + (\frac{-1}{2})(\frac{1}{37}) \approx
%-0.0135.
%\]

%Under option~(b), if red turns up you win 1 dollar, if black turns up, you
%lose 1 dollar, and if 0 followed by black or 0 turns up, you lose 1
%dollar. Thus the expected winnings are
%\[
%1(\frac{18}{37}) + (-1)(\frac{18}{37}) + (-1)(\frac{1}{37})(\frac{19}{37})
%\approx -0.0139.
%\]

%Under option (c), it is a bit more complicated.  Let $x$ be the
%probability that you lose your money given that it is in prsion, and let
%$y$ be the probability that you lose given that your money is in double
%prison.  Then
%\[
%x = \frac{18}{37} + \frac{1}{37}y.
%\]
%Also, 
%\[
%y = \frac{19}{37} + \frac{18}{37}x.
%\]
%So, we have 
%\[
%x = \frac{18}{37} + \frac{1}{37}(\frac{19}{37} + \frac{18}{37}x).
%\]
%Solving, we have that $x = 685/1351$.  Thus, starting from the beginning,
%the probability that you lose your bet is
%\[
%\frac{18}{37} + \frac{1}{37}x = \frac{25003}{49987}.
%\]
%Now, the only way you can win is if red comes up on the first turn, which
%happens with probability $18/37$.  Thus the expected winnings are
%\[
%1 \cdot \frac{18}{37} - 1 \cdot \frac{25003}{49987} = -\frac{685}{49987}
%\approx -0.0137.
%\]

%Thus, the simple option~(a) is actually the best.

%}

\problem  %revised from S99 Final

Three hundred students take the 6.042 final exam.  The mean on the exam is
$90$ and the lowest score was 30.  You have no other information about the
students and the exam, e.g., you should not assume that the final is worth
100 points.

\bparts

\ppart State the best possible upper bound on the number of students who
scored at least $180$.  

\solution{Let $R$ be the score.  Apply Markov's Bound to $R-30$:
\[
\Pr(R \geq 180) = \Pr(R-30 \geq 150) \leq \expect{R-30}/150 = 60/150 = 2/5,
\]
so at most $(2/5)300 = \textbf{120}$ students score $\geq 180$.}

\ppart Give an example set of scores which achieve your bound.

\solution{Of the 300 students, 120 score 180 and 180 score 30.  The mean
is
\[
(120 \cdot 180 + 180 \cdot 30)/300 = 90,
\]
as required.}


\eparts


\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{

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*}

}

% \textbf{REVISE TO SOLVE W/O COVARIANCE:}

% To compute variance we use the identity:
% \[
% \variance{\sum X_i} = \sum \variance{X_i} + \sum_{i\neq j} \covar{X_i,X_j}.
% \]
% where the second sum is taken over all possible ordered pairs of distinct
% $i$'s and $j$'s.  Now for each indicator variable we have
% \[
% \variance{X_i} = \expect{X_i^2} - \expectsq{X_i} = 1/4 - 1/16 = 3/8,
% \]
% and for each pair of distinct indicator variables we have
% \[
% \covar{X_i, X_j} = \expect{X_i X_j}-\expect{X_i}\expect{X_j} =
% \frac{1}{4} \frac{12}{51} - \frac{1}{16} = \frac{-1}{272}.
% \]
% Putting it all together,
% \begin{eqnarray*}
% \variance{H} & = & 
% \sum_{i=1}^{13}\variance{X_i} + 2\left(\sum_{1<=i<j<=13}\covar{X_i,X_j}\right)\\
%  &  = & 13 \frac{3}{8} + 2\binom{13}{2}\frac{-1}{272} = \frac{585}{136} = 4.30147.
% \end{eqnarray*}


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

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


%\textbf{REVISE TO SOLVE W/O COVARIANCE:}
% To compute variance, first compute variance of each of the indicator
% variables:
% \[
% \variance{X_i}=\expect{X_i^2} +\expectsq{X_i} = 0.987209 - 0.987209^2 =
% 0.0126273.
% \]
% Note: $\expect{X_i^2} = \expect{X_i}$ since $X_i$ is an indicator variable.


% To compute the covariance of any pair of the indicator variables, we
% need to compute $\expect{X_{i} X_{j}}$, in other words, the
% probability that a hand contains both suits $i$ and $j$. Let $I$ be
% event that the hand contains suit $i$, and $J$ be event that the hand
% contains suit $j$. Then
% \begin{eqnarray*}
% \prob{I \cap J} & = & 1 - \prob{\bar{I} \cup \bar{J}}\\ & = & 1 -
%  \prob{\bar{I}} - \prob{\bar{J}} + \prob{\bar{I} \cap \bar{J}}\\ & = &
%  1 - 2\frac{\binom{52-13}{13}}{\binom{52}{13}} +
%  \frac{\binom{52-13-13}{13}}{\binom{52}{13}} = 0.974434.
% \end{eqnarray*}

% Then covariance is
% \[
% \covar{X_{i},X_{j}} = \expect{X_{i} X_{j}} -
%            \expect{X_{i}}\expect{X_{j}} = 0.974434 - 0.987209^2 =
%            -0.00014723.
% \]

% Putting this all together we get that
% \begin{eqnarray*}
% \variance{N} & = & \variance{X_s} + \variance{X_h} + \variance{X_d} + \variance{X_c}
%        + \sum_{i \neq j \in \set{ s,h,d,c}} \covar{X_{i},X_{j}}\\
%      &  = & 4 \cdot 0.0126273 + 2\binom{4}{2}(-0.00014723) = 0.487424.
% \end{eqnarray*}

}

\eparts


\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{

$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{

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{

\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{

\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{

\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


\problem Psychological diagnosis of sociopaths is notoriously unreliable.
For example, a random psychologist is as likely to diagnose a normal
patient as sociopathic as he is to recognize that the patient is normal.
A random psychologist is actually slightly \emph{less} likely to correctly
diagnose a real sociopath than not---sociopaths are really good liars.

\bparts

\ppart In these circumstances it might seem there was no reliable way to
diagnose sociopaths, but in theory there is a way---if we have a large
enough population of psychologists who reach their judgements
independently.  Explain how to obtain a reliable diagnosis in this case.
Briefly explain why your method will be reliable, citing appropriate
results from class.  A qualitative answer is all that's required---you
need not come up with any numerical estimates or growth rates.

\solution{

Get a reliable test by repeatedly asking randomly chosen psychologists to
do the diagnosis and computing the fraction, $f$, of ``normal'' diagnoses.
Let $s>1/2$ be the probability of a ``normal'' diagnosis on a sociopathic
patient.  Diagnose normal if $f$ is closer to $1/2$ than to $s$.

By diagnosing independently enough times, there is small probability that
$f$ differs from the expected value of a diagnosis by very much (the
expected value is either 1/2 or $s$ depending on whether or not the
patient is normal---we don't know which).  By the Law of Large Numbers, by
Chebyshev's bound, or by the estimation of the binomial distribution as
used in the Gallup Poll example in Lecture Notes, if we diagnose enough
times, we can make this probability as small as desired, so the
probability of a correct diagnosis can be as close to 1 as desired.

}

\ppart Is it plausible to assume that psychologists will make their
diagnoses independently?  Briefly explain.

\solution{

Not really.  It figures that some sociopaths would be particularly good
liars and be able to fool most psychologists.  Conversely, there figure to
be normal people whose anxious or defensive manner makes a sociopathic
diagnosis by many psychologists more likely.  Also, there may be some
specially expert psychologists whose diagnoses are more reliable than
average; this implies if one expert diagnoses ``normal,'' the diagnosis is
likely to be correct, making it more likely that another expert will also
correctly diagnose ``normal,'' so their diagnoses will not be independent
of each other.

}

\eparts


\problem We have two coins: one is a fair coin and the other is a coin
that produces heads with probability 3/4.  One of the two coins is picked,
and this coin is tossed $n$ times.

\bparts

\ppart

Does the Weak Law of Large Numbers allow us to \emph{predict} what limit, if any,
is approached by the expected proportion of heads that turn up as $n$
approaches infinity?  Briefly explain.


\solution{

There is no way to predict the proportion of heads in the long run, since
this will depend upon which of the two coins is picked, and we have no
information about which coin is picked or how it is picked.  So while the
Law of Large Numbers implies that the proportion of heads will, with
probability approaching one, be near either 1/2 or 3/4, it does not, and
cannot, say anything about which of these numbers is the expected limit.

}

\ppart

How many tosses suffice to make us 95\% confident which coin was chosen?
Explain.


\solution{

To be 95 percent sure which coin was picked, bet that the fair coin was
chosen if the proportion of heads is less than the average of 1/2 and 3/4,
namely 5/8; otherwise bet that the biased coin was chosen.  You will win
the bet if the proportion of heads does not deviate from the probability
of heads by more than 1/8.  A quick calculation using Chebyshev's bound
and the fact that the variance of a Bernoulli variable is at most 1/4,
implies that the probability of a deviation this large is at most
$1/(4n(1/8)^2)$.  This will be less than or equal to .05 if $n > 320$.

In this problem, the number of heads in $n$ flips will be a Bernoulli
distribution, and the estimates from Lecture Notes 21 could also be
applied to yield a tighter bound: $n > 42$.

}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 1
\problem A couple plans to have children until they have a boy.  What
is the expected number of children that they have, and what is the
variance?

\solution{The probability of having a single child (a boy) is
$\frac{1}{2}$, the probability of having two children (a girl and then
a boy) is $\frac{1}{4}$, and so forth; the probability of having $k$
children is $\frac{1}{2^k}$.  Therefore, the expected number of
children is:

\begin{eqnarray*}
\Ex(\text{children})	& = &	\sum_{k=1}^{\infty} k \cdot \frac{1}{2^k} \\
			& = &	2
\end{eqnarray*}

Similarly, we can compute the variance as follows:

\begin{eqnarray*}
\Var(\text{children})
	& = &	\Ex(\text{children}^2) - \Ex(\text{children})^2 \\
	& = &	\sum_{k=1}^{\infty} k^2 \cdot \frac{1}{2^k}
		- \left( \sum_{k=1}^{\infty} k \cdot \frac{1}{2^k} \right)^2 \\
	& = &	6 - 2^2 \\
	& = &	2
\end{eqnarray*}

The sums above are computed using the trick of differentiating the
formula for the sum of an infinite geometric sequence.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Let $X$ and $Y$ be independent random variables taking on
integer values in the range $1$ to $n$ uniformly.  Compute the
following quantities.

\begin{problemparts}

\problempart $\var(aX+bY)$

\solution{First, we can simplify this expression using standard rules.

\begin{eqnarray*}
\var(aX+bY)
	& = &	\var(aX) + \var(bY) \\
	& = &	a^2 \var(X) + b^2 \var(Y) \\
	& = &	(a^2 + b^2) \var(X)
\end{eqnarray*}

The first step uses the fact that the variance of a sum of independent
random variables is equal to the sum of the variances.  The second
step uses the fact that multiplying a random variable by a constant
multiplies the variance by the square of that constant.  The final
step is simplification, using the fact that $X$ and $Y$ must have the
same variance, because they are indentically distributed.

What remains is to compute $\var(X)$.  The calculation is carried out
below.

\begin{eqnarray*}
\var(X)
	& = &	\Ex(X^2) - \Ex(X)^2 \\
	& = &	\sum_{i=1}^n i^2 \cdot \frac{1}{n}
		- \left( \sum_{i=1}^n i \cdot \frac{1}{n} \right)^2 \\
	& = &	\frac{(n+1)(2n+1)}{6} - \frac{(n+1)^2}{4} \\
	& = &	\frac{n^2 - 1}{12}
\end{eqnarray*}

Substituting in this result gives a complete formula for the variance.

\begin{eqnarray*}
\var(aX + bY)	& = &	(a^2 + b^2) \var(X) \\
		& = &	(a^2 + b^2)  \cdot \frac{n^2 - 1}{12}
\end{eqnarray*}
}

\problempart $\Ex(\max(X,Y))$

\solution{We begin with the definition of expectation.

\begin{eqnarray*}
\Ex(\max(X, Y))
	& = &	\sum_{i=i}^{n} i \cdot \Pr(\max(X, Y) = i)
\end{eqnarray*}

To proceed, we must compute $\Pr(\max(X, Y) = i)$, the probability
that the maximum of $X$ and $Y$ is equal to $i$.  This is done below.

\begin{eqnarray*}
\Pr(\max(X, Y) = i)
	& = &	\Pr(X = i \cap Y < i) + \\
	& &	\Pr(X < i \cap Y = i) + \\
	& &	\Pr(X = i \cap Y = i) \\
	& = &	\Pr(X = i) \cdot \Pr(Y < i) + \\
	& &	\Pr(X < i) \cdot \Pr(Y = i) + \\
	& &	\Pr(X = i) \cdot \Pr(Y = i) \\
	& = &	\left(\frac{1}{n} \cdot \frac{i-1}{n} \right) +
		\left(\frac{i-1}{n} \cdot \frac{1}{n} \right) +
		\left(\frac{1}{n} \cdot \frac{1}{n} \right) \\
	& = &	\frac{2i-1}{n^2}
\end{eqnarray*}

Substituting this result into the formula above gives:

\begin{eqnarray*}
\Ex(\max(X, Y))
	& = &	\sum_{i=i}^{n} i \cdot \frac{2i-1}{n^2} \\
	& = &	\frac{1}{n^2} \cdot \sum_{i=1}^{n} 2i^2 - i \\
	& = &	\frac{1}{n^2} \cdot \left(
		2 \cdot \frac{n(2n+1)(n+1)}{6} - \frac{n(n+1)}{2}
		\right) \\
	& = &	\frac{(n+1)(4n-1)}{6n}
\end{eqnarray*}
}

\problempart $\Ex(\min(X,Y))$

\solution{Note that $\max(X, Y) + \min(X, Y) = X + Y$.  Taking the
expected value of both sides of this equation, applying linearity of
expectation, and shuffling terms gives:

\begin{eqnarray*}
\Ex(\min(X, Y))
	& = &	\Ex(X) + \Ex(Y) - \Ex(\max(X, Y)) \\
	& = &	\frac{n+1}{2} + \frac{n+1}{2} - \frac{(n+1)(4n-1)}{6n} \\
	& = &	\frac{(n+1)(2n+1)}{6n}
\end{eqnarray*}
}

\problempart $\Ex(|X-Y|)$

\solution{We could compute this in a straightforward way from the
definition of expected value.  However, we use a trick instead.  Note
that $|X - Y| = \max(X, Y) - \min(X, Y)$.  We now get the answer by
taking the expected value of both sides and substituting the results
from above.

\begin{eqnarray*}
\Ex(|X - Y|)
	& = &	\Ex(\max(X, Y) - \min(X, Y)) \\
	& = &	\Ex(\max(X, Y)) - \Ex(\min(X, Y)) \\
	& = &	\frac{(n+1)(4n-1)}{6n} - \frac{(n+1)(2n+1)}{6n} \\
	& = &	\frac{n^2 - 1}{3n}
\end{eqnarray*}
}

\problempart $\var(|X-Y|)$.

\solution{We start with one of the standard formulas for variance.

\begin{eqnarray*}
\var(|X - Y|)
	& = &	\Ex(|X-Y|^2) - \Ex(|X-Y|)^2 \\
	& = &	\Ex((X-Y)^2) - \Ex(|X-Y|)^2
\end{eqnarray*}

We could procede from here by brute force, using the definition of
expectation.  But note that this expression for the variance of
$|X-Y|$ is quite close to the expression for the variance of $X-Y$
obtained from the same formula.

\begin{eqnarray*}
\var(X - Y)
	& = &	\Ex((X-Y)^2) - \Ex(X-Y)^2 \\
	& = &	\Ex((X-Y)^2)
\end{eqnarray*}

By substituting one equation into the other, we obtain the following
formula for the desired variance.

\begin{eqnarray*}
\var(|X - Y|)
	& = &	\var(X - Y) - \Ex(|X-Y|)^2
\end{eqnarray*}

The quantities on the right side of the this equation were computed
earlier.  Plugging in these results, we have:

\begin{eqnarray*}
\var(|X - Y|)
	& = &	\var(X - Y) - \Ex(|X-Y|)^2 \\
	& = &	(1^2 + (-1)^2) \cdot \frac{n^2 - 1}{12} -
		\left(\frac{n^2 - 1}{3n}\right)^2 \\
	& = &	\frac{(n^2 - 1)(n^2 + 2)}{18 n^2}
\end{eqnarray*}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 4
\problem 
\bparts

\ppart Let $X$ be a random variable whose value is an observation drawn
uniformly at random from the $\set{i\in\ints \mid -n \le i \le n}$.  Let
$Y = X^2$.  Show that $\Ex[XY] = \Ex[X] \Ex[Y]$. 
Are $X$ and $Y$ independent?

\solution{
Since $Y$ is determined by $X$, there are many cases indicating where $X$
and $Y$ are not independent, e.g., 
\[\Pr(Y = 0) = 1/(2n+1),\mbox{  but } \Pr(Y=0 \mid X= 0) = 1.\]

To see that $\Ex[XY] = \Ex[X] \Ex[Y]$, note that $\Ex[X] = 0$ and $\Ex[XY]
= \Ex[X^3] = 0$ since $X$ and $X^3$ are both symmetrical.
}

\ppart 
Show that in general for any two random variables $X$ and $Y$
that if $\Ex[XY] = \Ex[X] \Ex[Y]$ then $\var(X+Y) =
\var(X) + \var(Y)$.  In particular, this shows that it is possible
for nonindependent variables to have variances that exhibit
linearity.

\solution{
We have that $\var(X + Y) = \Ex((X+Y)^2) - (\Ex(X+Y))^2 = \Ex(X^2 + 2XY +
Y^2) - (\Ex(X)+ \Ex(Y))^2 = \Ex(X^2) - (\Ex(X))^2 + \Ex(Y^2) - (\Ex(Y))^2 +
2\Ex(XY) - 2\Ex(X)\Ex(Y) = \var(X) + \var(Y)$. 
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 6
\problem 


Suppose that someone is infected with an unknown incurable contagious disease.
Everyday he encounters $n$ healthy people and infects each of them with
probability $p$. Encounters are mutually independent.
These people in turn meet $n$ people and infect them with 
probability $p$ and so on.

\bparts

\ppart 
Write a recurrence for the expected number of people on the $k+1$st day
in terms of the expected number of people on the $k$th day.
Assume that each day every sick person meets $n$ {\em different} persons.

\solution{
Let $S_k$ be a random variable giving  the number infected 
people after $k$ days. \\
We can write a recurrence for $S_{k+1}$ in terms of $S_k$. \\
\\
Let the sick people after day $k$ be numbered $1,\ldots,S_k$. \\
Let $H_i$ be a random variable giving the number of healthy 
people infected by sick person $i$ in one day. \\
Then $H_i$ has a binomial distribution with parameters $n$ and $p$. \\
Then: \\
\[
S_{k+1} = S_k+ \sum_{i=1}^{S_k} H_i
\]
It follows from linearity of expectation that
\[
\Ex[S_{k+1}] = \Ex[S_k]+\Ex[ \sum_{i=1}^{S_k} H_i].
\]
Then by Wald's theorem,
\[
\Ex[S_{k+1}] = \Ex[S_k]+\Ex[S_k]\cdot \Ex[H]
\]
where $H$ is a variable with the binomial distribution with
parameters $n$ and $p$. \\
Thus, $\Ex[H] = np$.  \\
\\
So
\[
\Ex[S_{k+1}] = \Ex[S_k]+\Ex[S_k]\cdot np = (1 + np) \Ex[S_k]
\]
Also, $\Ex[S_0] = 1$. \\
So we have a recurrence involving these expectations. \\
Writing $e_i$ for $\Ex[S_i]$, we have:
\[
e_{k+1} = (1+np)e_k
\]
and 
\[
e_0 = 1
\]
}

\ppart Solve the recurrence of part (a).

\solution{$e_k = (1+np)^k$.}

\ppart
Now suppose that any sick person recovers from the disease each day with 
probability $r$. Find the expected number of sick people on the $k$th day.

\solution{
 Let $B_i$ be the indicator variable for whether the $i^{th}$ sick person gets better.  Then $\Ex[B_i] = r$.  Then
\[
S_{k+1} = S_k+ \sum_{i=1}^{S_k} (H_i-B_i)
\]
It follows that
\[
\Ex[S_{k+1}] = \Ex[S_k]+\Ex[S_k]\cdot \Ex[H]-\Ex[S_k]\Ex[B_i]
\]
and so

\begin{eqnarray*}
e_{k+1} &= & e_k(1+np-r)\\ &= &(1+np-r)^k
\end{eqnarray*}
}

\eparts
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 7
\problem


A miner, lost in some abandoned mine, finds himself in a room 
containing three doors.  Door 1 leads him to freedom after two 
hours travel; door 2 returns him to the same room after four hours travel, and 
door 3 returns him to the room after eight hours travel.
Each time he finds himself in the room, 
the miner picks a door with equal probability.  
Let $T$ denote the time until he finds the exit. \\

\bparts

\ppart Define a sequence of iid random variables $X_i$ and a stopping rule 
$N$ such that

\begin{displaymath}
T = \sum_{i=1}^{N}{X_i}
\end{displaymath}


\solution{
We view this as an experiment where at each step we make a choice between
three equiprobable outcomes.

Let $X_i$ = number of hours to return to room on $i$th step.

Let $N$ = number of steps until good door is selected.

Then $N$ is geometrically distributed with probability $1/3$.
}

\ppart Use Wald's Identity to find $\Ex[T]$

\solution{
$\Pr(X_i = 2) = 1/3$

$\Pr(X_i = 4) = 1/3$

$\Pr(X_i = 8) = 1/3$

$\Ex[X_i] = 14/3$

$\Ex[N] = 3$

By Wald's Identity

\[
\Ex[\sum_{i=1}^N X_i] = 14
\]
}

\eparts   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 8
%\problem
%
%
%Recall than in the Chinese Appetizer Problem $R$ is number of people that
%get the same appetizer after a spin of the Lazy Susan.
%
%\bparts
%
%\ppart
%Compute the variance of $R$.
%
%\ppart
%Show that the upper bound that you get on $\Pr(R \geq N)$ from the strong form
%of Chebyshev's inequality is tight.
%
%\eparts
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 9


\problem 

In this problem, we analyze probabilistically the 1st stage of bubble sort
performed on a list of $n$ integers $\{ i_1, \ldots i_n \}$.  
We assume that all the integers are 
distinct.

On the first step we compare integers $i_1$ and  $i_2$. If $i_1 > i_2$ we
swap them otherwise we leave them as they are.

On step $k~(2\leq k\leq n-1)$, we compare the new  $i_k$ with
$i_{k+1}$. If $i_k > i_{k+1}$ we swap else we leave them as they are.

We assume that the order of the integers is chosen uniformly from all 
possible orderings.  

\bparts
\ppart  
If a number $x$ is randomly (uniformly) chosen from a set of 
$n$ distinct numbers, what is the probability that $x$ is the largest
number in the set? 

What is the probability that on the $k$th step ($2\leq k\leq n-1)$,
$i_{k+1}$ is the biggest integer to appear in the list so far?

\solution{
$\Pr({\mbox{choosing largest of $n$ numbers}}) = 1/n$.  

$\Pr({\mbox{$i_{k+1}$ in $k$ step is highest so far}})=1/(k+1)$.
}

\ppart 
Let $C_k$ be a random variable that is equal to $1$ if $i_{k+1} > i_{k}$. 
What is $\Ex[C_k]$?

\solution{
\[\Ex[C_k] = \Pr({C_k = 1}) 
	= \Pr({\mbox{ $i_k$ is highest so far}}) 
	= \frac{1}{k+1}.\]
}

\ppart  
Let random variable $C=\sum_{k=1}^n C_k$. 
Give an asymptotic bound for $\Ex[C]$ as well as an interpretation
of what $\Ex[C]$ is.

\solution{
\[\Ex[C] = \sum_k \Ex[C_k] = \sum_{k=2}^{n}\frac{1}{k} \sim \ln n.\]
$C$ is the total number of swaps, 
so $\Ex[C]$ is the expected number of swaps.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F96 PS 12 Problem 5
\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{
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 $\Ex[Z]$.  Now all the rolls are mutually independent, so
we can use Wald's theorem to get $\Ex[Y] = \Ex[X]\Ex[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 $\Ex[Z] = \Ex[Y]\Ex[Z_i] = (7/2)^3.$

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F96 PS 12 Problem 7
%\problem
%
%
%\bparts
%\ppart Let $X$ be a random variable whose value is an observation
%drawn uniformly at random from the set
%$\{-n,-n+1,\ldots,-2,-1,0,1,2,\ldots,n-1,n\}$.
%Let $Y = X^2$. Show that $X$ and $Y$ are {\em not} independent, but
%that
%$\Ex{XY} = \Ex{X} \Ex{Y}$.
%\ppart Show in general for any two random variables $X$ and $Y$
%that if $\Ex{XY} = \Ex{X} \Ex{Y}$ then $\var(X+Y) =
%\var{X} + \var{Y}$.  In particular, this shows that it is possible
%for non independent variables to have variances that exhibit
%linearity.
%\ppart Let $X_1, X_2, \ldots, X_n$ be $n$ {\em pairwise} independent
%random variables.  Show that $\var{X_1 + X_2 + \cdots + X_n} =
%\var{X_1} + \var{X_2} + \cdots + \var{X_n}$.
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F96 PS 12 Problem 8
%\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?

%\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?

%\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?

%\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$.


%%\problempart
%%\ldots according to the upper bound for binomial distributions
%%        derived in lecture?\\
%%        (Get a strict upper bound by using the multiplicative factors
%%of
%%        $\frac{1-\alpha}{1-2\alpha}$ to account for the case that
%%        there are strictly more than 70 heads,
%%        and $(\frac{n}{e})^{\frac{1}{12n}}$ to adjust Stirling's
%%        approximation.)
%\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F96 PS12
%\problem
%Give upper bounds for the following probabilities using the Markov,
%Chebyshev, or Chernoff inequality, where appropriate.  If more than
%one inequality applies, use the inequality that gives you the best
%bounds. 

%\bparts
%\ppart Suppose you play the following game:  Flip $5$ independent and
%fair coins.  Score one point if the difference between the number of
%heads and tails is at least $3$.  What is the probability that your
%average score is greater than $0.9$ if you play the game $100$ times?

%\ppart Let $a$ and $b$ be two numbers picked independently and
%uniformly at random from the set $\{0,1,2,3,4\}$.
%For $i = 0,1,2,3,4$, define the random
%variable $X_i$ to be equal to $ai + b \bmod p$.  
%Let $Y = \frac{1}{5}(X_1 + X_2 + X_3 + X_4 + X_5)$.  
%What is the probability that $Y$ is greater than $3.5$?
%{\em Hint}: Observe that $X_i$ is distributed uniformly on the set
%$\{0,1,2,3,4\}$.  

%\ppart You are told that the average (mean) annual income is \$10,000
%in a particular population.  Five people are picked independently and
% uniformly and at random from the population.  
%What is the probability that their avearge (mean) annual income is
%greater than or equal to \$1,000,000?
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%S95 PS 10 Problem 4
%\problem 

%Let $S$ be a sample space.  Say random variable $X: S \rightarrow
%\mathbb{N}$ has distribution
%\[
%X = \left\{ \begin{array}{cl} 2 & \mbox{with probability $1/4$,} \\
%                             3 & \mbox{with probability $1/4$,} \\
%			     5 & \mbox{with probability $1/2$;} \end{array}
%\right.
%\]
%and random variable $Y:S\rightarrow \naturals$ has distribution
%\[
%Y = \left\{ \begin{array}{cl} 1 & \mbox{with probability $2/3$,} \\
%                             4 & \mbox{with probability $1/3$;} \end{array}
%\right.
%\]
%where $X$ and $Y$ are independent.

%Let random variable $Z:S\rightarrow \naturals$ be given by $Z = \max(X,Y)$.
%\bparts
%\ppart What is the expected value of $Z$?

%\solution{
%We first compute the values of $Z$ along with their associated
%probabilities.  Note that $P(X=x \mbox{ \& } Y=y) = P(X=x)P(Y=y)$ since $X$
%and $Y$ are independent.

%\begin{center}
%\begin{tabular}{|c|c|c|c|c|} \hline
%$X$ & $Y$ & $Z$ & $Z^2$ & Pr \\ \hline
%$2$ & $1$ & $2$ & 4 & $\frac{1}{6}$ \\ \hline
%$3$ & $1$ & $3$ & 9 & $\frac{1}{6}$ \\ \hline
%$5$ & $1$ & $5$ & 25 & $\frac{1}{3}$ \\ \hline
%$2$ & $4$ & $4$ & 16 & $\frac{1}{12}$ \\ \hline
%$3$ & $4$ & $4$ & 16 & $\frac{1}{12}$ \\ \hline
%$5$ & $4$ & $5$ & 25 & $\frac{1}{6}$ \\ \hline
%\end{tabular}
%\end{center}

%Now
%\[
%E(Z) = 2\cdot\frac{1}{6} + 3\cdot\frac{1}{6} + 5\cdot\frac{1}{3} +
%4\cdot\frac{1}{12} + 4\cdot\frac{1}{12} + 5 \cdot\frac{1}{6} = 4
%\]
%}

%\ppart What is the variance of $Z$?

%\solution{
%Recall that ${\rm Var}Z = E(Z^2) - E(Z)^2$.  So we first compute $E(Z^2)$
%using the data from the above table
%\[
%E(Z^2) = 4\cdot\frac{1}{6} + 9\cdot\frac{1}{6} + 25\cdot\frac{1}{3} +
%16\cdot\frac{1}{12} + 16\cdot\frac{1}{12} + 15 \cdot\frac{1}{6} =
%	\frac{52}{3}
%\]
%Finally ${\rm Var}(Z) = 52/3 - 16 = \frac{4}{3}$.
%}

%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%S95 PS 10 Problem 6
%\problem


%\bparts
%\ppart Show that if random variables $X$ and $Y$ are independent then ${\rm
%Cov}(X,Y)=0$

%\solution{
%First we show that if $X$ and $Y$ are independent, then $E(XY) = E(X)E(Y)$.
%\begin{eqnarray*}
%E(XY) & = & \sum_{x,y} xyP(X=x \mbox{ \& } Y=y) \\
%      & = & \sum_x \sum_y xyP(X=x \mbox{ \& } Y=y) \\
%	  & = & \sum_x \sum_y xyP(X=x)P(Y=y) \\
%	  & = & \sum_x xP(X=x)\sum_y yP(Y=y) \\
%	  & = & \sum_x xP(X=x)E(Y) \\
%	  & = & E(Y)\sum_x xP(X=x) \\
%	  & = & E(X)E(Y)
%\end{eqnarray*}
%Since ${\rm Cov}(X,Y) = E(XY) - E(X)E(Y)$, ${\rm Cov}(X,Y) = 0$.
%}

%\ppart Show that having ${\rm Cov}(X,Y)=0$ does not necessarily mean that
%$X$ and $Y$ are independent.

%\solution{
%Let $(X,Y)$ have joint probability given by the table below:

%\begin{center}
%\begin{tabular}{|c|c|c|} \hline
%$X$ & $Y$ & P \\ \hline
%$-1$ & $1$ & $\frac{1}{3}$ \\ \hline
%$0$ & $0$ & $\frac{1}{3}$ \\ \hline
%$1$ & $1$ & $\frac{1}{3}$ \\ \hline
%\end{tabular}
%\end{center}

%Note that $X$ and $Y$ are not independent.  $P(X=1 \mbox{ \& } Y=1) =
%\frac{1}{3} \neq \frac{2}{9} = P(X=1)P(Y=1)$.  But $E(X) = 0$ and $E(XY) =
%0$ (since $XY=X$).  Thus ${\rm Cov}(X,Y) = 0$.
%}

%%\ppart Let $X_1,\ldots,X_n$ be random variables.  Prove that
%%\[
%%{\rm Var}(X_1+\ldots+X_n)=\sum_{i=1}^n {\rm Var}(X_i) + 2\sum_{i<j} {\rm Cov}(X_i,X_j)
%%\]
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}
