        \problemdata       % Takes 5 *mandatory* arguments
        {variance-6}             % latex-friendly label for the prob.
        {variance}               % The topic of the problem content.
        {Velleman}               % Source (if known)
        {S98 PS11-7; F97 PS11-8} % Usage (list ones you are aware of).
        {Theory Pig, S02}        % Last revision info (author, date).
\begin{problem}
% [[[Markov, Chebyshev, Chernoff]]]
% Variants of this problem appeared in:
% FA 1997, Final
% SP 1999, tutorial 13
% FA 2000, PS 11.5
% FA 2001, TUT 12
\begin{problemparts}
\problempart 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$.
}

\problempart 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$.
}

\problempart 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}\]
}
\end{problemparts}
\end{problem}        
%%%%%%%%%%%%%%
% Note, this ridiculously long version of the solutions came from fall 01

%\problem %From S99 Tutorial 13

%Suppose you have learned that the average graduating MIT student's
%total number of credits is 200.

%\bparts

%\ppart Knowing only this average, use Markov's inequality to find a best
%possible 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 a century---that is, assume that there is no theoretical
%upper bound on the possible number of credits a student may earn.)

%Explain why this is a best possible bound.  In other words, describe a
%distribution for which this bound holds with equality.

%\solnospace{ 
%By Markov's inequality $\prob{X\geq c}\leq\expect{X}/c$, with 
%$c = 235$, giving the upper bound $200/235 \approx 0.85$.

%The bound is attained with equality at the two-point distribution which has
%non-zero values only at 0 and 235, i.e.
%\begin{eqnarray*}
%\prob{X=235} &=& 200/235\\
%\prob{X=0} &=& 35/235\\
%\prob{X=x} &=& 0\text{ for all other }x
%\end{eqnarray*}

%You might wonder how we got to this particular distribution, since the
%space of all possible probability functions is very large \texttt{:-)}.
%This function could be derived intuitively as follows:

