\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps10-5
One hundred twenty 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 of a student chosen at random.  
Apply Markov's Bound to $R-30$:
\[
\Pr(R \geq 180) = \Pr(R-30 \geq 150) 
        \leq \frac{\expect{R-30}}{150} 
        = \frac{60}{150} = \frac{2}{5}.
\]
So at most $\frac{2}{5} \cdot 120 = 48$ students scored 
greater than or equal to $180$.}

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

\solution{Of the 120 students, 48 score 180 and 72 score 30.  
The mean is $\frac{48 \cdot 180 + 72 \cdot 30}{120} = 90$, as required.}

\ppart If the maximum score on the exam was $100$, 
give the best possible upper bound on the number of students 
who scored \emph{at most} $50$. 

\solution{Apply Markov's Bound to $100-R$: 
\[
\Pr(R \leq 50) = \Pr(100-R \geq 50)
        \leq \frac{\expect{100-R}}{50}
        = \frac{10}{50}
        = \frac{1}{5}.
\]
So at most $\frac{1}{5} \cdot 120 = 24$ students scored $50$ or less.} 

\eparts


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*}
%\expect{\text{children}}& = &  \sum_{k=1}^{\infty} k \cdot \frac{1}{2^k} \\
%                       & = &   2
%\end{eqnarray*}
\solution{Let $C$ be the expected number of children up to and including
the first boy. 
We showed $\expect{C} = 2$ in Lecture 22.
We can compute the variance as follows:
\[
\variance{C}
         = \expect{C^2} - \expect{C}^2 
         = \sum_{k=1}^{\infty} k^2 \cdot \left(\frac{1}{2}\right)^k - 2^2 
         = \frac{\frac{1}{2} + (\frac{1}{2})^2}{(1 - \frac{1}{2})^3} - 4 
         = 6 - 4
         = 2
\]
The sum is computed by differentiating the
formula for the sum of an infinite geometric sequence.
}

\problem %source: spring00 ps10-5
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 $\variance{aX+bY}$

