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

%\usepackage{psfig}

\input{macros-course}


\begin{document}

\tutn{20}{12/3/99}{December 3, 1999}

\begin{problems}

\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, 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.)

\solution{

Use Markov's inequality $\prob{X \geq c} \leq \expect{X}/c$, with $c
= 235$, to obtain the upper bound $200/235 \approx 0.85$.

}

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

\solution{

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

}

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

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

\eparts


\problem \textbf{Law of Large Numbers.}   %From S99 Final exam.

Let $G_1, G_2, \dots$ be a
sequence of mutually independent random variables such that $\variance{G_i}
\leq b$ for some $b \geq 0$ and all $i \geq 1$.  Let
\[
S_n ::= G_1 + G_2 + \cdots + G_n.
\]
Prove that for every $\epsilon > 0$
\[
\lim_{n \rightarrow \infty}
        \prob{\abs{\frac{S_n}{n} - \expect{\frac{S_n}{n}}}
 \geq \epsilon} = 0.
\]

\hint Adapt the proof in Handout 72, \emph{Expectation \& Variance:
Further Notes}, of the Weak Law of Large Numbers (attached).  Note that in
the proof from Handout 72, the $G_i$'s were Bernoulli variables with the
same probability $p$ of success, which is not the case here.

\solution{Same as proof in the notes, simply replacing $\variance{G}$ by
$b$.}


\end{problems}

\section*{Appendix}

\subsection*{Markov \& Chebyshev Bounds}

Markov bound:
\[
\prob{R \geq x} \leq \frac{\expect{R}}{x}.
\]


Chebyshev bound: for $c \geq 0$,
\[
\prob{\abs{R - \expect{R}} \geq c\sigma_R} \leq \frac{1}{c^2}.
\]

The ``one-way'' version of Chebyshev bound: for $c \geq 0$,
\[
\prob{R - \expect{R} \geq c\sigma_R} \leq \frac{1}{1+c^2}.
\]


\subsection*{Weak Law of Large Numbers for Bernoulli Variables}

Let $G_1, G_2, \dots, G_n$ independent Bernoulli variables, each with the
same probability $p$ of being equal to one.  In this case, $G_i=G_i^2$, so
\[
\expect{G_i^2} = \expect{G_i} = \prob{G_i=1} = p,
\]
and
\[
\variance{G_i} = \expect{G_i^2} - \expectsq{G_i} = p - p^2 = p(1-p).
\]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i,
\]

We can use the random variable $S_n/n$ to estimate $p$.  This estimator
$S_n/n$ is a random variable with two critical properties:
\begin{eqnarray*}
\expect{\frac{S_n}{n}} & = & \expect{G_i} = p,\\
\variance{\frac{S_n}{n}} & = & \frac{\variance{G_i}}{n} = \frac{p(1-p)}{n}.
\end{eqnarray*}

To prove this, note that by linearity of expectation
\[
\expect{\frac{S_n}{n}} = \frac{\expect{\sum_{i=1}^n G_i}}{n}
   = \frac{\sum_{i=1}^n \expect{G_i}}{n}
   = \frac{np}{n} = p.
\]

Also, since the $G_i$'s are independent, their variances will add, so
\begin{eqnarray*}
\variance{\frac{S_n}{n}} & = & (\frac{1}{n})^2 \variance{S_n}\\
& = & (\frac{1}{n})^2 \sum_{i=1}^n \variance{G_i}\\
& = & (\frac{1}{n})^2 n\variance{G_i}\\
& = & \frac{\variance{G}}{n}.
\end{eqnarray*}

Now Chebyshev's Bound tells us that
\begin{theorem}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent Bernoulli variables with the same probability $p$ of being
equal to one.
Then
\[
\prob{\abs{\frac{S_n}{n} - p} \geq x} \leq \frac{p(1-p)}{nx^2}.
\]
\end{theorem}

Now if we fix $p$ and $x$ and let $n$ approach infinity, we conclude that
the Weak Law of Large Numbers holds:

\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{S_n}{n} - p} \geq x} = 0.
\]


\end{document}
        
