\documentclass[12pt]{article}
\usepackage{latex-macros/course}


%\hidesolutions
%\showsolutions

\begin{document}

\inclassproblems{14, Wed.}

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

% 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}
\pr{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, that is,
\begin{eqnarray*}
\pr{X=235} &=& \frac{200}{235}\\
\pr{X=0} &=& \frac{35}{235}\\
\pr{X=x} &=& 0\text{ for all other }x.
\end{eqnarray*}
}

\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}
\pr{X \geq 235} = \pr{X - 170 \geq 235 - 170} =  \pr{Y \geq 65}
\end{displaymath}

Therefore:
\begin{eqnarray*}
\pr{X \geq 235}
  & =    & \pr{Y \geq 65} \\
  & \leq & \frac{\expect{Y}}{65} \\
  & \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$,
that is, $x=235$, and one at $(x-170)=0$, that is, $x=170$.
\begin{eqnarray*}
\pr{X=235} &=& (200-170)/(235-170)=30/65\\
\pr{X=170} &=& 35/65\\
\pr{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.  What is the
Chebyshev bound on the fraction of students who can graduate with at least
235 credits?

\solution{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*}
\pr{X \geq 235}
& = & \pr{Y \geq 65} \\
& = & \pr{Y - \expect{Y} \geq 65 - \expect{Y}} \\
& = & \pr{Y - 30 \geq 35} \\
& \leq & \pr{ \abs{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!
}

\end{problemparts}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
\begin{problemparts}
\ppart
Show that Markov's Theorem only applies to nonnegative random variables.  That
is,  give an example of a random variable to which Markov's Theorem gives
a {\em wrong} answer.
\solution{
Here is one possible answer:  
Let $R$ be -10 with probability $1/2$ and 10 with
probability $1/2$.  Then we have:
\[
\expect{R} = -10 \cdot \frac{1}{2} + 10 \cdot \frac{1}{2} = 0
\]
Suppose that we now tried to compute $\pr{R \geq 5}$ using Markov's
Theorem:
\begin{displaymath}
  \pr{R \geq 5} \leq \frac{\expect{R}}{5} = \frac{0}{5} = 0.
  \end{displaymath}
  This is the wrong answer!  Obviously, $R$ is at least 5 with
  probability $1/2$.
}


\ppart Suppose $R$ is a random variable that is always at least $-10$ and
has expectation $0$.  Since $R$ may be negative, Markov's theorem does not
apply directly.  Still, use Markov's theorem to show that the probability
that $R$ is $\geq 5$ is at most $2/3$.

\solution{Let $T \eqdef R+10$.  Now $T$ is a nonnegative random variable
with expectation $\expect{R + 10} = \expect{R}+10= 10$, so Markov's
Theorem applies and tells us that $\pr{T \geq 15} \le 10/15 = 2/3$.  But
$T \geq 15$ iff $R \geq 5$, so $\pr{R \geq 5} \leq 2/3$.}

\iffalse
\ppart
Prove the following:
\begin{theorem}
\label{th:below}
Let $l$ be a real number and let $R$ be a random variable such that $R
\leq l$.  For all $x < l$, we have:
\[
\pr{R \leq x} \leq \frac{l - \expect{R}}{l - x}.
\]
\end{theorem}
\solution{
The event that $R \leq x$ is the same as the event that $l - R \geq l -
x$.  Therefore:
\begin{align}
\pr{R \leq x} &  = \pr{l - R \geq l - x}\notag\\
 & \leq \frac{\expect{l - R}}{l - x}. & \text{(by Markov' Theorem)}\label{LR}
 \end{align}
 Applying Markov's Theorem in line~(\ref{LR}) is permissible
 since $l - R$ is a nonnegative random variable and $l - x > 0$.
}
\fi

\end{problemparts}
\end{problem}

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


\begin{problem}
There are $n$ people at a circular table in a Chinese restaurant.  On the
table, there are $n$ different appetizers arranged on a big Lazy Susan.
Each person starts munching on the appetizer directly in front of him or
her.  Then someone spins the Lazy Susan so that everyone is faced with a
random appetizer.  In class, we saw that the expected number of people
that end up with the appetizer that they had originally is 1.

Let $X_i$ be the indicator variable for the $i$th person getting their own
appetizer back.  Let $S_n$ be the total number of people who get their own
appetizer back, so $S_n = \sum_{i=1}^n X_i$.

\begin{problemparts}

\problempart What is $\expect{X_i^2}$?

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

\problempart For $i \neq j$, what is $\expect{X_i X_j}$?

\solution{
The probability that $X_i$ and $X_j$ are both 1 is $1/n$.  
Thus $X_i X_j = 1$ with probability $1/n$, and is zero
otherwise.  So $\expect{X_i X_j} = 1/n$.
}

\problempart What is  $\expect{S_n^2}$? 

\solution{
\begin{eqnarray*}
\expect{S_n^2} & = & \sum_{i,j} \expect{X_i X_j} \\
         & = & n^2 \cdot \frac{1}{n} \\
         & = & n.
\end{eqnarray*}

Alternatively, we observe directly that
\[
\pr{S_n^2=n^2} \pr{S_n = n} =  \frac{1}{n}
\]
and 
\[
\pr{S_n^2=0} \pr{S_n = 0} = \frac{n-1}{n},
\]
so
\[
\expect{S_n^2} = n^2 \frac{1}{n} + 0\cdot \frac{n-1}{n} = n.
\]
}

\problempart What is $\variance{S_n}$?

\solution{
\begin{eqnarray*}
\variance{S_n} & = & \expect{S_n^2} - \expectsq{S_n} \\ 
       & = & n - 1^2 \\
       & = & n - 1.
\end{eqnarray*}
}

%\problempart Explain why you cannot use the variance of sums formula to
%calculate $\variance{S_n}$.
%
%\solution{The indicator random variables, $X_i$, are not even pairwise
%independent.}

\problempart Discuss the accuracy of the Chebyshev Bound on the
probability that $S_n$ is distance $x$ from its expectation as $x$ ranges
over integers between 1 and $n$.

\solution{The bound $\variance{S_n}/x^2$ is trivial ($> 1$) unless $x^2>
variance{S_n}$, that is, unless $x \geq \floor{\sqrt{n-1}+1}$.  In the
case that $x$ equals this minimum value, it still gives yields a near
trivial bound of $(n-1)/\floor{\sqrt{n-1}+1} \approx 1$, whereas actually,
\[
\pr{\abs{S_n-1} \geq x} = \frac{1}{n}
\]
for all $x \leq n-1$, and
\[
\pr{\abs{S_n-1} \geq x} = 0
\]
for $x > n-1$.  At $x=n-1$, the Chebyshev Bound is $(n-1)/(n-1)^2 =
1/(n-1)$ which is still a bit larger than the actual value of $1/n$.
Finally, at $x=n$, the Chebyshev Bound is $(n-1)/n^2 = 1/n - 1/n^2$
whereas the actual probability is zero.}

\end{problemparts}
\end{problem}


\begin{problem}
For any random variable, $R$, with $\expect{R} = \mu$ and $\variance{R} =
v$, the Chebyshev Bound says that for any real number $x >0$,
\[
\pr{\abs{R-\mu} \geq x} \leq \frac{v}{x^2}.
\]
Show that for any real number, $\mu$, and real numbers $v,x >0$, there is
an $R$ for which the Chebyshev Bound is tight, that is,
\begin{equation}\label{t}
\pr{\abs{R} \geq x} = \frac{v}{x^2}.
\end{equation}
\hint Assume $\mu = 0$ and let $R$ be three valued with values $0, -x,$
and $x$.

\solution{
From the hint, we aim to find an $R$ with $\expect{R}=0$ and $\variance{R}
= v$ that satisfies equation~\eqref{t}.

Using the further hint that $R$ takes only values $0,-x,x$, we have
\[
0 = \expect{R} = x\pr{R=x} - x\pr{R=-x} = x\paren{\pr{R=x} - \pr{R=-x}}
\]
so
\begin{equation}\label{x-x}
\pr{R=x} = \pr{R=-x},
\end{equation}
since $x>0$.  Also,
\[
v  = \variance{R}  = \expect{R^2}  = x^2\pr{R=-x} + x^2\pr{R=x}  = 2x^2\pr{R=x},
\]
so
\[
\pr{R=x} = \frac{v}{2x^2}.
\]
This implies
\[
\pr{R=0} = 1 - \pr{R=-x} - \pr{R=x} = 1- \frac{v}{x^2},
\]
which completely determines the distribution of $R$.  Moreover,
\[
\pr{\abs{R} \geq x} = \pr{R=-x}+\pr{R=x} = \frac{v}{x^2}
\]
which confirms~\eqref{t}.

Finally, given $\mu,x,$ and $v$, if we let $R'\eqdef R+\mu$, then $R'$
will be the desired random variable for which the Chebyshev Bound is
tight.}

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
The covariance, $\covariance{X}{Y}$, of two random variables, $X$ and $Y$,
is defined to be $\expect{XY} - \expect{X}\expect{Y}$.  Note that if two
random variables are independent, then their covariance is zero.

\bparts 

\ppart Give an example to show that having $\covariance{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{array}{|c|c|c|} \hline
X & Y & P \\ \hline
-1 & 1 & 1/3 \\ \hline
0 & 0 & 1/3 \\ \hline
1 & 1 & 1/3 \\ \hline
\end{array}\]

Note that $X$ and $Y$ are not independent:
\[
\pr{X=1 \mbox{ \& } Y=1} = 1/3 \neq 2/9 = \pr{X=1}\pr{Y=1}.
\]
But since $XY=X$ and $\expect{X}=0$, we have
\[\expect{X}\expect{Y} = 0\cdot \expect{Y} = 0 = \expect{X} = \expect{XY}.
\]
Thus $\covariance{X}{Y} = 0$.}

\ppart Let $X_1,\ldots,X_n$ be random variables.  Prove that
\[
\variance{X_1+\cdots+X_n} = \sum_{i=1}^n \variance{X_i} + 2\sum_{i<j}
\covariance{X_i}{X_j}.
\]

\solution{
\begin{eqnarray*}
\variance{X_1+\cdots+X_n} & = & \expect{(X_1 + \cdots +X_n)^2} -
\expectsq{X_1+\cdots+X_n} \\
& = & \expect{\sum_i X_i^2+(\sum_{i < j}2X_iX_j)} - \paren{\sum_i\expect{X_i}^2 +
\sum_{i<j}2\expect{X_i}\expect{X_j}}\\
& = & \sum_i \expect{X_i^2} + \sum_{i<j} 2\expect{X_iX_j} - \sum_i\expect{X_i}^2 -
\sum_{i<j} 2\expect{X_i}\expect{X_j} \\
& = & \sum_i \expect{X_i^2} - \expect{X_i}^2 + \sum_{i<j}2(\expect{X_iX_j} - \expect{X_i}\expect{X_j})
\\
& = & \sum_i \variance{X_i} + 2\sum_{i<j} \covariance{X_i}{X_j}.
\end{eqnarray*}
}

\eparts

\end{problem}

\end{document}