\solution{First, we compute $\variance{X}$, 
which is also $\variance{Y}$ since $X$ and $Y$ are identically distributed.
\begin{align*}
\variance{X}
        & = \expect{X^2} - \expect{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{align*}

We now use this to compute $\variance{aX + bY}$: 
\begin{align*}
\variance{aX+bY}
        & = \variance{aX} + \variance{bY} 
                & & \text{because $aX$ and $bY$ are independent} \\
        & = a^2 \variance{X} + b^2 \variance{Y}
                & & \text{Theorem~4.4 in Lecture Notes 24} \\
        & = (a^2 + b^2) \variance{X}
                & & \text{because $\variance{X} = \variance{Y}$} \\
        & = (a^2 + b^2) \frac{n^2 - 1}{12}
                & & \text{substitution from computation above}
\end{align*}
}

\problempart $\expect{\max(X,Y)}$

\solution{
First we compute the probability that the maximum of $X$ and $Y$ 
is equal to $i$: 
\begin{align*}
\Pr(\max(X,Y) = i) 
        & = \Pr(X \leq i \land Y \leq i) - \Pr(X < i \land Y < i) \\
        & = \Pr(X \leq i) \Pr(Y \leq i) - \Pr(X < i) \Pr(Y < i) \\
        & = \frac{i}{n} \cdot \frac{i}{n} 
                - \frac{i-1}{n} \cdot \frac{i-1}{n} \\
%       & = \frac{i^2 - (i-1)^2}{n^2} \\
        & = \frac{2i-1}{n^2}
\end{align*}

We now compute the expectation using these probabilities:
\begin{align*}
\expect{\max(X, Y)}
        & = \sum_{i=i}^{n} i \cdot \Pr(\max(X,Y) = i) 
          = \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{align*}

Alternatively, we could also compute it as follows:
\begin{align*}
\expect{\max(X,Y)}
        & = \sum_{i=0}^{\infty} \Pr(\max(X,Y) > i) 
          = \sum_{i=0}^{n-1} \left(1 - \Pr(\max(X,Y) \leq i)\right) \\
        & = n - \sum_{i=0}^{n-1} \Pr(X \leq i \land Y \leq i) 
          = n - \sum_{i=0}^{n-1} \Pr(X \leq i) \Pr(Y \leq i) \\
        & = n - \sum_{i=0}^{n-1} \left(\frac{i}{n}\right)^2 
          = n - \frac{1}{n^2} \cdot \frac{n(n-1)(2n-1)}{6} \\
        & = \frac{(n+1)(4n-1)}{6n}
\end{align*}
}


\problempart $\expect{\min(X,Y)}$

\solution{Note that $\max(X, Y) + \min(X, Y) = X + Y$.  
Thus,
\begin{align*}
\expect{\min(X, Y)}
        & = \expect{X} + \expect{Y} - \expect{\max(X, Y)} \\
        & = \frac{n+1}{2} + \frac{n+1}{2} - \frac{(n+1)(4n-1)}{6n} \\
        & = \frac{(n+1)(2n+1)}{6n}
\end{align*}
}

\problempart $\expect{|X-Y|}$

\solution{We could compute this directly. 
However, note that $|X - Y| = \max(X,Y) - \min(X, Y)$.  
Thus,
\begin{align*}
\expect{|X - Y|}
        & = \expect{\max(X, Y) - \min(X, Y)} \\
        & = \expect{\max(X, Y)} - \expect{\min(X, Y)} \\
        & = \frac{(n+1)(4n-1)}{6n} - \frac{(n+1)(2n+1)}{6n} \\
        & = \frac{n^2 - 1}{3n}
\end{align*}
}

\problempart $\variance{|X-Y|}$.

\solution{
We start with one of the standard formulas for variance:
\[
\variance{|X - Y|}
        = \expect{|X-Y|^2} - \expect{|X-Y|}^2 
        = \expect{(X-Y)^2} - \expect{|X-Y|}^2
\]

We could compute $\expect{(X-Y)^2}$ directly, 
but note that 
$\variance{X-Y} = \expect{(X-Y)^2} - \expect{X-Y}^2$, 
and $\expect{X-Y} = 0$. 
We can compute $\variance{X-Y}$ using the 
result in part (a). 
Thus, 
\begin{align*}
\variance{|X - Y|}
        & = \variance{X - Y} - \expect{|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{align*}
}

\end{problemparts}



\problem %source: spring00 ps10-5
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 in your hand?

\solution{
Let $H$ be the number of hearts in your hand, 
and let $X_i$ be the indicator random variable 
for the event that the $i$th card in your hand is a heart. 
Then $H = \sum_{i=1}^{13} X_i$.  
So
\[
\expect{H}  = \sum_{i=1}^{13} \expect{X_i}
        = \sum_{i=1}^{13} \Pr(\text{$i$th card is a heart}) 
        = \sum_{i=1}^{13} \frac{1}{4} = \frac{13}{4}.
\]

To compute variance, 
we first compute $\expect{H^2}$, 
following the solution to Problem~4c. 
\[
\expect{H^2} = \expect{\left(\sum_{i=1}^{13} X_i\right)^2} 
        = \sum_i \expect{X_i} + \sum_i \sum_{j \neq i} \expect{X_i X_j} 
\]
Note that $X_i^2 = X_i$, so $\expect{X_i^2} = 1/4$.  
When $i \neq j$,
$X_i X_j = 1$ if cards $i$ and $j$ are both hearts, and 0 otherwise.  The
probability that both cards are hearts is $\binom{13}{2}/\binom{52}{2}$, 
so 
$\expect{X_iX_j} = \binom{13}{2}/\binom{52}{2} = 3/51$.  
In the summation above, there
are 13 $\expect{X_i^2}$ terms, and $13 \cdot 12 = 156$ terms of the
form $\expect{X_i X_j}$ with $i \neq j$.  Thus,
\[
\variance{H} = \expect{H^2} - \expect{H}^2
        = 13 \cdot \frac{1}{4} + 156 \cdot \frac{3}{51} - (\frac{13}{4})^2 
        \approx 1.864. 
\]
}

% \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{
Let $N$ denote the number of suits in a hand.
Let $X_s$ be the indicator random variable 
for the event that there is a spade in the hand. 
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}} \approx 0.9872,
\]
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} \approx 4 \cdot 0.9872 = 3.9488.
\]
To compute variance, we compute $\expect{N^2}$ directly, 
and then $\variance{N} = \expect{N^2} - \expect{N}^2$. 
We first calculate $\Pr(N=i)$ for $i = 1,2,3,4$.
\[
\Pr(N=1) = \frac{4} {\binom{52}{13}} \approx 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}\left[\binom{26}{13} - 2\right]}{\binom{52}{13}}
         \approx 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.  
\[
\Pr(N=3) = \frac{\binom{4}{3}
                    \left[\binom{39}{13} - \binom{3}{2}\binom{26}{13} 
                                + 3\right]}
                {\binom{52}{13}} \approx 0.05097,
\]
because there are $\binom{4}{3}$ ways to choose the three suits, 
and $\binom{39}{13}$ ways to choose $13$ cards from the $39$ cards of those
three suits.  But that includes hands with only one or two suits. 
So, using Inclusion-Exclusion, we subtract the
$\binom{3}{2}\binom{26}{13}$ ways to choose two of the three suits
and then choose $13$ cards from the $26$ cards of those suits. 
This subtracts out the three hands with only one suit twice, 
so we add these back. 