%Consider any distribution with the given mean, $\expect{X}=200$.  We can
%`shift' this distribution around, like sand on a see-saw, subject to the
%constraint that it remains balanced around the mean.  We want to maximize
%the portion of the distribution that is to the right of the point $x=235$.

%How can we do this?  Look at the portion of the distribution to the right
%of $x=235$.  We need to minimize this portion's contribution to the mean
%(so we can then maximize its volume).  \iffalse UNCLEAR, SHOULD BE REVISED
%TO CONSISTENT MAINTAIN THE SEE-SAW ANALOGY\fi For this, we must move it
%as close to the mean as possible, i.e. we pile it all up at the point
%$x=235$.

%Similarly, we need to maximize the contribution of the distribution to
%the left of the mean.  To do this, we move it \emph{away} from the
%mean, i.e. to the left as far as possible.  Since $X$ is non-negative,
%this means that it all piles up at the point $x=0$.

%Mathematically
%\iffalse
%\begin{math}
%\begin{array}[rcrlcrl]
%\expect{X} & = & \expect{X|X\ge c} & \pr{X\ge c} & + & \expect{X|X<c}
%& \pr{X<c}\\
%&\ge&c\cdot&\pr{X\ge c}&+&0\cdot&\pr{X<c}\\
%&=&\multicolumn{5}{l}{c\cdot\pr{X\ge c}}
%\end{array}
%\end{math}
%\fi
%\begin{eqnarray*}
%\expect{X}&=&\expect{X|X\ge c}  \pr{X\ge c}  +  \expect{X|X<c}
% \pr{X<c}\\
%&\ge&c\cdot\pr{X\ge c}+0\cdot\pr{X<c}\\
%&=&c\cdot\pr{X\ge c}
%\end{eqnarray*}
%Equality holding iff $\expect{X|X\ge c}=c$ AND $\expect{X|X<c}=0$,
%i.e. $x\ge c\Rightarrow x=c$ and $x<c\Rightarrow x=0$.
%}

%\ppart Suppose you are now told that no student can graduate with fewer
%than 170 units.  How does this allow you to improve your previous answer?

%As in the first part, show that this is the best possible bound.

%\solnospace{
%We can now apply Markov's inequality to the nonnegative variable $X -
%170$, obtaining 
%$$\prob{X \geq 235} = \prob{X - 170 \geq 235 - 170} \leq
%\expect{X - 170}/(235 - 170) = 30/65 \approx 0.46$$

%As above, we achieve an optimum (equality in the bound) when our
%distribution consists of two spikes: one at $(x-170)=c-170$,
%i.e. $x=235$, and one at $(x-170)=0$, i.e. $x=170$.
% \begin{eqnarray*}
%\prob{X=235} &=& (200-170)/(235-170)=30/65\\
%\prob{X=170} &=& 35/65\\
%\prob{X=x} &=& 0\text{ for all other }x
%\end{eqnarray*}
%}

%\ppart Now suppose you further learn that the standard deviation of the
%total credits per graduating student is~7.  Give a best possible bound on the
%fraction of students who can graduate with at least 235 credits.

%(Optional) As in previous parts, show that this is a best possible
%bound. 

%\solnospace{
%Use the one-way Chebyshev inequality
%\[
%\prob{X \geq \expect{X} + c \sigma_X} \leq \frac{1}{1+c^2}
%\]
%with $c = 5$ to get an upper bound of $1/26$.

%The correct distribution yet again turns out to be a two-point
%distribution.
%\begin{eqnarray*}
%\prob{X=235} &=& 1/26\\
%\prob{X=198.6} &=& 25/26\\
%\prob{X=x} &=& 0\text{ for all other }x
%\end{eqnarray*}

%Intuitively showing that $1/26$ this is the best possible bound turns out to
%be somewhat tricky.  To be honest, this question baffled the staff for
%quite a while!  We use the following Lemma:

%\begin{lemma*}\label{eq:variancelemm}
%For any random variable $X$, and any disjoint events $Y_1,
%Y_2, Y_3...$ whose union spans the sample space,
%\begin{eqnarray*}
%\variance{X}+\expectsq{X}&=&\expect{X^2}\\
%&=&\sum_i\pr{Y_i}\expect{X^2|Y_i}\\
%&=&\sum_i\pr{Y_i}\left(\variance{X|Y_i}+\expectsq{X|Y_i}\right)
%\end{eqnarray*}
%\end{lemma*}

%Now suppose we're given an arbitrary
%probability distribution (mean $\mu$, variance $\sigma^2$) and want to tweak it
%around to maximize $\pr{X\ge 235}$.  We can do this in two steps.
%First, we shift it to minimize the variance while maintaining the mean
%and the probability that $X\ge 235$.  Then, we shift around this new
%distribution while maintaining the mean and raising the variance to
%its original value of $\sigma^2$, and simultaneously increasing $\pr{X\ge
%  235}$.

%Define $Y_1\equiv(X<235)$, $Y_2\equiv(X\ge 235)$.  Then let us maintain
%$\expect{X}$, $\pr{Y_1}$, $\expect{X|Y_1}$, and the distribution of
%$\pr{X|Y_2}$ as constant.  From the Lemma\iffalse
%~\eqnref{eq:variancelemm}\fi, it follows that we can minimize
%$\variance{X}$ iff we minimize $\variance{X|Y_1}$.  As it happens, we can
%bring $\variance{X|Y_1}$ down to 0.  We simply compress the pdf left of
%235 into a spike at its mean value.  This will maintain $\pr{Y_1}$ and
%$\expect{X|Y_1}$, and clearly will also maintain
%$\expect{X}=\pr{Y_1}\expect{X|Y_1}+\pr{Y_2}\expect{X|Y_2}$.

%Having done this, we can further reduce the variance of the
%distribution by applying the same process to $Y_2$:  that is,
%compressing the pdf for $X|Y_2$ into a spike at its mean value.

%We now have a pdf with two spikes --- one to the left of $x=200$ and
%one to the right of $x=235$.  We can still reduce the variance
%further!  We shift the right spike to the left until it hits $x=235$,
%while simultaneously shifting the left spike to the right in such a
%way as to maintain the expected value (200) of the overall system.  Since
%both spikes are moving towards the mean, the variance will fall.  We
%now have the lowest possible variance we can achieve without changing
%$\expect{X}$ or $\pr{X\ge 235}$.

%We now move to the second stage:  we shift the left spike to the
%left, while reducing its height and adding to that of the right
%spike, in such a way that the center of mass of the two spikes stays
%the same.  Doing so will potententially raise the variance of the
%whole pdf;
%hence, we can only continue this shift until the variance has risen back to
%its original value, $\sigma^2$.

%What is the eventual result of all this shifting?  We have a 2-spike
%distribution with the mean at $\mu=200$, the variance $\sigma^2=49$
%and the right spike at the point $x=\mu+c\sigma=235$.  Let $p_1$ and
%$p_2$ be the heights of the left and right spikes, and $\delta$ be the
%distance of the left spike from the mean.  Then

%\begin{eqnarray*}
%p_1+p_2&=&1\\
%p_1\delta&=&p_2c\sigma\\
%p_1\delta^2+p_2c\sigma^2&=&\sigma^2
%\end{eqnarray*}
%Solving gives $\pr{X\ge\mu+c\sigma}=p_2=1/(1+c^2)$, our desired
%optimal bound.
%}

%\eparts


