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

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
\newcommand{\mquote}[1]{\mathify{\textrm{``$#1$''}}}
\newcommand{\mdash}{\mathify{\textrm{-}}}

\askaboutsolutions

\begin{document}
\ifshowsolutions
\psol{115}{Problem Set 11.5}{December 8, 2000}
\else
\handout{ps115}{Problem Set 11.5}{December 7, 2000}
\fi

\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{Self-study:}  
All about variance, from Section 2 of Lecture Notes 25.

\textbf{Reading:} Lecture notes 25 and 26;
Rosen, Sections 4.4, 4.5,; \\
(Optional) Ross Sections 4.6, 8.2, 8.5.

\textbf{Final Exam:} 
Covers the entire course, with more emphasis on the last 8 lectures.  The final will be held Thursday, December 21, 1:30 p.m. to 4:30 p.m. in Rockwell.


\medskip
\begin{problems}

% [[[Wald's theorem]]]
%Spring 00, problem set 10.5, problem 9
\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{
\medskip
\textbf{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{
\medskip
\textbf{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 +
2Ex(XY) - 2Ex(X)Ex(Y) = var(X) + var(Y)$. 
}

\eparts



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




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


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


\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


\problem
% [[[random walks]]]
%[[[Here's an idea; it needs polishing, solving, etc.]]]

The latest recount of the Florida votes has yielded exactly 3 million
votes for each.
The Florida Supreme Court has decided to allow repeated 
recounts of all the votes in Florida, until the difference between the
two is at least 1000 votes.

It turns out that recounting of votes has the odd property that it can
be modeled by a random walk.
Specifically, each recount has probability .4 of yielding exactly 100
more votes for Bush than the previous count, 
and exactly .6 of giving 100 more votes for Gore. (Unlike the current election, in this scenario, 
the total number of votes after each recount is constant.)

\bparts
\ppart
What is the probability of Bush eventually winning?
Of Gore eventually winning?  Of neither eventually winning (that is,
recounts go on forever)?

\solution{
\medskip
\textbf{Solution:}
Let $P_n$ be the probability that Bush wins the election where $n$ represents
the net number of recounts won by Bush (for example, if Bush wins the first
one and then loses the second and third, $n=-1$).  Bush wins if he gets 1000
more votes (n=10) and loses if Gore gets 1000 more votes (n=-10).  So, we can write
the following recurrence for $P_n$.

\[
P_n = \left\{
\begin{array}{cl}
0 & \text{if $n = -10$} \\
1 & \text{if $n = 10$} \\
.4*P_{n+1} + .6*P_{n-1} & \text{if $-10 < n < 10$}
\end{array}
\right.
\]

This leads to the recurrence 
\[ .4*P_{n+1}-P(n)+.6*P{n-1}=0, \] 
which has the
characteristic equation $r^2-2.5*r+1.5=0$, where $P_{10}=1$ and $P_{-10}=0$.
Using the quadratic formula, we find that the roots are r=1.5 and r=1.  
This gives us the solution:

\begin{eqnarray*}
P_n     & = &   A * \left( \frac{3}{2} \right)^n + B * (1)^n
\end{eqnarray*}

Using the boundary conditions, $P_{10}=1$ and $P_{-10}=0$, we can find the constants $A$ and $B$.  Substituting these two conditions into the general form gives:

\begin{eqnarray*}
0       & = &   A*1.5^{10} + B\\
1       & = &   A*1.5^{-10} + B
\end{eqnarray*}

Solving this system, we get $A=.0173$, $B=-3*10^{-4}$. Finally, solving for $P_0$, the probability that
Bush eventually wins the election:
\begin{eqnarray*}
P_0 	& = &	.0173*(1.5)^0 + -3*10^{-4}*(1)^0\\
	& = &	.0170
\end{eqnarray*}
So, the probability Bush wins is .017.  By the analysis of theorem 3.1 in Lecture 26, the probability that no one ever wins is 0, and so the probability that Gore eventually wins is 1-.017 = .983
}


\ppart 
What is the expected duration of the election (assume one recount per day)?

\solution{
\medskip
\textbf{Solution:}

By the analysis from Section 3 of Lecture 26, we have the following formula for $E_n$, the expected number of recounts of the election, given Bush is currently ahead by $n$ recounts (note that $n$ can range from -10 to 10).  

\[
E_n = \left\{
\begin{array}{cl}
0 & \text{if $n = -10$} \\
0 & \text{if $n = 10$} \\
1 + .4*E_{n+1} + .6*E_{n-1} & \text{if $-10 < n < 10$}
\end{array}
\right.
\]

Solving the homogeneous part of this recurrence gives the equation

\begin{eqnarray*}
E_n     & = &   A * \left( \frac{1-.4}{.4} \right)^n + B\\
	& = &	A*1.5^n + B
\end{eqnarray*}

Solving the particular part of the recurrences gives us $E_n = \frac{n}{1-(2*.4)}$.  Adding the two parts together gives a complete solution of the form:

\begin{eqnarray*}
E_n 	& = &	A*(1.5)^n + B + \frac{n}{.2}
\end{eqnarray*}

Using the boundary conditions $E_{-10} = E_{10} = 0$, we get the system of equations:

\begin{eqnarray*}
0 & = & A*(1.5)^{10} + B + \frac{10}{.2}\\
0 & = & A*(1.5)^{-10} + B - \frac{10}{.2}
\end{eqnarray*}

This gives $A=-1.73467$, $B=50.03008$.  Finally, solving the equation given that $n=0$ gives us the desired answer.  $E_0 = -1.73467*(1.5)^n + 50 + \frac{0}{.2} = 48.3$ days until a winner is declared.
\\
}

%%% BEGIN COMMENTING OUT LAST PART!  
%%% using \iffalse \fi construct to do so...

\iffalse

\ppart 
Gore has decided that if Bush wins according to this process, he
(Gore) will throw in the towel.
Bush, however, has decided that if Gore wins according to this
process, he (Bush) will insist on continuing the recounts forever until he
(Bush) has a 1000 vote margin.  
Now assume that Gore wins, according to this process.

i) How many recounts would be expected to occur until Bush wins?\\
ii) What is the probability that Bush eventually wins?

\fi

%% END COMMENTING OUT.

\eparts



\end{problems}


\end{document}