Of course, 
\[
\Pr(N=4) = 1 - (\Pr(N=1) +\Pr(N=2) + \Pr(N=3)) \approx 0.9489.
\]
Thus, 
\begin{align*}
\expect{N^2} & = 1 \cdot \Pr(N=1) + 4 \cdot \Pr(N=2) 
                + 9 \cdot \Pr(N=3) + 16 \cdot \Pr(N=4) \\
        & \approx 0 + 0.0004 + 0.4587 + 15.1824 = 15.6415
\end{align*}
This allows us to complete the calculation of the variance:
\[
\variance{N} \approx 15.6415 - (3.9488)^2 \approx 0.0485.
\]
}

\eparts




\problem %source: spring00 ps10-5
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{
The Weak Law of Large Numbers tells us that the proportion 
of heads will approach $1/2$ if the fair coin was picked, 
and it will approach $3/4$ if the other coin was picked. 
But it does not tell us anything about which of these two numbers 
it will approach, 
as we have no information about which coin is picked. 
}

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

\solution{
To guess which coin was picked, 
set a threshold $t$ between $1/2$ and $3/4$. 
If the proportion of heads is less than the threshold, 
guess it was the fair coin; 
otherwise, guess the biased coin. 
Let the random variable $H_n$ be the number of heads in the 
first $n$ flips. 
We need to flip the coin enough times 
so that $\Pr(H_n/n > t) \leq 0.05$ if the fair coin was picked, 
and $\Pr(H_n/n < t) \leq 0.05$ if the biased coin was picked. 
A natural threshold to choose is $5/8$, 
exactly in the middle of $1/2$ and $3/4$. 

$H_n$ is the sum of independent Bernoulli variables, 
which each have variance $1/4$ for the fair coin 
and $3/16$ for the biased coin. 
Using Chebyshev's Inequality for the fair coin, 
\begin{align*}
\Pr\left(\frac{H_n}{n} > \frac{5}{8} \right) 
        & = \Pr\left(\frac{H_n}{n} - \frac{1}{2} > \frac{5}{8} - \frac{1}{2}\right) 
          = \Pr\left(H_n - \frac{n}{2} > \frac{n}{8} \right) \\
        & = \Pr\left(H_n - \expect{H_n} > \frac{n}{8} \right) 
          \leq \Pr\left(|H_n - \expect{H_n}| > \frac{n}{8} \right) \\
        & \leq \frac{\variance{H_n}}{(n/8)^2} 
          = \frac{n/4}{n^2/64} 
          = \frac{16}{n}
\end{align*}
For the biased coin, we have
\begin{align*}
\Pr\left(\frac{H_n}{n} < \frac{5}{8} \right) 
        & = \Pr\left(\frac{3}{4} - \frac{H_n}{n} > \frac{3}{4} - \frac{5}{8}\right) 
          = \Pr\left(\frac{3n}{4} - H_n > \frac{n}{8} \right) \\
        & = \Pr\left(\expect{H_n} - H_n > \frac{n}{8} \right) 
          \leq \Pr\left(|H_n - \expect{H_n}| > \frac{n}{8} \right) \\
        & \leq \frac{\variance{H_n}}{(n/8)^2} 
          = \frac{3n/16}{n^2/64} 
          = \frac{12}{n}
\end{align*}
We are 95\% confident if these are at most $0.05$, 
which is satisfied if $n \geq 320$. 

Because the variance of the biased coin is less that of the fair coin, 
we can do slightly better if make our threshold 
a bit bigger, to about $0.634$, 
which gives 95\% confidence with 279 coin flips. 

Because $H_n$ has a binomial distribution, 
we can get a much better bound using the estimates 
from Lecture 21, 
giving 95\% confidence when $n > 42$. 
}

\eparts

%END   Joe's problems

%BEGIN Ray's problems
%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem9 spring98 (not used)
\problem{\bf [5 points]}

We want to determine the percentage $r$ of people who intend to watch
the final episode of {\em Seinfeld.} Our polling method is the same as
that discussed in lecture: we sample the opinion of $n$ people chosen
uniformly and at random, with replacement.

How many people should be polled so that $r$ is within 3 points of the
true percentage, with probability at least .96?

\solution{
{\bf Solution}

$\epsilon = .03, \delta = .04$

\begin{eqnarray*}
\delta \geq 2 F_{1/2}((1/2- \epsilon)n) & \Rightarrow &
.05 \geq 2  F_{1/2}(0.49n)\\
& \Rightarrow & 0.025 \geq {0.51 \over 0.02}f_{1/2}(0.49n)\\
& \Rightarrow & 0.025 \geq {25.5 \over\sqrt{2n\pi (.49)(.51)}}2^{(H(.49)-1)n}\\
& \Rightarrow & 0.0012285 \geq {2^{(H(.49)-1)n} \over \sqrt{n}}\\
& \Rightarrow & 0.0012285 \geq {2^{-0.000288574n} \over \sqrt{n}}\\
& \Rightarrow & 0.0012285 \geq {(.9998)^n \over \sqrt{n}}\\
\end{eqnarray*}

Choosing $n=10388$ will do it.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem7 spring98; from fall 97 pset11 problem8
%\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


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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem12 spring98; from fall 97 pset12
%\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

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000  PS 11.5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\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*}

}
                           
