\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightyear}{2002}
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{12M}

%%%% MONDAY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Gambling Game from the lecture notes
\begin{problem}

Consider the following two gambling games.

Game A: We win \$2 with probability $2/3$ and lose \$1 with probability
$1/3$.

Game B: We win \$1002 with probability $2/3$ and lose \$2001 with
probability $1/3$.

\begin{problemparts}
\problempart What is the expected win in each case?

\solution{From the Notes: Let random variables $A$ and $B$ be the
payoffs for the two games.  For example, $A$ is 2 with probability 2/3
and -1 with probability 1/3.  We can compute the expected payoff for
each game as follows:

\begin{eqnarray*}
\expect{A} = 2 \cdot \frac{2}{3} + (-1) \cdot \frac{1}{3} = 1, \\
\expect{B} = 1002 \cdot \frac{2}{3} + (-2001) \cdot \frac{1}{3} = 1.
\end{eqnarray*}

We have the same probability, 2/3, of winning each game and the same
expected return for each game.
}

\problempart What is the variance in each case?  

%\insolutions{\bf NOTE to TAs: the point of this problem is to make sure
%they understand what calculating variance means by doing a concrete
%example - they should be able to use BOTH formulas of variance to do
%this.}
%
\solution{The variances of the two games are very different. We can
compute the $\variance{A}$ by working ``from the inside out'' as
follows:

\begin{eqnarray*}
A - \expect{A}
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        -2 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(A - \expect{A})^2
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        4 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\expect{(A - \expect{A})^2}
        & = &   1 \cdot \frac{2}{3} + 4 \cdot \frac{1}{3} \\
\variance{A} & = & 2.
\end{eqnarray*}

Similarly, we have for $\variance{B}$:
\begin{eqnarray*}
B - \expect{B}
        & = &   \left\{
                \begin{array}{cl}
                        1001 & \text{ with probability } \frac{2}{3} \\
                        -2002 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(B - \expect{B})^2
        & = &   \left\{
                \begin{array}{cl}
                        1,002,001 & \text{ with probability } \frac{2}{3} \\
                        4,008,004 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\expect{(B - \expect{B})^2}
        & = &   1,002,001 \cdot \frac{2}{3} + 4,008,004 \cdot \frac{1}{3} \\
\variance{B} & = & 2,004,002.
\end{eqnarray*}

The variance of Game A is 2 and the variance of Game B is more than
two million!  Intuitively, this means that the payoff in Game A is
usually close to the expected value of \$1, but the payoff in Game B
can deviate very far from this expected value.

High variance is often associated with high risk.  For example, in ten
rounds of Game A, we expect to make \$10, but could conceivably lose
\$10 instead.  On the other hand, in ten rounds of game B, we also
expect to make \$10, but could actually lose more than
\$20,000!
}
\end{problemparts}
\end{problem}

%%---------------------------------------------------------------%%

% From fall 01 tut 12
% editted from the S99 Tutorial 13 version to add distribution questions
% topics: understand Markov. Chebyshev bounds and distributions that satisy bounds

\begin{problem}
Suppose you have learned that the average graduating MIT student's
total number of credits is 200.

\begin{problemparts}

\problempart 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. \footnote{Ignore the fact that there are
practical limits to the amount of time a student can stay at MIT and remain
sane; That is, assume that there is no bound on the number of credits a student
may earn.}

\solution{ 
Let $X$ be a random variable with a distribution equal to that of the 
graduating MIT students' credit count. We are given that $\expect{X} = 200$. 
By Markov's inequality:

\begin{displaymath}
\prob{X\geq 235}\leq\frac{\expect{X}}{235} = \frac{200}{235} \approx 0.85
\end{displaymath}

}

\problempart Demonstrate that this is a best possible bound by giving a
distribution for which this bound holds with equality.

\solution{ 
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,
%\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}
\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$.
}

\problempart Suppose you are now told that no student can graduate
with fewer than 170 units.  How does this allow you to improve your
previous bound? As before, show that this is the best possible bound.

\solution{
We can now apply Markov's inequality to the nonnegative variable $Y = X -
170$, with expectation $\expect{Y} = \expect{X-170} = \expect{X} - 170 = 30$.
So,
\begin{displaymath}
\prob{X \geq 235} = \prob{X - 170 \geq 235 - 170} =  \prob{Y \geq 65}
\end{displaymath}

Therefore:
\begin{eqnarray*}
\prob{X \geq 235}
  & =    & \prob{Y \geq 65} \\
  & \leq & \frac{\expect{Y}}{64} \\
  & \leq & \frac{30}{65} \approx 0.46
\end{eqnarray*}

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

\problempart Now suppose you {\em 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.

\solution{ Use the Chebyshev inequality to bound the probability.  The
variance of $X$ is the square of the standard deviation, or 49. The
variance of $Y$ is the same as that of $X$, by the linearity of
variance. That is, $\variance{Y} = \variance{X - 170} = \variance{X} -
\variance{170} = 49 - 0$. (The variance of a constant is 0).
\begin{eqnarray*}
\prob{X \geq 235}
& = & \prob{Y \geq 65} \\
& = & \prob{Y - \expect{Y} \geq 65 - \expect{Y}} \\
& = & \prob{Y - 30 \geq 35} \\
& \leq & \prob{| Y- 30 | \geq 35} \\
& \leq & \frac{\variance{Y}}{35^2} \\
& \leq & \frac{49}{1225} = \frac{1}{25} 
\end{eqnarray*}

This is a much better bound than before!

}
%(Optional*) As in previous parts, show that this is a best possible
% bound. 
%
%{\bf Note to TAs: in this case proving that this is the best bound
%given the data is much harder. If students want to discuss it fine,
%but make sure they do other parts before they spend too much time
%here.}
%
%here is a distribution courtesy Ashish:
%
%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.
%}
\end{problemparts}
\end{problem}

%%---------------------------------------------------------------%%
\begin{problem}
In this problem we will derive Chebyshev's Theorem from a corollary of
Markov's Theorem.

\begin{problemparts}
\problempart Explain why the following corollary of Markov's theorem holds:
\begin{corollary}
For any random variable~$R$, any positive integer~$k$, and any $x > 0$,
\[
\pr{\abs{R} \geq x} \leq \frac{\expect{\abs{R}^k}}{x^k}.
\]
\end{corollary}

\solution{This can be seen by letting the random variable in Markov's theorem be $\abs{R}^k$, which is nonnegative for any random variable $R$ and positive integer $k$. Notice as well that since $\abs{R} \geq x$ iff $\abs{R}^k \geq x^k$, the probabilities of the two events are the same.  Combining these facts we get, 
\[
\pr{\abs{R} \geq x} = \pr{\abs{R}^k \geq x^k} \leq \frac{\expect{\abs{R}^k}}{x^k}.
\]

\textbf{Note:} Even though Markov's theorem applies only to nonnegative random variables, this corollary applies to \emph{all} random variables.  This implies that Chebyshev's theorem, derived in the next part, also applies to all random variables.
}


\problempart Use the above corollary to prove the following:

\begin{theorem}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\end{theorem}

(Hint: Consider the case where $k=2$).

\solution{
The special case of this corollary when $k=2$ can be applied to bound the
random variable, $\abs{R - \expect{R}}$, that measures $R$'s
deviation from its mean.  Namely
\begin{equation}\label{chebE2}
\pr{\abs{R - \expect{R}} \geq x}
  = \pr{(R - \expect{R})^2 \geq x^2} \leq \frac{\expect{(R - \expect{R})^2}}{x^2},
\end{equation}
where the inequality follows from the corollary applied
to the random variable, $\abs{R - \expect{R}}$.  So we can bound the
probability that the random variable~$R$ deviates from its mean by
more than~$x$ by an expression decreasing as $1/x^2$ multiplied by the
constant $\expect{(R - \expect{R})^2}$.  This constant is the
\emph{variance of~$R$}. Hence,

\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
}

\end{problemparts}
\end{problem}

%%---------------------------------------------------------------%%

\begin{problem}
Prove that the following two formulas for calculating variance are equivalent:
\begin{eqnarray}
\variance{R} \eqdef \expect{(R - \expect{R})^2}.\\
\variance{R} = \expect{R^2} - \expectsq{R},
\end{eqnarray}

\solution{From the Notes:
Remember that $\expect{R^2}$ is generally not equal to $\expectsq{R}$.
The expected value of a product is the product of the expected values only
for independent variables, and $R$ is not independent of itself unless it
is constant.
\begin{proof}
  Write $\mu = \expect{R}$.  Then
  \begin{eqnarray*}
    \variance{R}
        & = &   \expect{(R - \mu)^2} \\
        & = &   \expect{R^2 - 2 R \cdot \mu + \mu^2} \\
        & = &   \expect{R^2} - \expect{2 R \cdot \mu} + \expect{\mu^2} \\
        & = &   \expect{R^2} - 2 \expect{R} \cdot \mu + \mu^2 \\
        & = &   \expect{R^2} - 2 \expectsq{R} + \expectsq{R} \quad
           \text{(definition of $\mu$)}\\
        & = &   \expect{R^2} - \expectsq{R}.
  \end{eqnarray*}
  The first step uses the definition of variance.  In the second step,
  we multiply out the squared term.  The third step uses linearity of
  expectation.  There are two transformations on the fourth line.  In
  the second term, we pull the constant $2 \mu$ out of the
  expectation.  In the third term, we use the fact that the
  expectation of a constant, namely $\mu^2$, is that constant.  The
  final step is simplification.
\end{proof}
}
\end{problem}


\appendix
\section{Appendix}
\setcounter{secnumdepth}{0}
%%%%%%%%%%%%%%%%%%%%%%%% EXPECTATION %%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{definition}
The \emph{expectation} of random variable, $R$, is:
\begin{equation}
\expect{R} \eqdef \sum_{r \in \range{R}} r \cdot \pr{R = r}
\end{equation}
\end{definition}

%%%%%%%%%%%%%%%%%%%%%%%%% VARIANCE %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{definition}
The \emph{variance}, $\variance{R}$, of a random variable, $R$, is:
\[
\variance{R} \eqdef \expect{(R - \expect{R})^2}.
\]
Variance can also be equivalently defined as:
\[
\variance{R}\eqdef \expect{R^2} - \expectsq{R},
\]
\end{definition}

%%%%%%%%%%%%%%%%%%%%%%%%%% MARKOV %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}[Markov's Theorem]
  If R is a nonnegative random variable, then for all $x > 0$
  \begin{displaymath}
    \pr{R \geq x} \leq \frac{\expect{R}}{x}.
  \end{displaymath}
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%% Chebyshev %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\end{theorem}

\end{document}