%%%%%%%%%%%%%%  Fall 2000 PS 11.5    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
\bparts



% [[[variance]]]
%Spring 00, problem set 10.5, problem 3

\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
                                      
%%%%%%%%%%%%%%  Fall 2000  PS 11.5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%[[[expectation, variance]]]
%Spring 00, problem set 10.5, problem 5
\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{
\medskip
\textbf{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{
\medskip
\textbf{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


                  
%%%%%%%%%%%%%%  Fall 2000   PS 11.5  %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%[[[Markov]]]
%Spring 00, problem set 10.5, problem 2
\problem
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{
\medskip
\textbf{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{
\medskip
\textbf{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  



%%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%


%[[[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
          
%%%%%%%%%%%%%%  Fall 2000  PS 11.5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem
% [[[Markov, Chebyshev, Chernoff]]]
% [[[Here's something from Fall 97 final]]]
\bparts
\ppart Knowing only that the average graduating MIT student's
total number of credits is 200, find a tight upper bound for the fraction
of MIT students graduating with at least 235 credits.  (Ignore the fact
that students who graduate do so after at most 700 years; that is, assume
that there is no theoretical upper bound on the possible number of credits
a student may earn.)

\solution{
\medskip
\textbf{Solution:}

We use Markov's inequality $\Pr(X \geq c) \leq E[X]/c$, with $c = 235$,
to obtain the upper bound $200/235 \approx .85$.
}

\ppart Assuming in addition only that the standard deviation of
the total credits per graduating student is~7, give a tight bound on the
fraction of students who can graduate with at least 235 credits.

\solution{
\medskip
\textbf{Solution:}

We use the one-sided Chebyshev inequality 
$\Pr(X \geq E[X] + c \sigma_X) \leq \frac{1 }{1+c^2}$
with $c = 5$ to get an upper bound of $1/26$.
}

\ppart Different information about MIT credits is now provided
by the Registrar.  The standard deviation is not 7 after all.  Instead,
the registrar reports that 30\% of past graduates are EECS majors and half
of them had 235 or more credits.  Only $1/7$th of the non-EECS students
graduated with that many credits.  Use this information and the Chernoff
bound to give a tight upper bound on the probability that among 1000
randomly chosen graduating students, at least 300 have 235 or more
credits.  (You may leave $\ln$ and $e$ in your answer).

\solution{
\medskip
\textbf{Solution:} 

We use the Chernoff bound.  Among 1000 students, let
$N$ be the number with at least 235 credits. So $\expect{N}=
(1/7)700+(1/2)300 = 250$ and

\[\begin{array}{rl}
\pr{N \ge 300} & = \pr{X \geq (1.2)250} \leq e^{-(\ln{1.2} + 1/(1.2) -
 1)(1.2)250} = e^{-(\ln{1.2} -.1666)300}\\
& =  e^{-(.182 -.1666)300} \le e^{-4.6} \approx .01.
\end{array}\]
}
\eparts
        
%%%%%%%%%%%%%%
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%%%%%%%%%%%%%%%FALL 99 %%%%%%%%%%
\problem %{\bf fall96 }

Use the lecture notes to compute upper bounds on the
following probabilities:

\bparts
\ppart 
In a poll with 2000 people, what is the probability that the result is off
by more than $1\%$?

\solution{$\prob{\geq 0.01} = 1 - \prob{< 0.01} \leq 1 -
\left(\frac{1-0.01}{1-0.02}\right) 2^{-2000} \binom{2000}{0.01\times
2000}$}

\ppart
In 1000 independent coin flips, what is the probability of getting 
at least 600 heads?

\solution{ $\prob{\geq 600} = 1-\prob{< 600}(n=1000,\alpha=3/5)\leq 1 - 
2^{-1000}{\binom{1000}{600}}{\frac{1-3/5}{1-6/5}}$}


\ppart
In a noisy communication channel with $10\%$ error rate, what is the
probability that out of 1000 transmitted bits, at least 200 bits are 
wrongly transmitted ({\em i.e.}, {\tt 1} is received as {\tt 0} and 
vice versa)?

\solution{
g$\prob{\geq 200} = 1-\prob{< 200}(n=1000,\alpha=1/5)\leq 1 - 
2^{-1000}{\binom{1000}{200}}{\frac{1-1/5}{1-2/5}}$}
\eparts

\fi



\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



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 appraoching 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


%END   Tina's problems


\end{problems}

\end{document}



