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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

%\renewcommand{\coursecopyrightyear}{2002}

\begin{document}
\lecturenotes{13-14}{Deviation from the Mean}

\newcommand{\IQ}{I.Q.\@\xspace}
\newcommand{\ok}{\marginpar{OK?}}

%%%SECTION{BIRTHDAYS AGAIN} NEEDS FALL 02 DATA

\section{What the Mean Means}
 
We have focused on the expectation of a random variable because it
indicates the ``average value'' the random variable will take.  But what
precisely does this mean?

We know a random variable may never actually equal its expectation.  We
also know, for example, that if we flip a fair coin 100 times, the chance
that we actually flip \emph{exactly} 50 heads is only about 8\%.  In fact,
it gets less and less likely as we continue flipping that the number of
heads will exactly equal the expected number, \eg the chance of exactly
500 heads in 1000 flips is less than 3\%, in 1,000,000 flips less than
0.1\%, \dots.

But what is true is that the fraction of heads flipped is likely to be
\emph{close} to half of the flips, and the more flips, the closer the
fraction is likely to be to 1/2.  For example, the chance that the
fraction of heads is within 5\% of 1/2 is
\begin{itemize}
\item more than 24\% in 10 flips,
\item more than 38\% in 100 flips,
\item more than 56\% in 200 flips, and
\item more than 89\% in 1000 flips.
\end{itemize}

%%99.9999999\% in 1,000,000 flips????

These numbers illustrate the single most important phenomenon of
probability: the average value from repeated experiments is likely to be
close to the expected value of one experiment.  And it gets more likely to
be closer as the number of experiments increases.  This result was first
formulated and proved by Jacob D. Bernoulli in his book \emph{Ars
Conjectandi} (The Art of Guessing) published posthumously in 1713.  In his
Introduction, Bernoulli comments that\footnote{These quotes are taken from
Grinstead \& Snell,
\href{http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/book.html}
{\emph{Introduction to Probability}}, American Mathematical Society,
p. 310.}
\begin{quote}
even the stupidest man---by some instinct of nature \emph{per se} and by
no previous instruction (this is truly amazing)---knows for sure that the
more observations \dots that are taken, the less the danger will be of
straying from the mark.
\end{quote}

But he goes on to argue that this instinct should not be taken for
granted:
\begin{quote}
Something further must be contemplated here which perhaps no one has
thought about until now.  It certainly remains to be inquired whether
after the number of observations has been increased, the probability\dots
of obtaining the true ratio\dots finally exceeds any given degree of
certainty; or whether the problem has, so to speak, its own
asymptote---that is, whether some degree of certainty is given which one
can never exceed.
\end{quote}

Here's how to give a technical formulation of the question Bernoulli wants
us to contemplate.  Repeatedly performing some random experiment
corresponds to defining $n$ random variables equal to the results of $n$
trials of the experiment.  That is, we let $G_1,\dots,G_n$ be independent
random variables with the same distribution and the same expectation,
$\mu$.  Now let $A_n$ be the average of the results, that is,
\[
A_n \eqdef \frac{\sum_{i=1}^n G_i}{n}.
\]
How sure we can be that the average value, $A_n$, will be close to $\mu$?
By letting $n$ grow large enough, can we be as certain as we want that the
average will be close, or is there is some irreducible degree of
uncertainty that remains no matter how many trials we perform?  More
precisely, given any positive tolerance, $\epsilon$, how sure can we be
that the average, $A_n$, will be within the tolerance of $\mu$ as $n$
grows?  In other words, we are asking about the limit
\[
\lim_{n \rightarrow \infty} \pr{\abs{A_n-\mu} < \epsilon}.
\]
Bernuolli asks if we can be sure this limit approaches certainty, that is,
equals one, or whether it approaches some number slightly less than one
that cannot be increased to one no matter how many times we repeat the
experiment.  His answer is that the limit is indeed one.  This result is
now known as the Weak Law of Large Numbers.  Bernoulli says of it:
\begin{quote}
Therefore, this is the problem which I now set forth and make known after
I have pondered over it for twenty years.  Both its novelty and its very
great usefulness, coupled with its just as great difficulty, can exceed in
weight and value all the remaining chapters of this thesis.
\end{quote}

With the benefit of three centuries of mathematical development since
Bernoulli, it will be a lot easier for us to resolve Bernoulli's questions
than it originally was for him.

\section{The Weak Law of Large Numbers}

\hyperdef{ln13}{weaklaw}{The Weak Law of Large Numbers} crystallizes, and
confirms, the intuition of Bernoulli's ``stupidest man'' that the average
of a large number of independent trials is more and more likely to be
within a smaller and smaller tolerance around the expectation as the
number of trials grows.

\begin{theorem}\label{weaklaw-lim1}[Weak Law of Large Numbers]
Let $G_1, \dots, G_n, \dots$ be independent variables with the same
distribution and the same expectation, $\mu$.  For any $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{\sum_{i=1}^n G_i}{n} - \mu}
\leq \epsilon} = 1.
\]
\end{theorem}

This Law gives a high-level description of a fundamental probabilistic
phenomenon, but as it stands it does not give enough information to be of
practical use.  The main problem is that it does not say anything about
the \emph{rate} at which the limit is approached.  That is, how big must
$n$ be to be within a given tolerance of the expected value with a
specific desired probability?  This information is essential in
applications.  For example:
\begin{itemize}

\item Suppose we want to estimate the number of voters who are registered
Republicans.  Exactly \emph{how many} randomly selected voters should we
poll in order to be sure that 99\% of the time, the average number of
Republicans in our poll is within 1/2\% of the actual percentage in the
whole country?

\item Suppose we want to estimate the number of fish in a lake.  Our
procedure will be to catch, tag and release 500 fish caught in randomly
selected locations in the lake at random times of day.  Then we wait a few
days, and catch another 100 random fish.  Suppose we discover that 10 of
the 100 were previously tagged.  Assuming that our 500 tagged fish
represent the same proportion of the whole fish population as the ones in
our sample of 100, we would estimate that the total fish population was
5000.  But how confident can we be of this?  Specifically, \emph{how
confident} should we be that our estimate of 5000 is within 20\% of the
actual fish population?

\item Suppose we want to estimate the average size of fish in the
lake by taking the average of the sizes of the 500 in our initial catch.
How confident can we be that this average is within 2\% of the average
size of all the fish in the lake?

\iffalse
\item ADD network redundancy/reliability example to illustrate need to
estimate distribution  tails.
\fi

\end{itemize}

In these Notes we will develop three basic results about this topic of
\emph{deviation from the mean}.  The first result is Markov's Theorem,
which gives a simple but coarse upper bound on the probability that the
value of the random variable is more than a certain multiple of its mean.
Markov's result holds if we know nothing more than the value of the mean
of a random variable.  As such, it is very general, but also is much
weaker than results which take more information about the random variable
into account.

In many situations, we not only know the mean, but also another numerical
quantity called the \emph{variance} of the random variable.  Our second
basic result is Chebyshev's Theorem, which combines Markov's Theorem and
information about the variance to give more refined bounds.

The third basic result we call the Pairwise Independent Sampling Theorem.
It provides the additional information about rate of convergence we need
to calculate numerical answers to questions such as those above.  The
Sampling Theorem follows from Chebyshev's Theorem and properties of the
variance of a sum of independent variables.

Finally, the Weak Law of Large Numbers will be an easy corollary of
the Pairwise Independent Sampling Theorem.

\subsection{Markov's Theorem}

We want to consider the problem of bounding the probability that the
value of a random variable is far away from the mean. Our first
theorem, Markov's theorem, gives a very rough estimate, based only on
the value of the mean.

The idea behind Markov's Theorem can be explained with a simple example of
\IQ measurment.  \IQ was devised so that the average \IQ measurement would
be 100.  Now from this fact alone we can conclude that at most 1/2 the
population can have an \IQ of 200 or more, because if more than half had
an \IQ of 200, then the average would have to be more than $(1/2)200 =
100$, contradicting the fact that the average is 100.  So the probability
that a randomly chosen person has an \IQ of 200 or more is at most 1/2.
Of course this is not a very strong conclusion; in fact no \IQ of over 200
has ever been recorded.  But by the same logic, we can also conclude that
at most 2/3 of the population can have an \IQ of 150 or more.  \IQ's of
over 150 have certainly been recorded, though again, a much smaller
fraction of the population actually has an \IQ that high.

But although these conclusions about \IQ are weak, they are actually the
\emph{strongest possible} general conclusions that can be reached about a
random variable using \emph{only} the fact that its mean is 100.  For
example, if we choose a random variable equal to 200 with probability 1/2,
and 0 with probability 1/2, then its mean is 100, and the probability of a
value of 200 or more is really 1/2.  So we can't hope to get a upper
better bound on the probability of 200 than 1/2.

\iffalse
Note that very different distributions can
still have the same mean.

\begin{example}
  Suppose that we roll a fair die.  This gives a random variable
  uniformly distributed on $1, 2, \ldots 6$.  The mean, or expected
  value, is 3.5.  Of course, this random variable never takes on
  exactly the expected value; in fact, the outcome deviates from the
  mean by at least 0.5 with probability 1.  Furthermore, there is a
  $\frac{2}{3}$ probability that the outcome deviates from the mean by
  at least 1.5 (roll 1, 2, 5, or 6), a $\frac{1}{3}$ probability that
  the outcome deviates by at least 2.5 (roll 1 or 6), and zero
  probability that the outcome deviates by more than 2.5.
\end{example}

\begin{example}
  A random variable with the binomial distribution is much less likely
  to deviate far from the mean.  For example, suppose we flip 100
  fair, mutually independent coins and count the number of heads.  The
  expected number of heads is 50.  There is an 8\% chance that the
  outcome is exactly the mean, and the probability of flipping more
  than 75 heads or fewer than 25 is less than 1 in a billion.
\end{example}

The probability distribution functions for the two preceding examples
are graphed in Figure~\ref{fig:uniform} and Figure~\ref{fig:binom2}.
There is a big difference!  For the uniform distribution, the graph is
flat; that is, outcomes far from the mean are as likely as outcomes
close to the mean.  However, the binomial distribution has a peak
centered on the expected value and the tails fall off rapidly.  This
shape implies that outcomes close to the expected value are vastly
more likely than outcomes far from the expected value.  In other
words, a random variable with the binomial distribution rarely
deviates far from the mean.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/uniform}}
  \caption{This is a graph of the uniform distribution arising from
    rolling a fair die.  Outcomes within the range of the distribution
    are equally likely, regardless of distance from the mean.}
  \label{fig:uniform}
\end{figure}
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/binom2}}
  \caption{This is a rough graph of the binomial distribution given by
    the number of heads that come up when we flip 100 fair, mutually
    independent coins.  Outcomes close to the mean are much more
    likely than outcomes far from the mean.}
  \label{fig:binom2}
\end{figure}

On the other hand, we can define a random variable that always
deviates substantially from its expected value.  Suppose that we glue
100 coins together, so that with probability 1/2 all are heads and
with probability 1/2 all are tails.  The graph of the probability
distribution function for the number of heads is shown in
Figure~\ref{fig:nasty}.  While the expected value of this random
variable is 50, the actual value is always 0 or~100.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/nasty}}
  \caption{This is the nasty distribution corresponding to the number
    of heads that come up when we flip 100 coins that are all glued
    together. The outcome always differs from the mean by at
    least~50.}
  \label{fig:nasty}
\end{figure}

Even in this last example, however, the random variable is twice the
mean with probability only $1/2$.  In fact, we will see that this is a
worst-case distribution with respect to deviation from the mean.


\subsection{Theorem Statement and Some Applications}
\fi

\begin{theorem}[Markov's Theorem]\label{markovthm}
  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}

\iffalse

Before we prove Markov's Theorem, let's apply it to the three examples in
the preceding subsection.  First, let the random variable~$R$ be the
number that comes up when we roll a fair die.  By Markov's Theorem, the
probability of rolling a 6 is at most:
\[
\pr{R \geq 6} \leq \frac{\expect{R}}{6} = \frac{3.5}{6} = 0.583\ldots
\]
This conclusion is true, but weak.  The actual probability of rolling
a 6 is $1/6 = 0.166\ldots$.

This is typical of Markov's Theorem.  The theorem is easy to apply
because it requires so little information about a random variable,
only the expected value and nonnegativity.  But as a consequence,
Markov's Theorem often leads to weak conclusions like the one above.

Suppose that we flip 100 mutually independent, fair coins.  Markov's
Theorem says that the probability of throwing 75 or more heads is at
most:
\[
\pr{\text{heads} \geq 75} \leq \frac{\expect{\text{heads}}}{75} =
\frac{50}{75} = \frac{2}{3}.
\]
Markov's Theorem says that the probability of 75 or more heads is at
most $2/3$, but the actual probability is less than 1 in a
billion!

These two examples show that Markov's Theorem gives weak results for
well-behaved random variables; however, the theorem is actually tight
for some nasty examples.  Suppose we flip 100 fair coins and use
Markov's Theorem to compute the probability of getting all heads:
\[
\pr{\text{heads} \geq 100} \leq \frac{\expect{\text{heads}}}{100} =
\frac{50}{100} = \frac{1}{2}.
\]
If the coins are mutually independent, then the actual probability of
getting all heads is a miniscule 1 in $2^{100}$.  In this case, Markov's
Theorem looks very weak.  However, in applying Markov's Theorem, we made
no independence assumptions.  In fact, if all the coins are glued
together, then probability of throwing all heads is exactly $1/2$.
In this nasty case, Markov's Theorem is actually tight!



\subsection{Proof of Markov's Theorem}

Let $R$ be the weight of a person selected randomly and uniformly.
Suppose that an average person weighs 100 pounds; that is, $\expect{R} =
100$.  What is the probability that a random person weighs at least
200 pounds?

There is insufficient information for an exact answer.  However, we
can safely say that the probability that $R \geq 200$ is most
$1/2$.  If more than half of the people weigh 200 pounds or
more, then the average weight would exceed 100 pounds, even if
everyone else weighed zero!  Markov's Theorem gives the same result:
\begin{displaymath}
  \pr{R \geq 200} \leq \frac{\expect{R}}{200} = \frac{100}{200} = \frac{1}{2}.
\end{displaymath}

Reasoning similar to that above underlies the proof of Markov's
Theorem. Since expectation is a weighted average of all the outcomes
of the random variable, \ie\ a sum over all the variables the random
variable can assume, we can give a lower bound on the expectation by
removing some of the terms from the sum defining the expectation; this
new sum can then be modified into an expression involving the
probability of an event in the tail $[R \geq x]$.
\fi

\begin{proof}%[Proof of Markov's Theorem]
We will show that $\expect{R} \geq x \pr{R \geq x}$.  Dividing
both sides by $x$ gives the desired result.

So let $I_x$ be the indicator variable for the event $[R \geq x]$, and
consider the random variable $x I_x$.  Note that $R \geq x I_x$, because
if $R(w) \geq x$ then $x I_x(w) = x\cdot 1 = x$, and if $R(w) < x$ then $x
I_x(w) = x \cdot 0 = 0$.  Therefore,
\begin{align*}
\expect{R} & \geq \expect{x I_x} & (R \geq xI_x)\\
   & = x \expect{I_x} & \text{(linearity of expectation)}\\
   & = x \pr{R \geq x}.  &  (\expect{I_x} = \pr{I_x =1})
\end{align*}
\end{proof}

Markov's Theorem is often expressed in an alternative form, stated
below as a corollary.
\begin{corollary}
If R is a nonnegative random variable, then for all $c > 0$
\begin{equation*}
\pr{R \geq c \cdot \expect{R}}  \leq  \frac{1}{c}.
\end{equation*}
\end{corollary}
\begin{proof}
In Markov's Theorem, set $x = c \cdot \expect{R}$.  This gives:
\[
\pr{R \geq c \cdot \expect{R}} \leq \frac{\expect{R}}{c \cdot \expect{R}} =
\frac{1}{c}.
\]
\end{proof}


\subsubsection{Examples of Markov's Theorem}

Suppose that $N$ men go to a dinner party and check their hats.  At
the end of the night, each man is given his own hat back with
probability $1/N$.  What is the probability that $x$ or more
men get the right hat?

We can compute an upper bound with Markov's Theorem.  Let the random
variable, $R$, be the number of men that get the right hat.  In
previous  notes, we used linearity of expectation to show that
$\expect{R} = 1$.  By Markov's Theorem, the probability that $x$ or more
men get the right hat is:
\[
\pr{R \geq x} \leq \frac{\expect{R}}{x} = \frac{1}{x}.
\]
For example, there is no better than a 20\% chance that 5 men get the
right hat, regardless of the number of people at the dinner party.

The Chinese Appetizer problem is very similar.  In this case, $N$
people are eating Chinese appetizers arranged on a circular, rotating
tray.  Someone then spins the tray so that each person receives a
random appetizer.  What is the probability that everyone gets the same
appetizer as before?

There are $N$ equally likely orientations for the tray after it stops
spinning.  Everyone gets the right appetizer in just one of these $N$
orientations.  Therefore, the correct answer is $1/N$.

But what probability do we get from Markov's Theorem?  Let the random
variable, $R$, be the number of people that get the right appetizer.  We
showed in previous notes that $\expect{R} = 1$.  Applying Markov's
Theorem, we find:
\begin{displaymath}
  \pr{R \geq N} \leq \frac{\expect{R}}{N} = \frac{1}{N}\,.
\end{displaymath}
In this case, Markov's Theorem is tight!

On the other hand, Markov's Theorem gives the same $1/N$ bound for the
probability everyone gets their hat in the hat check problem.  But in
reality, the probability of this event is $1/N!$.  So Markov's Theorem in
this case gives probability bounds that are way off.

\subsubsection{Why \emph{R} Must be Nonnegative}

The proof of Markov's Theorem requires that the random variable, $R$, be
nonnegative.  The following example shows that the theorem is false
if this restriction is removed.  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$.  Remember that Markov's Theorem applies
only to nonnegative random variables!

On the other hand, we can still apply Markov's Theorem to bound the
probability that an arbitrary variable like $R$ is 5 more.  Namely, given
any random variable, $R$ with expectation 0 and values
$\geq -10$, we can conclude that $\pr{R \geq 5} \le 2/3$.
\begin{proof}
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$, as claimed.
\end{proof}

\subsubsection{Deviation Below the Mean}

Markov's Theorem says that a random variable is unlikely to greatly exceed
the mean.  Correspondingly, there is a theorem that says a random variable
is unlikely to be much smaller than its mean.

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

\begin{proof}
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$.
\end{proof}

For example, suppose that the class average on the 6.042 midterm was
75/100.  What fraction of the class scored below 50?

There is not enough information here to answer the question exactly,
but Theorem~\ref{th:below} gives an upper bound.  Let $R$ be the score
of a random student.  Since 100 is the highest possible score, we
can set $L = 100$ to meet the condition in the theorem that $R \leq
L$.  Applying Theorem~\ref{th:below}, we find:
\begin{displaymath}
  \pr{R \leq 50} \leq \frac{100 - 75}{100 - 50} = \frac{1}{2}\,.
\end{displaymath}

That is, at most half of the class scored 50 or worse.  This makes
sense; if more than half of the class scored 50 or worse, then the
class average could not be 75, even if everyone else scored 100.
As with Markov's Theorem, Theorem~\ref{th:below} often gives weak
results.  In fact, based on the data given, the entire class could
have scored above 50.


\subsubsection{Using Markov To Analyze Non-Random Events [Optional]}
\begin{optional}

In the previous examples, we used a theorem about a random variable to
conclude facts about non-random data.  For example, we concluded that
if the average score on a test is 75, then at most $1/2$ the
class scored 50 or worse.  There is no randomness in this problem,
so how can we apply Theorem~\ref{th:below} to reach this conclusion?

The explanation is not difficult.  For any set of scores $S = \set{s_1,
s_2, \dots, s_n}$, we introduce a random variable, $R$, such that
\[
\pr{R = s_i} = \frac{\text{(\# of students with score $s_i$)}}{n}
\]
We then use Theorem~\ref{th:below} to conclude that $\pr{R \leq 50}
\leq 1/2$.  To see why this means (with certainty) that at most
$1/2$ of the students scored 50 or less, we observe that
\begin{eqnarray*}
\pr{R \leq 50}  & = & \sum_{s_i \leq 50} \pr{R = s_i} \\
  & = & \sum_{s_i \leq 50} \frac{\text{(\# of students with score $s_i$)}}{n} \\
  & = & \frac{1}{n} \text{(\# of students with score 50 or less)}.
\end{eqnarray*}
So, if $\pr{R \leq 50} \leq 1/2$, then the number of students
with score 50 or less is at most $n/2$.

\end{optional}

\section{Chebyshev's Theorem}

We have versions of Markov's Theorem for deviations above and below the
mean, but often we want bounds that apply in both directions, that is,
bounds on the probability that $\abs{R - \expect{R}}$ is large.

It is a bit messy to use Markov's inequality directly to bound the
probabilty that $\abs{R - \expect{R}} \geq x$, since we then would have to
compute $\expect{\abs{R - \expect{R}}}$.  However, since $\abs{R}$ and
hence $\abs{R}^k$ are nonnegative variables for any $R$, Markov's
inequality also applies to the event $[\abs{R}^k \geq x^k]$.  But this
event is equivalent to the event $[\abs{R} \geq x]$, so we have:

\begin{corollary}\label{cor:Markov2}
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}

The special case of this corollary when $k=2$ can be applied to bound the
random variable, $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~(\ref{chebE2}) follows from
Corollary~\ref{cor:Markov2} applied to the random variable, $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 called the \emph{variance of~$R$}.

\begin{definition}\label{defvar}
The \emph{variance}, $\variance{R}$, of a random variable, $R$, is:
\[
\variance{R} \eqdef \expect{(R - \expect{R})^2}.
\]
\end{definition}

So we can restate~(\ref{chebE2}) as
\begin{theorem}[Chebyshev]\label{chebthm}
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}

The expression $\expect{(R - \expect{R})^2}$ for variance is a bit
cryptic; the best approach is to work through it from the inside out.  The
innermost expression, $R - \expect{R}$, is precisely the deviation of $R$
from the mean.  Squaring this, we obtain, $(R - \expect{R})^2$.  This is a
random variable that is near 0 when $R$ is close to the mean and is a
large positive number when $R$ deviates far above or below the mean.  The
variance is just the average of this random variable, $\expect{(R -
\expect{R})^2}$.  Therefore, intuitively, if $R$ is always close to the
mean, then the variance will be small.  If $R$ is often far from the mean,
then the variance will be large.  For this reason, variance is useful in
studying the probability that a random variable deviates far from the
mean.

\subsection{Example: Gambling Games}

The relevance of variance is apparent when we compare 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$.

Which game is better financially?  We have the same probability, 2/3,
of winning each game, but that does not tell the whole story.  What about
the expected return for each game?  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*}

The expected payoff is the same for both games, but they are obviously
very different!  This difference is hidden by expected value, but
captured by variance.  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!

\section{Properties of Variance}

\subsection{Why Variance?}

The definition of variance of $R$ as $\expect{(R - \expect{R})^2}$ may
seem rather arbitrary.  The variance is the average \emph{of the square}
of the deviation from the mean.  For this reason, variance is sometimes
called the ``mean squared deviation.''  But why bother squaring?  Why not
simply compute the average deviation from the mean?  That is, why not
define variance to be $\expect{R - \expect{R}}$?

The problem with this definition is that the positive and negative
deviations from the mean exactly cancel.  By linearity of expectation,
we have:
\[
  \expect{R - \expect{R}} = \expect{R} - \expect{\expect{R}}.
\]
Since $\expect{R}$ is a constant, its expected value is itself. Therefore
\[
\expect{R - \expect{R}} = \expect{R} - \expect{R} = 0.
\]
By this definition, every random variable has zero variance.  That is not
useful!  Because of the square in the conventional definition, both
positive and negative deviations from the mean increase the variance;
positive and negative deviations do not cancel.

Of course, we could also prevent positive and negative deviations from
cancelling by taking an absolute value.  That is, we could define variance
to be $\expect{\abs{R - \expect{R}}}$.  There is no great reason not to
use this definition.  However, the conventional version of variance has
some pleasant mathematical properties that the absolute value variant does
not.  For example, for independent random variables, the variance of a sum
is the sum of the variances; that is, $\variance{R_1 + R_2} =
\variance{R_1} + \variance{R_2}$.  We will prove this fact below.

\subsection{Standard Deviation}

Due to squaring, the variance of a random variable may be very far from a
typical deviation from the mean.  For example, in Game B above, the
deviation from the mean is 1001  in one outcome and -2002  in
the other. But the variance is a whopping 2,004,002.  From a
dimensional analysis viewpoint, the ``units'' of variance are wrong:
if the random variable is in dollars, then the expectation is also in
dollars, but the variance is in square dollars.  For this reason,
people often describe random variables using standard deviation
instead of variance. 

\begin{definition}
The \emph{standard deviation} of a random variable R is denoted
$\sigma_R$ and defined as the square root of the variance:
\[
\sigma_R \eqdef \sqrt{\variance{R}} = \sqrt{\expect{(R - \expect{R})^2}}.
\]      
\end{definition}

So the standard deviation is the square root of the mean of the square of
the deviation, or the ``root mean square'' for short.  It has the same
units---dollars in our example---as the original random variable and as
the mean.  Intuitively, it measures the ``expected (average) deviation
from the mean,'' since we can think of the square root on the outside as
cancelling the square on the inside.

\begin{example}
The standard deviation of the payoff in Game B is:
\[
    \sigma_B  = \sqrt{\variance{B}} = \sqrt{2,004,002} \approx 1416.
\]

The random variable~$B$ actually deviates from the mean by either
positive 1001  or negative 2002; therefore, the standard
deviation of 1416 describes the situations reasonably well.
\end{example}

As can be seen in Figure~\ref{fig:stdev}, the standard
deviation measures the ``width'' of the main part of the distribution
graph.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/stdev}}
  \caption{The standard deviation of a distribution says how wide the
    ``main'' part of it is.}
  \label{fig:stdev}
\end{figure}

\subsection{An Alternative Definition of Variance}

There is an equivalent way to define the variance of a random variable
that is less intuitive, but is often easier to use in calculations
and proofs:
\begin{theorem}\label{th:alt}
\[
\variance{R} = \expect{R^2} - \expectsq{R},
\]
for any random variable, $R$.
\end{theorem}
Here we use the notation $\expectsq{R}$ as shorthand for $(\expect{R})^2$.

Remember that $\expect{R^2}$ is generally not equal to $\expectsq{R}$.  We
know the expected value of a product is the product of the expected values
for independent variables, but not in general.  And $R$ is not independent
of itself unless it is constant.
\begin{proof}
Let $\mu = \expect{R}$.  Then
\begin{align*}
\variance{R} & =   \expect{(R - \expect{R})^2}
               & \text{(Def.~\ref{defvar} of variance)}\\
        & = \expect{(R - \mu)^2} & \text{(Def. of $\mu$)}\\
        & = \expect{R^2 - 2  \mu R + \mu^2} \\
        & = \expect{R^2} - 2 \mu \expect{R} + \mu^2 
                & \text{(linearity of expectation)}\\
        & = \expect{R^2} - 2 \mu^2 + \mu^2
              &  \text{(definition of $\mu$)}\\
        & = \expect{R^2} - \mu^2\\
        & = \expect{R^2} - \expectsq{R}.
                  &  \text{(definition of $\mu$)}
\end{align*}
\end{proof}

\begin{optional}

Theorem~\ref{th:alt} gives a convenient way to compute the variance of a
random variable: find the expected value of the square and subtract the
square of the expected value.  For example, we can compute the variance of
the outcome of a fair die as follows:
\begin{gather*}
  \expect{R^2} = \frac{1}{6} (1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2) = \frac{91}{6}, \\
  \expectsq{R} = \left(3 \frac{1}{2}\right)^2 = \frac{49}{4}, \\
  \variance{R}  = \expect{R^2} - \expectsq{R}
  = \frac{91}{6} - \frac{49}{4} = \frac{35}{12}.
\end{gather*}

This result is particularly useful when we want to estimate the variance
of a random variable from a sequence $x_1,x_2,\dots,x_n$, of sample values
of the variable.

\begin{definition}
For any sequence of real numbers $x_1,x_2,\dots,x_n$, define the
\emph{sample mean}, $\mu_n$, and the \emph{sample variance}, $v_n$, of the
sequence to be:
\begin{eqnarray*}
\mu_n  & \eqdef & \frac{\sum_{i=1}^n x_i}{n},\\
v_n  & \eqdef & \frac{\sum_{i=1}^n (x_i - \mu_n)^2}{n}.
\end{eqnarray*}
\end{definition}
Notice that if we define a random variable, $R$, which is equally likely
to take each of the values in the sequence, that is $\pr{R = x_i} = 1/n$
for $i = 1,\dots,n$, then $\mu_n = \expect{R}$ and $v_n = \variance{R}$.
So Theorem~\ref{th:alt} applies to $R$ and lets us conclude that
\begin{equation}\label{vn:alt}
v_n = \frac{\sum_{i=1}^n x_i^2}{n} - \left(\frac{\sum_{i=1}^n x_i}{n}\right)^2.
\end{equation}
This leads to a simple procedure for computing the sample mean and
variance while reading the sequence $x_1,\dots,x_n$ from left to right.
Namely, maintain a sum of all numbers seen and also maintain a sum of the
squares of all numbers seen.  That is, we store two values, starting with
the values $x_1$ and $x_1^2$.  Then, as we get to the next number, $x_i$,
we add it to the first sum and add its square, $x_{i}^2$, to the second
sum.  After a single pass through the sequence $x_1,\dots,x_n$, we wind up
with the values of the two sums $\sum_{i=1}^n x_i$ and $\sum_{i=1}^n
x_i^2$.  Then we just plug these two values into~(\ref{vn:alt}) to find
the sample variance.

\end{optional}

\subsubsection{Expectation Squared [Optional]}

\begin{optional}

The alternate definition of variance given in Theorem~\ref{th:alt} has
a cute implication:
\begin{corollary}
If $R$ is a random variable, then $\expect{R^2} \geq \expectsq{R}$.
\end{corollary}
\begin{proof}
We first defined $\variance{R}$ as an average of a squared expression, so
$\variance{R}$ is nonnegative.  Then we proved that $\variance{R} =
\expect{R^2} - \expectsq{R}$.  This implies that $\expect{R^2} -
\expectsq{R}$ is nonnegative.  Therefore, $\expect{R^2} \geq
\expectsq{R}$.
\end{proof}

In words, the expectation of a square is at least the square of the
expectation. The two are equal exactly when the variance is zero:
\begin{displaymath}
\expect{R^2} = \expectsq{R} \text{  iff  } \expect{R^2} - \expectsq{R} = 0
\text{  iff  } \variance{R} = 0.
\end{displaymath}

\end{optional}


\subsubsection{Zero Variance}

When does a random variable, $R$, have zero variance?\dots when the random
variable \emph{never} deviates from the mean!
\begin{lemma}\label{zvar}
The variance of a random variable, $R$, is zero if and only if $R =
\expect{R}$ for all outcomes with positive probability.
\end{lemma}

The final phrase is a technicality; for an outcome with zero
probability, $R$ can take on any value without affecting the variance.

\begin{proof}
By the definition of variance, $\variance{R} = 0$ is equivalent to the
condition $\expect{(R - \expect{R})^2} = 0$.
  
The inner expression, $(R - \expect{R})^2$, is always nonnegative because
of the square.  As a result, $\expect{(R - \expect{R})^2} = 0$ if an only
if $(R - \expect{R})^2 = 0$ for all outcomes with positive probability.
Now, the conditions $(R - \expect{R})^2 = 0$ and $R = \expect{R}$ are also
equivalent.  Therefore, $\variance{R} = 0$ iff $R = \expect{R}$ for all
outcomes with positive probability.
\end{proof}

\subsubsection{Dealing with Constants}

The following theorem describes how the variance of a random variable
changes when it is scaled or shifted by a constant.
\begin{theorem}\label{th:const}
Let $R$ be a random variable, and let $a$ and $b$ be constants. Then
\begin{equation}\label{aRb}
\variance{a R + b} = a^2 \variance{R}.
\end{equation}
\end{theorem}

This theorem makes two points.  First, adding a constant $b$ to a random
variable does not affect the variance.  Second, multiplying a random
variable by a constant changes the variance by a \emph{square factor}.

\begin{proof}
We will transform the left side of~(\ref{aRb}) into the right side.  The
first step is to expand $\variance{a R + b}$ using the alternate
definition of variance.
\[
\variance{a R + b} =
\expect{(a R + b)^2} - \expectsq{a R + b}.
\]
We will work on the first term and then the second term.  For the first
term, note that by linearity of expectation,
\begin{equation}\label{R2}
\expect{(aR+b)^2} = \expect{a^2 R^2 + 2 a b R + b^2} =
a^2 \expect{R^2} + 2 a b \expect{R} + b^2.
\end{equation}
Similarly for the second term:
\begin{equation}\label{2R}
\expectsq{aR+b} = (a \expect{R} + b)^2 = a^2 \expectsq{R} + 2 a b
\expect{R} + b^2.
\end{equation}

Finally, we substract the expanded second term from the first.
\begin{align*}
\variance{a R + b} & = \expect{(a R + b)^2} - \expectsq{a R + b}
      & \text{(Theorem~\ref{th:alt})}\\
  & = a^2 \expect{R^2} + 2 a b \expect{R} + b^2 -\\
  &\quad (a^2 \expectsq{R} + 2 a b \expect{R} + b^2)
     & \text{(by~(\ref{R2}) and~(\ref{2R}))}\\
  & = a^2 \expect{R^2} - a^2 \expectsq{R}\\
  & = a^2 (\expect{R^2} - \expectsq{R})\\
  & = a^2 \variance{R} 
     & \text{(Theorem~\ref{th:alt})}
\end{align*}
\end{proof}
A similar rule holds for the standard deviation when a random variable
is adjusted by a constant.  Recall that standard deviation is the
square root of variance.  Therefore, adding a constant $b$ to a random
variable does not change the standard deviation.  Multiplying a random
variable by a constant $a$ multiplies the standard deviation by $a$.  So
we have
\begin{corollary}
The standard deviation of $a R + b$ equals $a$ times the standard deviation
of $R$.
\end{corollary}

\subsection{Variance of a Sum}

Earlier, we claimed that for independent random variables, the variance of
a sum is the sum of the variances.
\iffalse

\begin{theorem}\label{indvar}
If $R_1$ and $R_2$ are independent random variables, then
\[
\variance{R_1 + R_2} = \variance{R_1} + \variance{R_2}.
\]
\end{theorem}
\begin{proof}
We will transform the left side into the right side.  We begin by
applying the alternate definition of variance.
\[
\variance{R_1 + R_2} = \expect{(R_1 + R_2)^2} - \expectsq{R_1 + R_2}.
\]

We will work on the first term and then the second term separately.
For the first term, note\begin{eqnarray*}
\expect{(R_1+R_2)^2}
& = &   \expect{R_1^2 + 2 R_1 R_2 + R_2^2} \\
& = &   \expect{R_1^2} + \expect{2 R_1 R_2} + \expect{R_2^2} \\
& = &   \expect{R_1^2} + 2 \expect{R_1} \expect{R_2} + \expect{R_2^2}.
\end{eqnarray*}
First, we multiply out the squared expression.  The second step uses
linearity of expectation.  In the last step, we break the
expectation of the product $R_1 R_2$ into a product of expectations;
this is where we use the fact that $R_1$ and $R_2$ are independent.
Now we work on the second term.
\begin{eqnarray*}
\expectsq{R_1+R_2} & = & (\expect{R_1} + \expect{R_2})^2 \\
& = & \expectsq{R_1} + 2 \expect{R_1} \expect{R_2} + \expectsq{R_2}.
\end{eqnarray*}
The first step uses linearity of expectation, and in the second step
we multiply out the squared expression.  Now we subtract the
(expanded) second term from the first. Cancelling and rearranging
terms, we find that
\begin{eqnarray*}
\variance{R_1 + R_2} & = &   (\expect{R_1^2} - \expectsq{R_1}) +
(\expect{R_2^2}) - \expectsq{R_2}) \\
& = &   \variance{R_1} + \variance{R_2}.
\end{eqnarray*}
\end{proof}
\fi
An independence condition is necessary.  If we ignored independence, then
we would conclude that $\variance{R + R} = \variance{R} + \variance{R}$.
However, by Theorem~\ref{th:const}, the left side is equal to $4
\variance{R}$, whereas the right side is $2 \variance{R}$.  This implies
that $\variance{R}=0$, which, by Lemma~\ref{zvar}, holds only if $R$ is
constant.

However, \emph{mutual} independence is not necessary: \emph{pairwise}
independence will do.  This is useful to know because there are some
important situations involving variables that are pairwise independent but
not mutually independent.  Matching birthdays is an example of this kind,
as we shall see below.

\begin{theorem}\label{th:varsum}[Pairwise Independent Additivity of Variance]
If $R_1, R_2, \ldots, R_n$ are \emph{pairwise} independent random
variables, then
\[
\variance{R_1 + R_2 + \ldots + R_n} = \variance{R_1} + \variance{R_2} +
  \cdots + \variance{R_n}.
\]
\end{theorem}
\begin{proof}
By linearity of expectation, we have
\begin{align}
\expect{\biggl(\sum_{i=1}^n R_i\biggr)^2} &
    = \expect{\sum_{i=1}^n \sum_{j=1}^n R_i R_j} \notag\\
   &  = \sum_{i=1}^n \sum_{j=1}^n \expect{R_i R_j} & \text{(linearity)}\notag\\
   & = \sum_{1\le i \neq j \le n} \expect{R_i}\expect{R_j} + \sum_{i=1}^n
     \expect{R_i^2}.
       & \text{(pairwise independence)} \label{ER2}
\end{align}
In~(\ref{ER2}), we use the fact from previous Notes that the expectation
of the product of two independent variables is the product of their
expectations.

Also,
\begin{align}
\expectsq{\sum_{i=1}^n R_i} & = \biggl(\expect{\sum_{i=1}^n R_i}\biggr)^2 \notag\\
  &  = \biggl(\sum_{i=1}^n \expect{R_i}\biggr)^2 &\text{(linearity)} \notag\\
  &  = \sum_{i=1}^n \sum_{j=1}^n \expect{R_i} \expect{R_j}\notag\\
  & = \sum_{1\le i \neq j \le n} \expect{R_i}\expect{R_j} + \sum_{i=1}^n
     \expectsq{R_i}.\label{E2R}
\end{align}
So,
\begin{align*}
\variance{\biggl(\sum_{i=1}^n R_i\biggr)}
   & =  \expect{\biggl(\sum_{i=1}^n R_i\biggr)^2} -
\expectsq{\sum_{i=1}^n R_i}  & \text{(Theorem~\ref{th:alt})}\\
   &  = \sum_{1\le i \neq j \le n} \expect{R_i} \expect{R_j}
        + \sum_{i=1}^n \expect{R_i^2} - \\
   & \quad \paren{\sum_{1\le i \neq j \le n} \expect{R_i}\expect{R_j}
        + \sum_{i=1}^n \expectsq{R_i}}
      & \text{(by~(\ref{ER2}) and~(\ref{E2R}))}\\
   & = \sum_{i=1}^n \expect{R_i^2} - \sum_{i=1}^n \expectsq{R_i}\\
   & = \sum_{i=1}^n (\expect{R_i^2} - \expectsq{R_i})
             & \text{(reordering the sums)}\\
   & = \sum_{i=1}^n \variance{R_i}. & \text{(Theorem~\ref{th:alt})}
\end{align*}
\end{proof}

\subsection{Variance of a Binomial Distribution}

We now have enough tools to find the variance of a binomial
distribution.  Recall that if a random variable, $R$, has a binomial
distribution, then
\[
\pr{R = k} = \binom{n}{k} p^k (1-p)^{n-k}
\]
where $n$ and $p$ are parameters such that $n \geq 1$ and $0 < p < 1$.

We can think of $R$ as the sum of $n$ independent Bernoulli variables.
For example, we can regard $R$ as the number of heads that come up
when we toss $n$ independent coins, where each coin comes up heads
with probability $p$.  Formally, we can write $R = R_1 + R_2 + \cdots
+ R_n$ where
\begin{displaymath}
  R_i = \begin{cases}
    1 & \text{with probability $p$,} \\
    0 & \text{with probability $1-p$.}
  \end{cases}
\end{displaymath}
Now we can compute the variance of the binomially distributed
variable~$R$.
\begin{align*}
\variance{R}
   & =  \variance{R_1} + \variance{R_2} + \ldots + \variance{R_n}
              & \text{(Theorem~\ref{th:varsum})}\\
   & =  n \variance{R_1} & (\variance{R_i} = \variance{R_j})\\
   & =  n (\expect{R_1^2} - \expectsq{R_1}) 
             & \text{(Theorem~\ref{th:alt})}\\
   & =  n (\expect{R_1} - \expectsq{R_1}) & (R_1^2 = R_1)\\
   & =  n (p - p^2). & (\expect{R_1} = \pr{R_1 = 1} = p)
\end{align*}

This shows that the binomial distribution has variance $p (1 - p) n$ and
standard deviation $\sqrt{p (1- p) n}$.  In the special case of an
unbiased binomial distribution ($p = 1/2$), the variance is $n/4$ and the
standard deviation is $\sqrt{n}/2$.


\section{Applications of Chebyshev's Theorem}

There is a nice reformulation of Chebyshev's Theorem in terms of
standard deviation.
\begin{corollary}
\label{cor:cheby}
Let $R$ be a random variable, and let $c$ be a positive real number.
\[
\pr{\abs{R - \expect{R}} \geq c \sigma_R} \leq \frac{1}{c^2}.
\]
\end{corollary}
Here we see explicitly how the ``likely'' values of $R$ are clustered in
an $O(\sigma_R)$-sized region around $\expect{R}$, confirming that the
standard deviation measures how spread out the distribution of $R$ is
around its mean.

\begin{proof}
  Substituting $x = c \sigma_R$ in Chebyshev's Theorem gives:
  \begin{displaymath}
    \pr{\card{R - \expect{R}} \geq c \sigma_R}
    \leq
    \frac{\variance{R}}{(c \sigma_R)^2}
    =  \frac{\sigma_R^2}{(c \sigma_R)^2}
    = \frac{1}{c^2}.
  \end{displaymath}
\iffalse
  The last equality holds because variance is the square of standard
  deviation: $\variance{R} = \sigma_R^2$.
\fi

\end{proof}

\subsection{I.Q. Example}\label{IQsec}

Suppose that, in addition to the average \IQ being 100, we also know the
standard deviation of \IQ's is 10.  How rare is an \IQ of 200 or more?

Let the random variable, $R$, be the \IQ of a random person.  So we are
supposing that $\expect{R} = 100$, $\sigma_R = 10$, and $R$ is
nonnegative.  We want to compute $\pr{R \geq 200}$.

We have already seen that Markov's Theorem~\ref{markovthm} gives a coarse
bound, namely,
\[
  \pr{R \geq 200} \leq \frac{1}{2}.
\]
Now we apply Chebyshev's Theorem to the same problem:
\[
\pr{R \geq 200} = \pr{\abs{R - 100} \geq 100} \leq
\frac{\variance{R}}{100^2} = \frac{10^2}{100^2} = \frac{1}{100}.
\]
The purpose of the first step is to express the desired probability in the
form required by Chebyshev's Theorem; the equality holds because $R$ is
nonnegative.  Chebyshev's Theorem then yields the inequality.

So Chebyshev's Theorem implies that at most one person in a hundred has an
\IQ of 200 or more.  We have gotten a much tighter bound using the
additional information, namely the variance of $R$, than we could get
knowing only the expectation.

\subsection{A One-Sided Bound}

Chebyshev's Theorem gives a ``two-sided bound''.  That is, it bounds
the probability that a random variable deviates \emph{above or below}
the mean by some amount.  What if we want only a one-sided bound?  For
example, what is the probability that a random variable deviates
\emph{above} the mean by some amount?

This question is often answered incorrectly.  The erroneous argument runs
as follows.  By Chebyshev's Theorem, $R$ deviates above or below the mean
by some amount with probability $p$.  Therefore, $R$ deviates above the
mean by this amount with probability $p/2$, and $R$ deviates below the
mean by this amount with probability $p/2$.

While this argument is correct for a probability distribution function
that is symmetric about the mean, it is not correct for random variables
that are more likely to deviate above the mean than below.  For example,
in the \IQ question, some people deviate 100 points above the mean; that
is, there are people with \IQ greater than 200.  However, by assumption
everyone has a positive \IQ; no one deviates more than 100 points below
the mean.  For this reason it turns out we could actually improve the
bound of Section~\ref{IQsec} slightly---from 1 in 100 to 1 in 101.  In
general, there is a Chebyshev bound for the one-sided case that slightly
improves our two-sided bound, but we don't need to go into it.

\iffalse

The following theorem is analogous to Chebyshev's Theorem, but gives
(correct!) one-sided bounds.  We will not give a proof.
\begin{theorem}
  Let $R$ be a random variable, and let $x$ be a positive real number.
  \begin{gather*}
    \pr{R - \expect{R} \geq x} \leq \frac{\variance{R}}{\variance{R} + x^2}, \\
    \pr{R - \expect{R} \leq -x} \leq \frac{\variance{R}}{\variance{R} + x^2}.
  \end{gather*}
\end{theorem}
This theorem has a corollary analogous to Corollary~\ref{cor:cheby}.
\begin{corollary}
  \label{cor:cheby1}
  Let $R$ be a random variable, and let $c$ be a positive real number.
  \begin{gather*}
    \pr{R - \expect{R} \geq c \sigma_R} \leq \frac{1}{1 + c^2}, \\
    \pr{R - \expect{R} \leq - c \sigma_R} \leq \frac{1}{1 + c^2}.
  \end{gather*}
\end{corollary}
\begin{proof}
  Substitute $x = c \sigma_R$ in the preceding theorem.
\end{proof}
We can use this theorem to improve our solution to the \IQ problem
just slightly.  Recall that $R$ is the \IQ of a random person and
that $\expect{R} = 100$ and $\sigma_R = 10$.
\begin{eqnarray*}
\pr{R \geq 200}
        & = &           \pr{R - 100 \geq 100} \\
        & \leq &        \frac{\variance{R}}{\variance{R} + 100^2} \\
        & = &           \frac{10^2}{10^2 + 100^2} \\
        & = &           \frac{1}{101}.
\end{eqnarray*}
This shows that at most 1 person in 101 has an \IQ of 200 or more.

\subsection{Problem Scores}

The following example shows the difference between one-sided and two-sided
bounds.  On the 6.042 final, what fraction of the class can score two
standard deviations or more \emph{above or below} the class average?
Surprisingly, we can answer this question without any assumptions about
the range or distribution of scores!

In this case, we want a two-sided bound.  Let $R$ be the score of a
random student.  By Corollary~\ref{cor:cheby}, the probability is at
most:
\[
\pr{|R - \expect{R}| \geq 2 \sigma} \leq \frac{1}{2^2} = \frac{1}{4}.
\]
What fraction of the class can score two standard deviations or more
\emph{above} the class average?  Now we want a one-sided bound.  By
Corollary~\ref{cor:cheby1}, the probability is at most:
\[
\pr{R - \expect{R} \geq 2 \sigma} \leq \frac{1}{1 + 2^2} = \frac{1}{5}.
\]
This makes sense; the probability of deviating above the mean
(1/5) should be smaller than the probability of deviating
above or below the mean (1/4).
\fi

\section{Deviation of Repeated Trials}

Using Chebyshev's Theorem and the facts about variance and expectation, we
are finally in a position to be show how the average of many trials
approaches the mean.

\subsection{Estimation from Repeated Trials}

For example, suppose we want to estimate the fraction of the U.S. voting
population who would favor Al Gore over George Bush in the year 2004
presidential election.  Let $p$ be this unknown fraction.  Let's suppose
we have some random process---say throwing darts at voter registration
lists---which will select each voter with equal probability.  Now we can
define a Bernoulli variable, $G$, by the rule that $G=1$ if a random voter
most prefers Gore, and $G=0$ otherwise.  In this case, $G=G^2$, so
\[
\expect{G^2} = \expect{G} = \prob{G=1} = p,
\]
and
\[
\variance{G} = \expect{G^2} - \expectsq{G} = p - p^2 = p(1-p).
\]

To estimate $p$, we take a large number, $n$, of sample voters and count
the fraction who favor Gore.  We can describe this estimation as taking
independent Bernoulli variables $G_1, G_2, \dots, G_n$, each with the same
expectation as $G$, computing their sum
\begin{equation}\label{Sn}
S_n \eqdef \sum_{i=1}^n G_i,
\end{equation}
and then using the average, $S_n/n$, as our estimate of $p$.

More generally, we can consider \emph{any} set of random variables $G_1,
G_2, \dots, G_n$, with the same mean, $\mu$, and likewise use the average,
$S_n/n$, to estimate $\mu$.  One of the properties of $S_n/n$ that is
critical for this purpose is that $S_n/n$ has the same expectation as the
$G_i$'s, namely,
\begin{equation}\label{Smu}
\expect{\frac{S_n}{n}} = \mu,
\end{equation}
\begin{proof}
\begin{align*}
\expect{\frac{S_n}{n}} & = \expect{\frac{\sum_{i=1}^n G_i}{n}}
         & \text{(by def.~(\ref{Sn}) of $S_n$)}\\
 &  = \frac{\sum_{i=1}^n \expect{G_i}}{n} 
     & \text{(linearity of expectation)}\\
 & = \frac{\sum_{i=1}^n \mu}{n}\\
 & = \frac{n\mu}{n} = \mu.
\end{align*}
\end{proof}
Note that the random variables $G_i$ need not be Bernoulli or even
independent for~(\ref{Smu}) to hold, because linearity of expectation
always holds.

Now suppose the $G_i$'s also have the same deviation, $\sigma$.  The second
critical property of $S_n/n$ is that
\begin{equation}\label{Snu}
\variance{\frac{S_n}{n}} = \frac{\sigma^2}{n}.
\end{equation}
This follows as long as the variance of $S_n$ is the sum of the variances
of the $G_i$'s.  For example, by Theorem~\ref{th:varsum}, the variances
can be summed if the $G_i$'s are pairwise independent.  Then we calculate:
\begin{align*}
\variance{\frac{S_n}{n}} & =  \frac{1}{n^2} \variance{S_n}
          & \mbox{(Theorem~\ref{th:const})}\\
 & =  \frac{1}{n^2} \variance{\sum_{i=1}^n G_i} 
          & \text{(def~(\ref{Sn}) of $S_n$)}\\
 & =  \frac{1}{n^2} \sum_{i=1}^n \variance{G_i}
        & \text{(variances assumed to add)}\\
 & =  \frac{1}{n^2}\cdot n\sigma^2 =  \frac{\sigma^2}{n}.
\end{align*}

This is enough to apply Chebyshev's Bound and conclude:
\begin{theorem}\label{devmean}[Pairwise Independent Sampling]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i
\]
where $G_1, \dots, G_n$ are pairwise independent variables with the same
mean, $\mu$, and deviation, $\sigma$.  Then
\begin{equation}\label{Snx}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x}
    \leq \frac{1}{n} \left(\frac{\sigma}{x}\right)^2.
\end{equation}
\end{theorem}

\begin{proof}
\begin{align*}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x} & \leq \frac{\variance{S_n/n}}{x^2}.
       & \text{(Chebyshev's bound, Theorem~\ref{chebthm})}\\
    & = \frac{\sigma^2/n}{x^2} & \text{(by~(\ref{Snu}))}\\
    & = \frac{1}{n} \left(\frac{\sigma}{x}\right)^2.
\end{align*}
\end{proof}

Theorem~\ref{devmean} finally provides a precise statement about how the
average of independent samples of a random variable approaches the mean.
It generalizes to many cases when $S_n$ is the sum of independent
variables whose mean and deviation are not necessarily all the same,
though we shall not develop such generalizations here.


\subsection{Birthdays again}

\iffalse

In the polling example, we got a much better estimate of probable
deviation from the mean using the fact that the samples were
independent---and hence that the sampling distribution was binomial---than
from the Pairwise Independent Sampling Theorem~\ref{devmean}.  This should
not be surprising, since the Sampling Theorem is based on Chebyshev's
bound, and we've already seen that the Chebyshev bound can be much weaker
than bounds derived using more information about a density function than
simply its variance.

However, there are places where mutual independence of the samples doesn't
hold, but pairwise independence does, and that's where the Pairwise
Independent Sampling Theorem becomes our main handle on predicting sample
deviations.  We've already examined one scenario which illlustrates this
point: birthday matching.
\fi

We observed in lecture that the expected number of matching birthday pairs
among $n$ people was $\binom{n}{2}/365$.  But how close to this expected
value can we expect a typical sample to be?  We can apply the Pairwise
Independent Sampling Theorem to answer this question.

Now having matching birthdays for different pairs of students are not
mutually independent events.  For example, knowing that Alice and Bob have
matching birthdays, and also that Ted and Alice have matching birthdays
obviously implies that Bob and Ted have matching birthdays.  On the other
hand, knowing that Alice and Bob have matching birthdays tells us nothing
about whether Alice and Carol have matching birthdays, \viz these two
events really are independent.  We already already observed this
phenomenon in
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln11-12.pdf}
{Notes 11-12, \S4.3.1}, for the case of matching pairs among three coins.  So
even though the events that a pair of students have matching birthdays are
not mutually independent, indeed not even three-way independent, they are
\emph{pairwise} independent.

This allows us to apply the Sampling Theorem.  Let $B_1,B_2,\dots,B_n$ be
the birthdays of the $n$ people, let $E_{i,j}$ be the indicator variable
for the event $[B_i = B_j]$.  For $i\neq j$, the probability that $B_i =
B_j$ is 1/365, so $\expect{E_{i,j}} = 1/365$.

Now let $M_n$ be the number of matching pairs, \ie
\begin{equation}\label{Vn}
M_n \eqdef \sum_{1\le i < j \le n} E_{i,j}.
\end{equation}

So by linearity of expectation
\[
\expect{M_n} = \expect{\sum_{1\le i < j \le n} E_{i,j}} = 
               \sum_{1\le i < j \le n} \expect{E_{i,j}} =
               \binom{n}{2}\frac{1}{365},
\]
as we noted above.  Also, by linearity of variance for pairwise
independent variables
\[
\variance{M_n} = \variance{\sum_{1\le i < j \le n} E_{i,j}} = 
               \sum_{1\le i < j \le n} \variance{E_{i,j}} =
               \binom{n}{2}\frac{1}{365}\left(1-\frac{1}{365}\right).
\]

%%%UPDATE BELOW WITH FALL 02 DATA

Now for our 6.042 class of 146 students, we have $\expect{M_{146}} = 29$ 
and $\variance{M_{146}} = 29(1- 1/365) < 29$.  So by
Theorem~\ref{devmean},
\[
\pr{\abs{M_{146} - 29} \geq x} < \frac{29}{x^2}.
\]
Letting $x=8$, we conclude that there is a better than 50\% chance that in
a class of 146 students, the number of pairs of students with the same
birthday will be between 21 and 37.  In our class, we actually found that
there were 17 matching pairs and 2 triples, for a total of 23 matching
pairs.

%%%UPDATE ABOVE WITH FALL 02 DATA

\iffalse
Add another calculation, say for a 6.001 class of 400, or for uniform
selection of numbers from 1 to 1,000,000.
\fi


\subsection{Size of a Poll}

Theorem~\ref{devmean} allows us to calculate poll size.  How many people
should we poll to get a reliable estimate of voters' preference?

\iffalse The results will be weaker than we previously derived using
approximations to the binomial distribution, but they are still
illustrative.\fi


\iffalse
Notice that if $p=0$ or $p = 1$ our estimate is guaranteed to be
correct, so we henceforth assume $0<p<1$.
\fi

Suppose, in particular, we want to know within tolerance $x \eqdef 0.02$
what fraction of the voters favor Gore.  By choosing $n$ large enough in
Theorem~\ref{devmean} that we can reduce the probability that our estimate
is off by more than $x$ to as close to zero as we please.

For example, ninety-five per cent ``confidence level'' is a standard used
in many statistical applications.  So let's suppose we want our estimate
of $p$ to be within the tolerance 95\% of the time, that is, with
probability 0.95.  Then we choose $n$ so that $(1/n)(\sigma/x)^2 \leq 1 -
0.95$.  That is, we want
\[
n \geq \frac{\sigma^2}{(0.02)^2(1-0.95))} = \frac{p(1-p)}{0.00002} = 50,000p(1-p).
\]
Solving for the sample size $n$ in terms of the unknown $p$ that we are
trying to estimate in the first place may not seem to be making progress,
but it's easy to see that the maximum value of $p(1-p)$ in the interval
$0\leq p \leq 1$ occurs at $p=1/2$.  So we conclude that if we sample
\[
n \geq 50,000(1-1/2)1/2 = 12,500
\]
voters, we can say that 95\% of the time, our estimate $S_{12,500}/12,500$
will be within 0.02 of the fraction of voters who favor Gore.

Note that this bound on poll size holds regardless of how large the total
voting population may be---whether we are trying to determine the
preferences of a few tens of thousands of voters in a small city like
Cambridge, or of the tens of millions of voters in a large nation like the
U.S., the same poll size is adequate.

\subsection{Confidence Levels}

Now suppose a pollster dutifully checks with 12,500 randomly chosen voters
and finds that 6,300 prefer Gore.  It's tempting, but sloppy, to say that
this means ``With probability 0.95, the fraction, $p$, of voters who
prefer Gore is $6300/12,500 = 0.504 \pm 0.02$.''

What's objectionable about this statement is that it talks about the
probability of a real world fact, namely the actual value of the fraction
$p$.  But $p$ is what it is, and it simply makes no sense to talk about
the probability that it is something else.  For example, suppose $p$ is
actually 0.53; then it's nonsense to ask about the probability that it is
within 0.02 of 0.504---it simply isn't.

A more careful summary of what we have accomplished goes this way: we have
described a probabilistic procedure for estimating the actual value of the
fraction $p$.  The probability that \emph{our estimation procedure} will
yield a value within 0.02 of $p$ is 0.95.  This is a bit of a mouthful, so
special phrasing closer to the sloppy language is commonly used.  The
pollster would describe his conclusion by saying that ``At the 95\%
\emph{confidence level}, the fraction of voters who prefer Gore is $0.504
\pm 0.02$.''

Actually, polling 12,500 voters is excessive.  We derived this bound on
poll size solely by applying Chebyshev's Theorem to the value of the
variance of $S_n/n$.  But in fact we know the exact distribution of $S_n$,
namely, it has a binomial distribution with parameters $n,p$.  In the next
section we do a more detailed calculation of probabilities of deviation
from the mean specifically for the binomial distribution; we can show that
the poll size need only be about 1/5 of the size derived from the
Chebyshev bound.

\subsection{Better Polling}

Let $\epsilon$ be the acceptable error tolerance of our poll.  In the
previous section we chose $\epsilon = 0.02$.  We can define $\delta$, the
probability that our poll is off by more than $\epsilon$ as follows:
\begin{eqnarray*}
\delta  & \eqdef &
        \underbrace{\pr{\frac{S_n}{n} < p - \epsilon}}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{say ``Bush''}
\end{array}}
        + \underbrace{\pr{\frac{S_n}{n} > p + \epsilon}}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{say ``Gore''}
\end{array}} \\
        & = & \pr{S_n < (p - \epsilon) n} + \pr{S_n > (p + \epsilon) n}.
\end{eqnarray*}

Since $S_n$ has the binomial distribution with parameters $n$ and $p$,
the two terms in the definition of $\delta$ can be bounded using the
bound~(\ref{Fbyf}) on $F_{n,p}$ from Notes 10:
\begin{lemma*}
\begin{equation}\label{Fbyf}
F_{n, p}(\alpha n) \leq
\left(\frac{1 - \alpha}{1 - \alpha/p}\right) f_{n, p}(\alpha n)
\end{equation}
for $\alpha < p$.
\end{lemma*}

To ensure that $\alpha < p$, we observe that
\[
\pr{\frac{S_n}{n} > p + \epsilon} = \pr{\frac{n - S_n}{n} < 1 -p - \epsilon},
\]
where $(n - S_n)/n$ is the fraction of people polled who say that they
prefer Bush, and $1-p$ is the fraction of all Americans who prefer Bush.
This gives
\begin{equation}\label{Fnpe}
\delta \leq F_{n,p}((p - \epsilon) n) + F_{n,1-p}((1-p-\epsilon) n).
\end{equation}

As in the previous section, the bound~(\ref{Fnpe}) contains $p$, the
fraction of Americans that favor Gore, which is the number we are trying
to determine by polling.  But as before, the worst case for the bound is
when $p = 1/2$, though we shall not prove this.  So we get
\begin{equation}\label{delta bound}
\delta \leq F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n) +
   F_{n,1-\frac{1}{2}}((1-\frac{1}{2}-\epsilon) n)
 = 2 F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n).
\end{equation}

Now plugging in $\epsilon = 0.02$ into~(\ref{delta bound}) gives:
\begin{align*}
\delta \leq  2 F_{n,\frac{1}{2}}(0.48 n)
    & \leq 2 \cdot  \frac{1 - \alpha}{1 - 2\alpha} f_{n,1/2}(0.48 n)\\
    &  \approx 2 \cdot 13 \cdot 2^{-n(1 - H(0.48))}/\sqrt{2\pi \cdot 0.48(1-0.48)n}\\
    & = 26 \cdot \frac{2^{-0.00115 n}}{1.2523 \sqrt{n}}.
\end{align*}

We want to poll enough people so that $\delta$ is less than $0.05$.
The easiest way is to plug in values for $n$, the number of people
polled:
\[
\begin{array}{c|l}
\mbox{$n$ = people polled} & \begin{array}{cc}
\mbox{upper bound on} \\
\mbox{probability poll is wrong}
\end{array} \\
\hline
1000 &  29.4\% \\
2000 &  9.3\% \\
3000 &  3.4\% \\
2500 &  5.6\% \\
2750 &  4.4\%\\
2616 &  5.004\%\\
2617 &  4.999\%
\end{array}
\]

So polling 2617 people is sufficient to determine public opinion to within
2\% with confidence of 95\%.  Again, the remarkable point is that the
population of the country has no effect on the poll size.  Whether there
are ten thousand people or a billion in a country, polling 2617 people
is sufficient!

Here we got a much better estimate of probable deviation from the mean
using the fact that the samples were independent---and hence that the
sampling distribution was binomial---than in the previous section using
the Pairwise Independent Sampling Theorem~\ref{devmean}.  This should not
be surprising, since the Sampling Theorem is based on Chebyshev's bound,
and we've already seen that the Chebyshev bound can be much weaker than
bounds derived using more information about a density function than simply
its variance.

However, there are situations---matching birthdays is a good
example---where mutual independence of the samples doesn't hold, but
pairwise independence does, and that's where the Pairwise Independent
Sampling Theorem becomes our main handle on predicting sample deviations.


\section{Proof of the Weak Law}
An equivalent way to state the conclusion of the Weak Law of Large
Numbers, Theorem~\ref{weaklaw-lim1}, is that the probability that the
average \emph{differs} from the expectation by more than any given
tolerance approaches zero.

\begin{theorem}\label{weaklaw-lim0}[Weak Law of Large Numbers]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i,
\]
where $G_1, \dots, G_n, \dots$ are pairwise independent variables with the
same expectation, $\mu$ and standard deviation, $\sigma$.  For any
$\epsilon > 0$,
\[
\lim_{n \rightarrow \infty} \pr{\abs{\frac{S_n}{n} - \mu} \geq \epsilon} = 0.
\]
\end{theorem}

\begin{proof}
Choose $x$ in Theorem~\ref{devmean} to be $\epsilon$.  Then, given any
$\delta>0$, choose $n$ large enough to make $(\sigma/x)^2/n < \delta$.
By Theorem~\ref{devmean},
\[
\pr{\abs{\frac{S_n}{n} - \mu} \geq \epsilon} < \delta.
\]
So the limiting probability must equal zero.
\end{proof}

Notice that this version of the Weak Law is slightly different from the
version we first stated in Theorem~\ref{weaklaw-lim1}.
Theorem~\ref{weaklaw-lim0} requires that the $G_i$'s have finite variance
but Theorem~\ref{weaklaw-lim1} only requires finite expectation.  On the
other hand, the original version~\ref{weaklaw-lim1} requires mutual
independence, while Theorem~\ref{weaklaw-lim0} requires only pairwise
independence.  The case when the variance may be infinite is not important
to us, and we will not try to prove it.

A weakness of both the Weak Law as well as our Pairwise Independence
Sampling Theorem~\ref{devmean} is that neither provides any information
about the way the average value of the observations may be expected to
\emph{oscillate} in the course of repeated experiments.  In later Notes we
will briefly consider a \emph{Strong} Law of Large Numbers which deals
with the oscillations.  Such oscillations may not be important in our
example of polling about Gore's popularity or of birthday matches, but
they are critical in gambling situations, where large oscillations can
bankrupt a player, even though the player's average winnings are assured
in the long run.  As the famous economist Keynes is alleged to have
remarked, the problem is that ``In the long run, we are all dead.''


\section{Random Walks and Gamblers' Ruin}

Random Walks nicely model many natural phenomena in which a person, or
particle, or process takes steps in a randomly chosen sequence of
directions.  For example in Physics, three-dimensional random walks are
used to model Brownian motion and gas diffusion.  In Computer Science, the
Google search engine uses random walks through the graph of world-wide web
links to determine the relative importance of websites.  In Finance
Theory, there is continuing debate about the degree to which
one-dimensional random walks can explain the moment-to-moment or day-to-day
fluctuations of market prices.  In these Notes we consider 1-dimensional
random walks: walks along a straight line.  Our knowledge of expectation
and deviation will make 1-dimensional walks easy to analyze, but even
these simple walks exhibit probabilistic behavior that can be astonishing.

In the Mathematical literature, random walks are for some reason
traditionally discussed in the context of some social vice.  A
one-dimensional random walk is often described as the path of a drunkard
who randomly staggers left or right at each step.  In the rest of these
Notes, we examine one-dimensional random walks using the language of
gambling.  In this case, a position during the walk is a gambler's
cash-on-hand or \emph{capital}, and steps on the walk are bets whose
random outcomes increase or decrease his capital.  We will be interested
in two main questions:
\begin{enumerate}
\item What is the probability that the gambler wins?
\item How long must the gambler expect to wait for the walk to end?
\end{enumerate}

In particular, we suppose a gambler starts with $n$ dollars.  He makes a
sequence of \$1 bets.  If he wins an individual bet, he gets his money
back plus another \$1.  If he loses, he loses the \$1.  In each bet, he
wins with probability $p>0$ and loses with probability $q \eqdef 1-p >0$.
The gambler plays until either he is bankrupt or increases his capital to
a goal amount of $T$ dollars.  If he reaches his goal, then he is called
an overall {\em winner}, and his \emph{profit} will be $m \eqdef T-n$
dollars.  If his capital reaches zero dollars before reaching his gaol,
then we say that he is ``ruined'' or {\em goes broke}.

The gambler's situation as he proceeds with his \$1 bets is illustrated in
Figure~\ref{fig:walk1}.  The random walk has boundaries at 0 and $T$.  If
the random walk ever reaches either of these boundary values, then it
terminates.  We want to determine the probability, $w$, that the walk
terminates at boundary $T$, namely, the probability that the gambler is a
winner.

\begin{figure}
  \centerline{\includegraphics[height=2.5in]{figures/walk1}}
  \caption{\em This is a graph of the gambler's capital versus time
  for one possible sequence of bet outcomes.  At each time step, the
  graph goes up with probability $p$ and down with probability $1-p$.
  The gambler continues betting until the graph reaches either 0 or $T
  = n + m$.}
  \label{fig:walk1}
\end{figure}

In a fair game, $p = q = 1/2$.  The corresponding random walk is
called {\em unbiased}.  The gambler is more likely to win if $p>1/2$ and
less likely to win if $p<1/2$; the corresponding random walks are called
{\em biased}.

\begin{example}
Suppose that the gambler is flipping a coin, winning \$1 on Heads and
losing \$1 on Tails.  Also, the gambler's starting capital is $n = 500$
dollars, and he wants to make $m = 100$ dollars.  That is, he plays until
he goes broke or reaches a goal of $T = n + m = \$600$.  What is the
probability that he is a winner?  We will show that in this case the
probability $w = 5/6$.  So his chances of winning are really very good,
namely, 5 chances out of 6.

Now suppose instead, that the gambler chooses to play roulette in an
American casino, always betting \$1 on red.  A roulette wheel has 18 black
numbers, 18 red numbers, and 2 green numbers.  In this game, the
probability of winning a single bet is $p = 18/38 \approx 0.47$.  It's the
two green numbers that slightly bias the bets and give the casino an edge.
Still, the bets are almost fair, and you might expect that the gambler has
a reasonable chance of reaching his goal---the 5/6 probability of winning
in the unbiased game surely gets reduced, but perhaps not too drastically.
Not so!  His odds of winning against the ``slightly'' unfair roulette
wheel are less than 1 in 37,000.  If that seems surprising, listen to this:
\emph{no matter how much money} the gambler has to start, \eg \$5000,
\$50,000, $\$5 \cdot 10^{12}$, his odds are still less than 1 in 37,000 of
winning a mere 100 dollars!

Moral:  Don't play!
\end{example}

The theory of random walks is filled with such fascinating and
counter-intuitive conclusions.

\section{The Probability Space}

Each random-walk game corresponds to a path like the one in
Figure~\ref{fig:walk1} that starts at the point $(n,0)$.  A winning path
never touches the $x$ axis and ends when it first touches the line $y=T$.
Likewise, a losing path never touches the line $y=T$ and ends when it first
touches the $x$ axis.

\iffalse

\setlength{\unitlength}{0.0125in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(300,175)(0,-10)
\path(40,160)(40,0)
\path(20,40)(300,40)
\dottedline{5}(20,140)(300,140)
\path(40,80)(60,100)(80,80)
	(100,100)(120,120)(140,100)
	(160,120)(180,100)(200,80)
	(220,60)(240,80)(260,100)
	(280,120)(300,140)
\put(0,140){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}T}}}}}
\put(0,40){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}0}}}}}
\put(60,20){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}1}}}}}
\put(80,20){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}2}}}}}
\put(100,20){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}3}}}}}
\put(0,80){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}n}}}}}
\end{picture}
\fi

Any length $k$ path can be characterized by the history of wins and losses
on individual \$1 bets, so we use a length $k$ string of $W$'s and $L$'s to
model a path, and assign probability $p^rq^{k-r}$ to a string that contains
$r$ $W$'s.  The \emph{outcomes} in our sample space will be precisely those
string corresponding to winning or losing walks.

What about the infinite walks in which the gambler plays forever, neither
reaching his goal nor going bankrupt?  We saw in an in-class problem that
the probability of playing forever is zero, so we don't need to include
any such outcomes in our sample space.

As a sanity check on this definition of the probability space, we should
verify that the sum of the outcome probabilities is one, but we omit this
calculation.

\iffalse

To do this, we
let $X$ be any string of $W$'s and $L$'s, and let $[X]$ be the event
consisting of the outcomes that begin with $X$.  If $X$ itself is not an
outcome but begins with an outcome, then $[X] = \emptyset$ so $\pr{[X]} =
0$.  On the other hand, if no prefix of $X$ is an outcome, then it's easy
to verify by induction on $k$ that $\pr{[X]} = p^rq^{k-r}$.  length $k$

%%%COMPLETE

We'll leave this to the reader.
\fi

\section{The Probability of Winning}

\subsection{The Unbiased Game}

Let's begin by considering the case of a fair coin, that is, $p = 1/2$, and
determine the probability, $w$, that the gambler wins.  We can handle this
case by considering the expectation of the random variable $G$ equal to the
gambler's dollar gain.  That is, $G = T-n$ if the gambler wins, and $G= -n$
if the gambler loses, so
\[
\expect{G} = w(T-n) - (1-w)n = wT - n.
\]
Notice that we're using the fact that the only outcomes are those in which
the gambler wins or loses---there are no infinite games---so the
probability of losing is $1-w$.

Now let $G_{i}$ be the amount the gambler gains on the $i$th flip:
$G_{i}=1$ if the gambler wins the flip, $G_{i}=-1$ if the gambler loses
the flip, and $G_{i}=0$ if the game has ended before the $i$th flip.
Since the coin is fair, $\expect{G_{i}}=0$.

The random variable $G$ is the sum of all the $G_{i}$'s, so by linearity of
expectation\footnote{We've been stung by paradoxes in this kind of
situation, so we should be careful to check that the condition for infinite
linearity of expectation is satisfied.  Namely, we have to check that
$\sum_{i=1}^\infty \expect{\abs{G_i}}$ converges.

In this case, $\abs{G_i} = 1$ iff the walk is of length at least $i$, and
$\abs{G_i} = 0$ otherwise.  So
\[
\expect{\abs{G_i}} = \pr{\text{the walk is of length } \geq i}.
\]

But we show in an in-class problem that there is a constant $r<1$
such that
\[
\pr{\text{the walk is of length } \geq i} \leq \Theta(r^i).
\]
So the $\sum_{i=1}^\infty \expect{\abs{G_i}}$ is bounded term-by-term by a
convergent geometric series, and therefore it also converges.}
\[
wT - n= E(G) = \sum_{i=1}^{\infty}E(G_{i}) = 0,
\]
which proves
\begin{theorem}\label{fairwinthm}
In the unbiased Gambler's Ruin game with probability $p=1/2$ of winning
each individual bet, with initial capital, $n$, and goal, $T$,
\begin{equation}\label{fairwin}
\pr{\text{the gambler is a winner}} = \frac{n}{T}.
\end{equation}
\end{theorem}

\begin{example}
Suppose we have \$100 and we start flipping a fair coin, betting \$1 with
the aim of winning \$100.  Then the probability of reaching the \$200 goal
is $100/200=1/2$---the same as the probability of going bankrupt.  In
general, if $T=2n$, then the probability of doubling your money or losing
all your money is the same.  This is about what we would expect.
\end{example}

\begin{example}\label{win100}
Suppose we have \$500 and we start flipping a fair coin, betting \$1 with
the aim of winning \$100.  So $n=500, T=600$, and $\pr{\mbox{win}} =
500/600 = 5/6$, as we claimed at the outset.
\end{example}

\begin{example}
Suppose Albert starts with \$100, and Radhi starts with \$10.  They flip a
fair coin, and every time a Head appears, Albert wins \$1 from Radhi, and
vice versa for Tails.  They play this game until one person goes bankrupt.
What is the probability of Albert winning?

This problem is identical to the Gambler's Ruin problem with $n=100$ and
$T=100+10=110$.  The probability of Albert winning is $100/110 = 10/11$,
namely, the ratio of his wealth to the combined wealth.  Radhi's chances of
winnning are $1/11$.

Note that although Albert will win most of the time, the game is still
fair.  When Albert wins, he only wins \$10; when he loses, he loses
big: \$100.  Albert's---and Radhi's---expected win is zero dollars.
\end{example}

Another intuitive idea is confirmed by this analysis: the larger the
gambler's initial stake, the larger the probability that he will win a
fixed amount.

\begin{example}
If the gambler started with one million dollars instead of 500, but aimed
to win the same 100 dollars as in the Example~\ref{win100}, the
probability of winning would increase to $1M/(1M + 100) > .9999$.
\end{example}

\subsection{A Recurrence for the Probability of Winning}

To handle the case of a biased game we need a more general approach.  We
consider the probability of the gambler winning as a function of his
initial capital.  That is, let $p$ and $T$ be fixed, and let $w_n$ be the
gambler's probabiliity of winning when his initial capital is $n$ dollars.
For example, $w_0$ is the probability that the gambler will win given that
he starts off broke; clearly, $w_0 = 0$.  Likewise, $w_T =1$.

Otherwise, the gambler starts with $n$ dollars, where $0 < n < T$.
Consider the outcome of his first bet.  The gambler wins the first bet with
probability $p$.  In this case, he is left with $n+1$ dollars and becomes a
winner with probability $w_{n+1}$.  On the other hand, he loses the first
bet with probability $1-p$.  Now he is left with $n-1$ dollars and becomes
a winner with probability $w_{n-1}$.  Overall, he is a winner with
probability $w_n = p w_{n+1} + q w_{n-1}$.  Solving for $w_{n+1}$ we
have
\begin{equation}\label{rec1}
w_{n+1} = \frac{w_n}{p} - w_{n-1}\frac{q}{p}.
\end{equation}

This kind of inductive definition of a quantity $w_{n+1}$ in terms of a
linear combination of values $w_k$ for $k < n+1$ is called a
\emph{homogeneous linear recurrence}.  There is a simple general method for
solving such recurrences which we now illustrate.  The method is based on a
guess that the form of the solution is $w_n = c^n$ for some $c>0$.  It's
not obvious why this is a good guess, but we now show how to find the
constant $c$ and verify the guess.

Namely, from~(\ref{rec1}) we have
\begin{equation}\label{rec2}
w_{n+1} - \frac{w_n}{p} + w_{n-1}\frac{q}{p} = 0.
\end{equation}
If our guess is right, then this is equivalent to
\[
c^{n+1} - \frac{c^n}{p} + c^{n-1}\frac{q}{p} = 0.
\]
Now factoring out $c^{n-1}$ gives
\[
c^2 - \frac{c}{p} + \frac{q}{p} = 0.
\]
Solving this quadratic equation in $c$ yields two roots, $(1 - p)/p$ and 1.
\iffalse
\begin{eqnarray*}
c       & = &   \frac{1/p \pm \sqrt{(1/p)^2 - 4(q/p)}}{2} \\
        & = &   \frac{1 \pm \sqrt{1 - 4p(1-p)}}{2p} \\
        & = &   \frac{1 \pm \sqrt{1 - 4p - 4 p^2}}{2p} \\
        & = &   \frac{1 \pm \sqrt{(1 - 2p)^2}}{2p} \\
        & = &   \frac{1 - p}{p} \text{ or } 1.
\end{eqnarray*}
\fi
So if we define $w_n \eqdef ((1-p)/p)^n =
(q/p)^n$, then~(\ref{rec2}), and hence~(\ref{rec1}) is satisifed.  We can
also define $w_n \eqdef 1^n$ and satisfy ~(\ref{rec2}).  Since the lefthand
side of~(\ref{rec2}) is zero using either definition, it follows that any
definition of the form
\begin{equation*}
w_n \eqdef A\left(\frac{q}{p}\right)^n + B\cdot 1^n
\end{equation*}
will also satisfy~(\ref{rec2}).  Now our boundary conditions, namely the
values of $w_0$ and $w_T$, let us solve for $A$ and $B$:
\[\begin{array}{rcccl}
0 & = & w_0 & = & A + B,\\
1 & = & w_T & = &  A\left(\dfrac{q}{p}\right)^T + B,
\end{array}
\]
so
\begin{equation}
A =  \frac{1}{(q/p)^T -1},\qquad B = -A,
\end{equation}
and therefore
\begin{equation}
w_n = \frac{(q/p)^n-1}{(q/p)^T -1}. \label{wnsol}
\end{equation}
Now we could verify our guess work and prove~(\ref{wnsol}) by a routine
induction on $n$ which we omit.

The solution~(\ref{wnsol}) only applies to biased walks, since we require
$p \neq q$ so the denominator is not zero.  That's ok, since we already
worked out that the case when $p=q$ in Theorem~\ref{fairwinthm}.  So we
have shown:
\begin{theorem}\label{biaswinthm}   
In the biased Gambler's Ruin game with probability, $p \neq 1/2$, of
winning each bet, with initial capital, $n$, and goal, $T$,
\begin{equation}\label{biaswin}
\pr{\text{the gambler is a winner}} = \frac{(q/p)^n-1}{(q/p)^T -1}.
\end{equation}
\end{theorem}

%\subsection{A Simplified Bound}

The expression~(\ref{biaswin}) for the probability that the Gambler wins
in the biased game is a little hard to interpret.  There is a simpler
upper bound which is nearly tight when the gambler's starting capital is
large.

Suppose that $p < 1/2$; that is, the game is biased {\em against} the
gambler.  Then both the numerator and denominator in the quotient
in~(\ref{biaswin}) are positive, and the quotient is less than one.  So
adding 1 to both the numerator and denominator increases the
quotient\footnote{
If $0 < a < b$, then
\[
\frac{a}{b} < \frac{a+1}{b+1},
\]
because
\[
\frac{a}{b} = \frac{a(1+1/b)}{b(1+1/b)} = \frac{a+a/b}{b+1} < \frac{a+1}{b+1}.
\]}, and the bound~(\ref{biaswin}) simplifies to $(q/p)^n/(q/p)^T
= (p/q)^{T-n}$, which proves
\begin{corollary}\label{biaswincor}
In the Gambler's Ruin game biased against the Gambler, that is, with
probability $p< 1/2$ of winning each bet, with initial
capital, $n$, and goal, $T$,
\begin{equation}\label{biaswinsimp}
\pr{\text{the gambler is a winner}} < \left(\frac{p}{q} \right)^m,
\end{equation}
where $m \eqdef T-n$.
\end{corollary}

The amount $m = T-n$ is called the Gambler's \emph{intended profit}.  So
the gambler gains his intended profit, $m$, before going broke with
probability at most $(p/q)^m$.  Notice that this upper bound does not
depend on the gambler's starting capital, but only on his intended profit.
The consequences of this are amazing:

\begin{example}
Suppose that the gambler starts with \$500 aiming to profit \$100, this
time by making \$1 bets on red in roulette.  By~(\ref{biaswinsimp}), the
probability, $w_n$, that he is a winner is less than
\[
\left( \frac{18/38}{20/38} \right)^{100}
   =      \left( \frac{9}{10} \right)^{100}
   <      \frac{1}{37,648}.
\]
This is a dramatic contrast to the unbiased game, where we saw in
Example~\ref{win100} that his probability of winning was 5/6.
\end{example}

\begin{example}
We also observed that with \$1,000,000 to start in the unbiased game, he
was almost certain to win \$100.  But betting against the ``slightly''
unfair roulette wheel, even starting with \$1,000,000, his chance of
winning \$100 remains less than 1 in 37,648!  He will almost surely lose
all his \$1,000,000.  In fact, because the bound~(\ref{biaswinsimp})
depends only on his intended profit, his chance of going up a mere \$100
is less than 1 in 37,648 \emph{no matter how much money he starts with}!
\end{example}

The bound~(\ref{biaswinsimp}) is exponential in $m$.  So, for example,
doubling his intended profit will square his probability of winning.
\begin{example}
The probability that the gambler's stake goes up $200$ dollars before he
goes broke playing roulette is at most
\[
(9/10)^{200} = ((9/10)^{100})^2 = \left(\frac{1}{37,648}\right)^2,
\]
which is about 1 in 70 billion.
\end{example}

The odds of winning a little money are not so bad.
\begin{example}
Applying the exact formula~(\ref{biaswin}), we find that the probability
of winning \$10 before losing \$10 is
\[
\frac{\left( \frac{20/38}{18/38} \right)^{10} - 1}
              {\left( \frac{20/38}{18/38} \right)^{20} - 1}
  = 0.2585\dots
\]
This is somewhat worse than the 1 in 2 chance in the fair game, but not
dramatically so.
\end{example}

Thus, in the fair case, it helps a lot to have a large bankroll,
whereas in the unfair case, it doesn't help much.

\subsection{Intuition}

Why is the gambler so unlikely to make money when the game is slightly
biased against him?  Intuitively, there are two forces at work.
First, the gambler's capital has random upward and downward {\em
swings} due to runs of good and bad luck.  Second, the gambler's
capital will have a steady, downward {\em drift}, because he has a
small, negative expected return on every bet.  The situation is shown
in Figure~\ref{fig:walk2}.

For example, in roulette the gambler wins a dollar with probability $9/19$
and loses a dollar with probability $10/19$.  Therefore, his expected
return on each bet is $9/10 - 10/19 = - 1/19 \approx -0.053$ dollars.  That
is, on each bet his capital is expect to drift downward by a little over 5
cents.

Our intuition is that if the gambler starts with a trillion dollars, then
he will play for a very long time, so at some point there should be a
lucky, upward swing that puts him \$100 ahead.  The problem is that his
capital is steadily drifting downward.  If the gambler does not have a
lucky, upward swing early on, then he is doomed.  After his capital drifts
downward a few hundred dollars, he needs a huge upward swing to save
himself.  And such a huge swing is extremely improbable.  As a rule of
thumb, \emph{drift dominates swings} in the long term.

%\begin{nooutline}
\begin{figure}
\centerline{\includegraphics[height=2.5in]{figures/walk2}}
\caption{\em In an unfair game, the gambler's capital swings randomly up
and down, but steadily drifts downward.  If the gambler does not have
a winning swing early on, then his capital drifts downward, and later
upward swings are insufficient to make him a winner.}
\label{fig:walk2}
\end{figure}
%\end{nooutline}

We can quantify these drifts and swings.  After $k$ rounds, the number of
wins by our player has a binomial distribution with parameters $p < 1/2$
and $k$.  His expected win on any single bet is $p-q = 2p-1$ dollars, so
his expected capital is $n-k(1-2p)$.  Now to be a winner, his actual number
of wins must exceed the expected number by $m+k(1-2p)$.  But we saw before
that the binomial distribution has a standard deviation of only
$\sqrt{kp(1-p)}$.  So for the gambler to win, he needs his number of wins
to deviate by
\[
\frac{m+k(1-2p)}{\sqrt{kp(1-2p)}}=\Theta(\sqrt{k})
\]
times its standard deviation.  In our study of binomial tails we saw that
this was extremely unlikely.

In a fair game, there is no drift; swings are the only effect.  In the
absence of downward drift, our earlier intuition is correct.  If the
gambler starts with a trillion dollars then almost certainly there
will eventually be a lucky swing that puts him \$100 ahead.

If we start with \$10 and play to win only \$10 more, then the difference
between the fair and unfair games is relatively small. We saw that the
probability of winning is $1/2$ versus about $1/4$.  Since swings of \$10
are relatively common, the game usually ends before the gambler's capital
can drift very far.  That is, the game does not last long enough for drift
to dominate the swings.

\section{How Long a Walk?}

Now that we know the probability, $w_n$, that the gambler is a winner in
both fair and unfair games, we consider how many bets he needs on average
to either win or go broke.

\subsection{Duration of an Biased Walk}

Let $Q$ be the number of bets the gambler makes until the game ends.  Since
the gambler's expected win on any bet is $2p-1$, Wald's Theorem should tell
us that his game winnings, $G$, will have expectation $\expect{Q}(2p-1)$.
That is,
\begin{equation}\label{gw}
\expect{G} = (2p-1)\expect{Q},
\end{equation}

In an unbiased game~(\ref{gw}) is trivially true because both $2p-1$ and
the expected overall winnings, $\expect{G}$, are zero.  On the other hand,
in the unfair case, $2p-1 \neq 0$.  Also, we know that
\[
\expect{G} = w_n(T-n) - (1-w_n)n = w_nT-n.
\]
So assuming~(\ref{gw}), we conclude
\begin{theorem}\label{ExQthm}
In the biased Gambler's Ruin game with initial capital, $n$, goal,
$T$, and probability, $p \neq 1/2$, of winning each bet,
\begin{equation}\label{ExQ}
\expect{\text{number of bets till game ends}} =
\frac{\pr{\text{gambler is a winner}}T-n}{2p-1}.
\end{equation}
\end{theorem}

The only problem is that~(\ref{gw}) is not a special case of Wald's
Theorem because $G = \sum_{i=1}^Q G_i$ is not a sum of \emph{nonnegative}
variables: when the gambler loses the $i$th bet, the random variable $G_i$
equals $-1$.  However, this is easily dealt with.\footnote{The random variable
$G_i+1$ is nonnegative, and $\expcond{G_i+1}{Q \geq i} =
\expcond{G_i}{Q\geq i}+1 = 2p$, so by Wald's Theorem
\begin{equation}\label{G1}
\expect{\sum_{i=1}^Q (G_i+1)}  = 2p\expect{Q}.
\end{equation}
But
\begin{eqnarray}
\expect{\sum_{i=1}^Q (G_i+1)} & = & \expect{\sum_{i=1}^Q G_i + \sum_{i=1}^Q 1}\notag\\
   & = & \expect{(\sum_{i=1}^Q G_i) + Q}\notag\\
   & = & \expect{\sum_{i=1}^Q G_i} + \expect{Q}\notag\\
   & = & \expect{G} + \expect{Q}\label{GQ}.
\end{eqnarray}
Now combining~(\ref{G1}) and~(\ref{GQ}) confirms the truth of our
assumption~(\ref{gw}).}

\begin{example}
If the gambler aims to profit \$100 playing roulette with $n$ dollars to
start, he can expect to make $((n+100)/37,648 - n)/(2(18/38) - 1) \approx
19n$ bets before the game ends.  So he can enjoy playing for a good while
before almost surely going broke.
\end{example}


\subsection{Duration of an Unbiased Walk}

This time, we need the more general approach of recurrences to handle the
unbiased case.  We consider the expected number of bets as a
function of the gambler's initial capital.  That is, for fixed $p$ and $T$,
let $e_n$ be the expected number of bets until the game ends when the
gambler's initial capital is $n$ dollars.  Since the game is over in no
steps if $n=0$ or $T$, the boundary conditions this time are $e_0=e_T=0$.

Otherwise, the gambler starts with $n$ dollars, where $0 < n < T$.
Now by the conditional expectation rule, the expected number of steps can
be broken down into the expected number of steps given the outcome of the
first bet weighted by the probability of that outcome.  That is,
\[
e_n = p\expcond{Q}{\text{gambler wins first bet}} +
q\expcond{Q}{\text{gambler loses first bet}}.
\]
But after the gambler wins the first bet, his capital is $n+1$, so
he can expect to make another $e_{n+1}$ bets.  That is,
\[
\expcond{Q}{\text{gambler wins first bet}} = 1 + e_{n+1},
\]
and similarly, 
\[
\expcond{Q}{\text{gambler loses first bet}} = 1 + e_{n-1}.
\]
So we have
\[
e_n =  p(1 + e_{n+1}) +  q(1 + e_{n-1}) =  pe_{n+1} + qe_{n-1} + 1, 
\]
which yields the linear recurrence
\[
e_{n+1} = \frac{e_n}{p} - \frac{q}{p} e_{n-1} - \frac{1}{p}.
\]
For $p = q = 1/2$, this equation simplifies to
\begin{equation}\label{en2}
e_{n+1} = 2e_n - e_{n-1} - 2.
\end{equation}
There is a general theory for solving linear recurrences like~(\ref{en2})
in which the value at $n+1$ is a linear combination of values at some
arguments $k<n+1$ plus another simple term---in this case plus the constant
$-2$.  This theory implies that
\begin{equation}\label{Tn}
e_n  = (T - n)n.
\end{equation}
Fortunately, we don't need the general theory to \emph{verify} this
solution.  Equation~(\ref{Tn}) can be verified routinely from the boundary
conditions and~(\ref{en2}) using strong induction on $n$.

So we have shown
\begin{theorem}\label{fairtime}
In the unbiased Gambler's Ruin game with initial capital, $n$, and goal,
$T$, and probability, $p = 1/2$, of winning each bet,
\begin{equation}
\expect{\text{number of bets till game ends}} = n(T-n).
\end{equation}
\end{theorem}

Another way to phrase Theorem~\ref{fairtime} is
\begin{equation}\label{mn}
\expect{\text{number of bets till game ends}} = \text{initial capital}
\cdot \text{intended profit}.
\end{equation}

Now for example, we can conclude that if the gambler starts with \$10
dollars and plays until he is broke or ahead \$10, then $10 \cdot 10 = 100$
bets are required on average.  If he starts with \$500 and plays until he
is broke or ahead \$100, then the expected number of bets until the game is
over is $500 \times 100 = 50,000$.

Notice that~(\ref{mn}) is a very simple answer that cries out for an
intuitive proof, but we have not found one.

\iffalse

\textbf{Below is my try at the suggestion of Santosh and Adam Kalai for an
example requiring a Pairwise \Emph{Uncorrlelated} Sampling Theorem.  But I
don''t think this goes anywhere. }

\section{Fluctuations in an Unbiased Walk}

Let's consider the probability that the game ends within $k$ flips.  This
number is awkward to calculate explicitly, but we will be able to estimate
it using our methods for estimating expected deviation from the mean.

Let $C_k$ be the gamblers capital after $k$ flips.  That is,
\[
C_k \eqdef n + \sum_{i=1}^k G_i.
\]
In the unbiased case, the expected win on one flip is zero, so since $C_k$
is the sum of variables which have expectation 0, it follows that
$\expect{C_k} = 0$.  What about $\variance{C_k}$?  We will prove that
\begin{equation}\label{sumvarg}
\variance{C_k} = \sum_{i=1}^k \variance{G_i}.
\end{equation}

Note that for $i \neq j$, $G_i$ and $G_j$ are not independent, and so we
cannot appeal to pairwise independent additivity of variance to
prove~(\ref{sumvarg}).  For example, if $G_i = 0$, then the game has
stopped before the $i$th flip, so if $j > i$, then $G_j = 0$.  On the
other hand, the probability that $G_j = 0$ is less than one, because there
is some positive probability that the game will continue for more than $j$
flips (except for the degenerate case when $n=1 and T=2$).  That is,
\[
\prcond{G_j = 0}{G_i = 0} = 1 > \pr{G_j = 0},
\]
confirming nonindependence.

However, inspection of the proof of pairwise independent additivity of
variance shows that it didn't really require pairwise independence!  The
only property of the variables being added is that they be pairwise
\emph{uncorrelated}:

\begin{definition*}
Random variables $R$ and $S$ are \emph{uncorrelated} iff
\begin{equation}\label{uncor}
\expect{RS} = \expect{R}\expect{S}.
\end{equation}
\end{definition*}

\begin{lemma}\label{Guncor}
For $i \neq j$, $G_i$ and $G_j$ are uncorrelated.
\end{lemma}
\fi

\section{Quit While You Are Ahead}

Suppose that the gambler never quits while he is ahead.  That is, he
starts with $n>0$ dollars, ignores any goal $T$, but plays until he is
flat broke.  Then it turns out that if the game is not favorable, \ie $p
\leq 1/2$, the gambler is sure to go broke.  In particular, he is even
sure to go broke in a ``fair'' game with $p = 1/2$.
\footnote{If the game is favorable to the gambler, \ie $p>1/2$, then we
could show that there is a positive probability that the gambler will play
forever, but we won't examine this case in these Notes.}
\begin{lemma}\label{go broke}
If the gambler starts with one or more dollars and plays a fair game until
he is broke, then he will go broke with probability 1.
\end{lemma}

\begin{proof}
If the gambler has initial capital $n$ and goes broke in a game without
reaching a goal $T$, then he would also go broke if he were playing and
ignored the goal.  So the probability that he will lose if he keeps
playing without stopping at any goal $T$ must be at least as large as the
probability that he loses when he has a goal $T>n$.

But we know that in a fair game, the probability that he loses is $1 -
n/T$.  This number can be made arbitrarily close to 1 by choosing a
sufficiently large value of $T$.  Hence, the probability of his losing
while playing without any goal has a lower bound arbitrarily close to 1,
which means it must in fact be 1.
\end{proof}

So even if the gambler starts with a million dollars and plays a perfectly
fair game, he will eventually lose it all with probability 1.  In fact, if
the game is unfavorable, then Theorem~\ref{ExQthm} and
Corollary~\ref{biaswincor} imply that his expected time to go broke is
essentially proportional to his initial capital, \ie $\Theta(n)$.

But there is good news: if the game is fair, he can ``expect'' to play for
a very long time before going broke; in fact, he can expect to play
forever!

\begin{lemma}\label{play forever}
If the gambler starts with one or more dollars and plays a fair game until
he goes broke, then his expected number of plays is infinite.
\end{lemma}

\begin{proof}
Consider the gambler's ruin game where the gambler starts with initial
capital $n$, and let $u_n$ be the expected number of bets for
the \emph{unbounded} game to end.  Also, choose any $T \geq n$, and as
above, let $e_n$ be the expected number of bets for the game to end when
the gambler's goal is $T$.

The unbounded game will have a larger expected number of bets compared to
the bounded game because, in addition to the possibility that the gambler
goes broke, in the bounded game there is also the possibility that the
game will end when the gambler reaches his goal, $T$.  That is,
\[
u_n \geq e_n.
\]
So by~(\ref{Tn}), 
\[
u_n \geq n(T-n).
\]
But $n \geq 1$, and $T$ can be any number greater than or equal to $n$, so
this lower bound on $u_n$ can be arbitrarily large.  This implies that
$u_n$ must be infinite.

Now by Lemma~\ref{go broke}, with probability 1, the unbounded game ends
when the gambler goes broke.  So the expected time for the unbounded game
to \emph{end} is the \emph{same} as the expected time for the gambler to
\emph{go broke}.  Therefore, the expected time to go broke is infinite.
\end{proof}

In particular, even if the gambler starts with just one dollar, his
expected number of plays before going broke is infinite!  Of course, this
does not mean that it is likely he will play for long.  For example, there
is a 50\% chance he will lose the very first bet and go broke right away.

Lemma~\ref{play forever} says that the gambler can ``expect'' to play
forever, while Lemma~\ref{go broke} says that with probability 1 he will
go broke.  These Lemmas sound contradictory, but our analysis showed that
they are not.

\section{Infinite Expectation}

So what are we to make of such a random variable with infinite
expectation?  For example, suppose we repeated the experiment of having
the gambler make fair bets with initial stake one dollar until he went
broke, and we kept a record of the average number of bets per experiment.
Our theorems about deviation from the mean only apply to random variables
with finite expectation, so they don't seem relevant to this situation.
But in fact they are.

For example, let $Q$ be the number of bets required for the gambler to go
broke in a fair game starting with one dollar.  We could use some of our
combinatorial techniques to show that
\begin{equation}\label{Qm}
\pr{Q=m} = \Theta(m^{-3/2}).
\end{equation}
This implies that
\[
\expect{Q} = \Theta\paren{\sum_{m=1}^\infty m\cdot m^{-3/2}} = 
\Theta\paren{\sum_{m=1}^\infty m^{-1/2}}.
\]
We know this last series is divergent, so we have another proof that $Q$
has infinite expectation.

But suppose we let $R \eqdef Q^{1/5}$.  Then the estimate~(\ref{Qm}) also
lets us conclude that
\[
\expect{R}  =  \Theta\paren{\sum_{m=1}^\infty m^{-13/10}}
\]
and
\[
\expect{R^2}  = \Theta\paren{\sum_{m=1}^\infty m^{-11/10}}.
\]
Since both these series are convergent, we can conclude that
$\variance{R}$ is finite.  Now our theorems about deviation can be applied
to tell us that the average \emph{fifth root} of the number of bets to go
broke is very likely to converge to a finite expected value.

\iffalse
%THIS WAS BASED ON A CONFUSED UNDERSTANDING OF Feller's REMARKS ON rth
%RETURNS.  AS IT STANDS, IT'S NONSENSE.

We could also use our techniques to estimate $\pr{Q_k = m}$, where $Q_k$
is the sum of $k$ independent gambler's ruin games starting with one
dollar.  So $\expect{Q_k/k} = \expect{Q}$ remains infinite, but
using~(\ref{Qm}), we could also show that $\expect{Q_k/k^2}$ is finite.
Our bounds on deviation from a finite mean now tell us that when the
gambler plays $k$ games, his average time to go broke will very likely
grow proportionally to $k$.
\fi

We won't go further into the details, but the moral of this discussion is
that our results about deviation from a finite mean can still be applied
to natural models like random walks where variables with infinite
expectation may play an important role.


\section{The Chernoff Bound}

The Chernoff bound applies to a sum of independent random variables that
satisfy conditions that lie between the conditions needed for the Pairwise
Independent Sampling Theorem of
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln11-12.pdf}{Notes
11-12} and conditions that imply the sum has a binomial distribution.
When it applies, the Chernoff bound gives nearly as good a bound as our
estimates for the binomial distribution in
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln11-12.pdf}{Notes
11-12}.  In particular, the Chernoff bound is exponentially smaller than
bound given by the Pairwise Independent Sampling Theorem.

The Chernoff bound plays a larger role in Computer Science than the more
traditional Central Limit Theorem (which will be briefly considered in
later Notes).  Both theorems give bounds on deviation from the mean, but
the Chernoff bound gives better estimates on the probability of deviating
from the mean by many standard deviations.

For example, suppose we are designing a system whose components may
occasionally fail, but we want the system as a whole to be very reliable.
The Chernoff bound can provide good estimates for the number of failures
the system should be designed to survive in order to meet the specified
high level of reliability.  That is, the system will only fail only if a
the number of component failures exceeds a designated threshold, but the
Chernoff bound tells us that this threshold is very unlikely to be
exceeded.

Another typical application is in designing probabilistic algorithms.  We
expect that such algorithms might give a wrong answer, but will do so only
if the number of mistaken probabilistic ``guesses'' it makes is much
larger than should be expected.  The likelihood of this unusually large
number of mistakes can often be estimated well using the Chernoff bound.

\section{The Probability of at Least One Event}\label{sc: one}

%\subsection{General Bounds on the Probability}

Let $A_1, A_2, \dots, A_n$ be a sequence of events, and let $T$ be the
number of these events that occur.  What is $\pr{T \geq 1}$, the
probability that at least $1$ event occurs?  Note that the event $[T \geq
1]$ is precisely the same as the event $\lgunion A_i$.  In
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln10.pdf}{Notes
10}, \S 5.2, and in
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/miscellaneous/cp10W.pdf}{Class
Problems 10W}, Problem 1, we verified the general bounds
\begin{equation}\label{Tgeq1}
\max_{1 \leq i \leq n} \pr{A_i} \leq \lgunion A_i \leq \sum_{i=1}^n \pr{A_i},
\end{equation}
and described situations in which each of these bounds were achieved.  So
in general, we cannot improve the bounds given in ~(\ref{Tgeq1}).

\iffalse

\begin{proposition}\label{fact:union}
Let $A_1, A_2, \dots, A_N$ be events over the same sample space, and let
the random variable $T$ be the number of these events that occur.  Then
\[
    \pr{T \geq 1}  \leq  \sum_{i=1}^n \pr{A_i}.
\]
\end{proposition}
In words, the probability that at least one of the events occurs is at
most the sum of the event probabilities.  Although
Proposition~\ref{fact:union} is obvious, and in a sense trivial, it can be
useful and so is well worth remembering.


Proposition~\ref{fact:union} is weak for events with sizable probabilities.
For example, if we flip a fair coin three times, then we can conclude that
the probability of flipping heads at least once is at most $1/2 + 1/2 +
1/2 = 3/2$, which is not front-page news.  But if the events $A_i$ all
have relatively low probability, then Proposition~\ref{fact:union} can be
useful.

For example, suppose that we want to compute the probability of a meltdown
at MIT's nuclear reactor on Albany Street.  First, we enumerate all events
$A_i$ that could lead to a meltdown, \eg operator error, earthquake,
terrorist attack, meteor strike, \etc\ Next, we determine, as best we can,
the probability of each type of catastrophe alone.
Proposition~\ref{fact:union} allows us to ignore tricky independence
issues---such as whether the terrorist team might be kept from the reactor
by an earthquake---and conclude that the probability of a meltdown is at
most the sum of these event probabilities.

In addition to this general \emph{upper} bound on $\pr{T \geq 1}$, there
is also a trivial \emph{lower} bound which can occasionally be useful:


\begin{proposition}
Let $A_1, A_2, \dots, A_N$ be events over the same sample space, and let
the random variable $T$ be the number of these events that occur.  Then
\[
\pr{T \geq 1} \geq \max_{1 \leq i \leq n} \pr{A_i}.
\]
\end{proposition}
In words, the probability that at least one of the events occurs is at
least as large as the probability that any particular one of them occurs.
This follows immediately from the fact each event, $A_i$, is subset of the
event $[T \geq 1]$.

Of course, if the events are known to be independent, then a lower bound
close to one holds, as we show next.

\subsection{The Probability of At Least One Independent Event}
\fi


On the other hand, if the events $A_i$ are mutually independent, we can
be much more precise about the probability that one or more of them occur.
In fact, we will show that if we expect several events to occur, then
almost certainly at least one event will occur.  Another way to say this
is that if we expect more than one event to occur, then the probability
that no event occurs is practically zero.  Specifically, we have:

\begin{theorem}\label{th:none}

\hyperdef{ln13}{none}{Let} $A_1, A_2, \dots A_n$ be independent events,
and let $T$ be the number of these events that occur.  The probability
that none of the events occur is at most $e^{-\expect{T}}$.
\end{theorem}

Interestingly, Theorem~\ref{th:none} does not depend on $n$, the number of
events.  It gives the same bound whether there are 100 events each with
probability 0.1 or 1000 events each with probability 0.01.  In both cases,
the expected number of events is 10, and so the probability of no event
occurring is at most $e^{-10}$ or about 1 in 22,000.  Note that the actual
probabilities are somewhat different in these two cases, indicating that
the given bound is not always tight.

Theorem~\ref{th:none} can be interpreted as a sort of ``Murphy's Law'': if
we expect some things to go wrong, then something probably will.  For
example, suppose that we are building a microprocessor, and the
fabrication process is such that each transistor is faulty mutually
independently with a probability of one in a million.  This sounds good.
However, microprocessors now contain about ten million transistors, so the
expected number of faulty transistors is 10 per chip.  Since we expect
some things to go wrong, something probably will.  In fact,
Theorem~\ref{th:none} implies that the probability of a defect-free a chip
is less than 1 in 22,000!

In proving Theorem~\ref{th:none}, we first note that
\begin{equation}\label{Tsum}
T = T_1 + T_2 + \dots + T_n,
\end{equation}
where $T_i$ is the indicator variable for the event $A_i$.  We also use
the fact that
\begin{equation}\label{1+xe}
1 + x \leq e^x
\end{equation}
for all $x$, which follows from the Taylor expansion
\[
e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots.
\]

\begin{proof}
\begin{align*}
\pr{T = 0}
  & = \bar{A_1 \union A_2 \union \cdots \union A_n} & \text{(def. of $T$)}\\
  & =  \pr{\bar{A_1} \cap \bar{A_2} \cap \dots \cap \bar{A_n}} &
          \text{(De Morgan's law)}\\
  & =  \prod_{i=1}^n \pr{\bar{A_i}} & \text{(mutual independence of $A_i$'s)}\\
  & =  \prod_{i=1}^n 1 - \pr{A_i} & \text{(complement rule)}\\
  & \leq  \prod_{i=1}^n e^{-\pr{A_i}} & \text{(by~(\ref{1+xe}))}\\
  & =  e^{-\sum_{i=1}^n \pr{A_i}} & \text{(exponent algebra)}\\
  & =  e^{-\sum_{i=1}^n \expect{T_i}} & \text{(expectation of indicator variable)}\\
  & =  e^{-\expect{T}}. & \text{((\ref{Tsum}) \& linearity of expectation)}
\end{align*}
\end{proof}

Two special cases of Theorem~\ref{th:none} are worth singling out because
they come up all the time.
\begin{corollary}\label{1/ktrials}
Suppose an event has probability $1/m$.  Then the probability that the
event will occur at least once in $m$ independent trials is at least 
approximately $1- 1/e \approx 63\%$.  There is at least 50\% chance the 
event will occur in $n = m \log 2 \approx 0.69m$ trials.
\end{corollary}

\solution{
In this case, $\pr{A_i}=1/m$ for $1\leq i \leq n$ and
\[
\expect{\text{\# occurrences}} = n \frac{1}{m} = \frac{n}{m}.
\]
So by Theorem~\ref{th:none},
\[
\pr{\text{no occurrence}} \leq e^{-(n/m)},
\]
and therefore
\begin{equation}\label{1-enm}
\pr{\text{at least one occurrence}} \geq 1 - e^{-(n/m)}.
\end{equation}
In fact, it follows from by~(\ref{1+xesim}), that the $\geq$
in~(\ref{1-enm}) is an approximate equality.

So if the number, $n$ of trials is $m$, we have
\[
\pr{\text{at least one occurrence}} \approx 1- e^{-(m/m)} = 1-\frac{1}{e}.
\]

If we want
\[
1 - e^{-(n/m)} \approx \pr{\text{at least one occurrence}} \approx
\frac{1}{2},
\]
then we need
\[
e^{-(n/m)} \approx \frac{1}{2},
\]
so taking log's we conclude
\[
n \approx m\log 2.
\]
}


\section{Chernoff Bounds}

\subsection{Probability of at least \emph{k} events}

Now we consider the more general question than the probability that one
event occurs, namely, the probability that $k$ events occur, still
assuming mutual independence of the events $A_i$.  In other words, what is
$\pr{T \geq k}$, given that the events $A_i$ are mutually independent?

For example, suppose we want to know the probability that at least $k$
heads come up in $N$ tosses of a coin.  Here $A_i$ is the event that the
coin is heads on the $i$th toss, $T$ is the total number of heads, and
$\pr{T \geq k}$ is the probability that at least $k$ heads come up.

As a second example, suppose that we want the probability of a student
answering at least $k$ questions correctly on an exam with $N$
questions.  In this case, $A_i$ is the event that the student answers
the $i$th question correctly, $T$ is the total number of questions
answered correctly, and $\pr{T \geq k}$ is the probability that the
student answers at least $k$ questions correctly.

There is an important difference between these two examples.  In the first
example, all events $A_i$ have equal probability, \ie the coin is as
likely to come up heads on one flip as on another.  So $T$ has a binomial
distribution whose tail bounds we have already characterized in
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln11-12.pdf}{Notes
11-12}.

In the second example, however, some exam questions might be more
difficult than others.  If Question 1 is easier than Question 2, then the
probability of event $A_1$ is greater than the probability of event $A_2$.
In this section we develop a method to handle this more general situation
in which the events $A_i$ may have different probabilities.

We will prove that the number of events that occur is almost never
much greater than the expectation.  This result is called the Chernoff
Bound.  For example, if we toss $N$ coins, the expected number of
heads is $N/2$ heads.  The Chernoff Bound implies that for
sufficiently large $N$, the number of heads is almost always not much
greater than $N/2$.

A nice feature of the Chernoff Bound is that we do not even need to
know the probability of each event $A_i$ or even the number of events
$N$; rather, we need only the expected number of events that occur and
the fact that the events are mutually independent.

\subsection{Statement of the Bound}

We state Chernoff's Theorem in terms of Bernoulli variables instead of
events.  However, we can regard $T_i$ as an indicator for the event $A_i$.
\begin{theorem}[Chernoff Bound] \label{Chbnd}
Let $T_1, T_2, \dots, T_n$ be mutually independent Bernoulli variables,
and let $T = T_1 + T_2 + \cdots + T_n$.  Then for all $c \geq 1$, we have
\begin{equation}\label{Chbndeq}
  \pr{T \geq c \expect{T}} \leq e^{- (c\ln c -c + 1) \expect{T}}.
\end{equation}
\end{theorem}

\iffalse
(A similar bound holds for $\pr{T \leq c \expect{T}}$, where $c < 1$; we
omit this here.)  See Motwani & Raghavan text.
\fi

The formula for the exponent in the bound is a little awkward.  The
situation is simpler when $c = e = 2.718\dots$.  In this case, $c\ln c - c
+ 1 = e \ln e - e + 1 = e\cdot 1 - e +1 =1$, so we have as an immediate
corollary of Theorem~\ref{Chbnd}:
\begin{corollary}\label{cor:ebound}
Let $T_1, T_2, \dots, T_n$ be mutually independent Bernoulli variables,
and let $T = T_1 + T_2 + \cdots + T_n$.  Then
\[
\pr{T \geq e \expect{T}} \leq e^{- \expect{T}}.
\]
\end{corollary}
We will prove the Chernoff Bound shortly.  First, let's see an example of
how it is used.

\subsection{Example: Pick 4}

There is a lottery game called Pick 4.  In this game, each player
picks 4 digits, defining a number in the range 0 to 9999.  A winning
number is drawn each week.  The players who picked the winning number
win some cash.  A million people play the lottery, so the expected
number of winners each week is
\[
\frac{1}{10,000} \cdot 1,000,000 = 100.
\]
However, on some lucky day thousands of people might all pick the winning
number, costing the lottery operators loads of money.  How likely is this?

Assume that all players pick numbers uniformly and mutually
independently.  Let $T_i$ be an indicator variable for the event that
the $i$th player picks the winning number.  Let $T = T_1 + T_2 +
\cdots + T_n$.  Then $T$ is the total number of players that pick the
winning number.  As noted above, an average of 100 people win each
week, so $\expect{T} = 100$.  We can use Corollary~\ref{cor:ebound} to
bound the probability that number of winners is greater than 272 as
follows:
\begin{displaymath}
  \pr{T \geq 272} \leq \pr{T \geq e\expect{T}} \leq e^{- Ex(T)} = e^{-100}.
\end{displaymath}
The probability of 272 or more people winning is absurdly small!  It
appears that the lottery operators should not worry that ten thousand
people will pick correctly one day!

But there is a catch.  The assumption that people choose Pick 4
numbers uniformly and mutually independently is empirically false;
people choose certain ``favorite'' numbers far more frequently than
others.

Chernoff used this fact in devising a scheme to actually make money on
the lottery.  In this case, a fraction of all money taken in by the
lottery was divided up equally among the winners.  A bad strategy
would be to pick a popular number.  Then, even if you pick the winning
number, you must share the cash with many other players.  A better
strategy is to pick a lot of unpopular numbers.  You are just as
likely to win with an unpopular number, but will not have to share
with anyone.  Chernoff found that peoples' picks were so highly
correlated that he could actually turn a 7\% profit by picking
unpopular numbers!

\subsection{The constant in the exponent}

For general $c$, what can we say about the factor $c\ln c -c +1$ in the
exponent?  First, note that when $c=1$, the exponent factor equals $1
\cdot 0 - 1 + 1 = 0$.  This means that the Chernoff bound cannot say
anything useful about the probability simply of exceeding the mean.
However, the exponent factor increases with $c$ for $c > 1$.  This follows
because its derivative respect to $c$ is positive:
\[
\frac{d(c\ln c - c + 1)}{dc} = (\frac{c}{c} + \ln c) - 1 = \ln c > 0
\]
when $c>1$.  In particular, for any $c>1$, the factor $(c\ln c -c + 1)$ in
the exponent is positive.

Let's consider the case of $c$ close to 1, say $c=1+\epsilon$.  Then a
Taylor expansion gives:
\begin{align*}
c\ln c - c + 1  &= (1+ \epsilon) \ln(1+\epsilon) - (1+\epsilon) + 1\\
  &= (1+ \epsilon) (\epsilon- \frac{\epsilon^2}{2}+ \frac{\epsilon^3}{3}-
  \frac{\epsilon^4}{4} + \cdots) - \epsilon\\
  &= (\epsilon - \frac{\epsilon^2}{2}+ \frac{\epsilon^3}{3}-
  \frac{\epsilon^4}{4} + \cdots) + (\epsilon^2 - \frac{\epsilon^3}{2}+ \frac{\epsilon^4}{3}-
  \frac{\epsilon^5}{4} + \cdots) - \epsilon\\
  & = \frac{\epsilon^2}{2} - \frac{\epsilon^3}{2 \cdot 3} + 
  \frac{\epsilon^4}{3 \cdot 4} -   \frac{\epsilon^5}{4 \cdot 5} +\cdots.
\end{align*}
In particular, for very small $\epsilon$, we have $c\ln c - c + 1 \approx
\epsilon^2/2$.  In fact one can prove the following:
\begin{lemma}
  For any $0< \epsilon < 1$, 
  $\pr{T \geq (1+\epsilon) \expect{T}} < e^{-\epsilon^2 \expect{T}/3}$.
\end{lemma}
In other words, the probability of deviation above the mean by a fraction
$\epsilon$ decays \emph{exponentially} in the expected value, for any
$\epsilon > 0$.

Another useful observation is that the Chernoff bound starts to ``kick
in'' when $\epsilon \approx 1/\sqrt{\expect{T}}$.  In other words, the
typical deviation of our random variable is going to be about the
square root of its expectation.  This is in line with our analysis of
binomial random variables: the number of heads in $n$ unbiased coin
flips has expectation $n/2$, but has standard deviation $\sqrt{n}/2$,
or roughly the square root of the expectation. 

\subsection{Proof of the Bound}

The Chernoff Bound uses an ingenious trick along the lines of the way we
derived Chebyshev's Bounds:
\begin{equation}\label{TcT}
  \pr{T \geq c \expect{T}} = \pr{c^T \geq c^{c \expect{T}}}
  \leq \frac{\expect{c^T}}{c^{c \expect{T}}}
\end{equation}
The first step may be a shocker; we exponentiate both sides of the
inequality in the probability by $c$.  Since the new inequality describes
the same event as the old, the probabilities are the same.  The second
step uses Markov's Theorem.

Recall that Markov's Theorem sometimes gives weak bounds and sometimes
gives tight bounds.  The motivation for the first step is to alter the
distribution of the random variable $T$ to hit the ``sweet spot'' of
Markov's Theorem.  That is, Markov's Theorem gives a tighter bound on
the random variable $c^T$ than on the original variable $T$.  We used
the same trick in Chebyshev's theorem: we looked at the expectation of
$T^2$ instead of that of $T$, because that gave us more powerful
results.

All that remains is to evaluate $\expect{c^T}$.  To do this we need a Lemma:
\begin{lemma}\label{RSfg}
If $R$ and $S$ are independent random variables, and $f$ and
$g$ are \emph{any} real-valued functions on the reals, then $f(R)$ and
$g(S)$ are independent random variables.
\end{lemma}
We leave the proof of Lemma~\ref{RSfg} as a routine exercise.

We begin by calculating $\expect{c^{T_i}}$:
\begin{align}
\expect{c^{T_i}}
        & \eqdef  c^1 \pr{T_i = 1} + c^0 \pr{T_i = 0}\notag\\
        & =    c \pr{T_i = 1} + (1 - \pr{T_i = 1}) & \text{(complement
        rule, since $T_i = 0$ iff $T_i \neq 1$)} \notag\\
        & =    1 + (c - 1) \pr{T_i = 1} \notag\\
        & \leq  e^{(c-1) \pr{T_i = 1}} & (1+x\leq e^x)\notag\\
        & =  e^{(c-1) \expect{T_i}} & \text{(expectation of indicator variable)}.\label{boundEcT}
\end{align}

So now we have
\begin{align}
\expect{c^T}
        & =    \expect{c^{T_1 + T_2 + \cdots + T_n}} & \text{(def of $T$)}\notag\\
        & =    \expect{c^{T_1} \cdot c^{T_2} \cdots c^{T_n}}\notag\\
        & =    \expect{c^{T_1}} \cdot \expect{c^{T_2}} \cdots \expect{c^{T_n}}
            & \text{(independence of $T_i$'s and Lemma~\ref{RSfg})}\notag\\
%        & =   \prod_{i=1}^n \expect{c^{T_i}}\label{cT3}\\
%        & \leq  \prod_{i=1}^n e^{(c-1) \expect{T_i}} & \text{(by~(\ref{boundEcT}))}\notag\\
   & \leq  e^{(c-1) \expect{T_1}} \cdot e^{(c-1) \expect{T_2}} \cdots e^{(c-1) \expect{T_n}}
            & \text{(by~(\ref{boundEcT}))}\notag\\
        & =    e^{(c-1) \expect{T_1} + (c-1) \expect{T_2} + \cdots + (c-1) \expect{T_n}} \notag\\
        & =    e^{(c-1) \expect{T_1 + \cdots + T_n}} & \text{(linearity of expectation)}\notag\\
        & =    e^{(c-1) \expect{T}} & \text{(def of $T$)}\label{ec-1T}.
\end{align}

Now we can substitute into the Markov inequality we started with to
complete the proof of the Chernoff bound~(\ref{Chbndeq}):
\begin{align*}
\pr{T \geq c \expect{T}} & \leq \frac{\expect{c^T}}{c^{c \expect{T}}}
     & \text{(by~(\ref{TcT}))}\\
 & \leq \frac{e^{(c-1) \expect{T}}}{c^{c \expect{T}}}
     & \text{(by~(\ref{ec-1T}))}\\
 & =  \frac{e^{(c-1) \expect{T}}}{(e^{\ln c})^{c \expect{T}}}\\
 & =    e^{(c-1) \expect{T} - c \ln c \expect{T}}\\
 & =    e^{-(c\ln c - c + 1) \expect{T}}.
\end{align*}


\subsection{Example:  A Phone Network Problem}

Suppose that there is a phone network that handles a billion calls a
day.  Some of these call are routed through a certain switch.  The
exact number of calls passing through this switch is somewhat random
and fluctuates over time, but on average the switch handles a million
calls a day.

Our problem is to set the capacity of the switch; that is, we must
determine the number of calls that a switch is able to handle in a
day.  If we make the capacity too small, then some phone calls will
not go through.  On the other hand, if we make the capacity too large,
then we are wasting money.  Of course, we cannot rule out a freak
situation in which a huge number of calls are all coincidentally
routed through the same switch, thus overloading it.  However, we would like to guarantee that a switch is rarely
overloaded.

Assume that each call has some probability of passing through a
particular switch.  In particular, let $T_i$ be an indicator variable
for the event that the $i$th call passes through the switch.  That
is, $T_i = 1$ if the call is routed through the switch, and $T_i = 0$
if the call does not pass through the switch.  Then the total call
load on the switch is $T = T_1 + T_2 + \cdots + T_n$.  We do not know
the exact probability that the switch handles the $i$th call, but we
are given that the switch handles an average of a million calls a day;
that is, $\expect{T} = 1,000,000$.

We will make the crucial assumption that the random variables $T_i$
are mutually independent; that is, calls do or do not pass through the
switch mutually independently.

\subsubsection{How to Build One Switch}

We can now compute the probability that the load on a switch
fluctuates upwards by 1\% due to the randomness of calling patterns.
Substituting $c = 1.01$ and $\expect{T} = 1,000,000$ into the Chernoff
Bound gives:
\begin{eqnarray*}
\pr{\text{particular switch overloaded}}
        & = & \pr{T \geq 1.01 \cdot 1,000,000} \\
&\leq&  e^{-(1.01 \ln 1.01 -1.01 + 1) \cdot 1,000,000}\\
& < &   e^{-1.01 (0.00004934) \cdot 1,000,000}\\
& < &   2.3 \cdot 10^{-22}.
\end{eqnarray*}
The probability that the load on the switch ever rises by even 1\% is
unbelievably small!  (A June blizzard during an earthquake in Cambridge is
far more likely.)  If we build the switch with capacity only 1\% above the
average load, then the switch will (almost) never be overloaded.

The strength of this result relies on the huge expected number of
calls.  For example, suppose that the average number of calls through
the switch were 100 per day instead of 1,000,000.  Then every million
in the above calculation would be replaced by a hundred; no other
numbers change.  The final probability of overloading the switch would
then be bounded above not by $2.3 \cdot 10^{-22}$, but by $0.995$!  If
the switch handles only 100 calls on an average day, then the call
load can very often fluctuate upward by 1\% to 101 or more.

\subsubsection{How to Build the Network}

We now know that building 1\% excess capacity into a switch ensures
that it is effectively never overloaded.  The next problem is to
guarantee that no switch in the entire network is overloaded.  Suppose
that are 1000 switches, and every switch handles an average of a
million calls a day.

Previously, we saw that the probability that some event occurs is at
most the sum of the event probabilities.  In particular, the
probability that some switch is overloaded is at most the sum of the
probabilities that each of the 1000 switches is overloaded.
Therefore, we have:
\begin{displaymath}
  \pr{\text{some switch overloaded}}
  \leq 1000 \cdot \pr{\text{particular switch overloaded}}
  < 2.3 \cdot 10^{-19}.
\end{displaymath}
This means that building 1\% excess capacity into every switch is
sufficient to ensure that no switch is ever overloaded.

The above results are of limited practical value, because calls typically
do not pass through a switch mutually independently.  For example, after
an earthquake on Albany Street, everyone would call through the eastern
Cambridge switchboard to check on friends and family.  Furthermore, there
are many more phone calls on certain dates like Mother's Day.  On such
occasions, 1\% excess capacity is insufficient.

%\section{Chernoff bounds and binomial tails}

\section{A Generalized Chernoff Bound}

\iffalse

\subsection{Deviation of an Unbiased Binomial Distribution}

The Chernoff bound also applies to a sum of independent events with the
same probability, $1/2$.  This of course just means that the number of
events has an unbiased binomial distribution.  Although we already have
estimates on the tail of the binomial distribution in
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}{Notes
12}, it's instructive to apply the Chernoff-bound approach to this
familiar example.

\begin{theorem}\label{binom dev}
If $R$ has an unbiased binomial distribution, then for $c\geq 1$,
\[
\pr{R-\expect{R} \geq c\sigma_R} \leq e^{-c^2/2}.
\]
\end{theorem}

\textbf{From the Chernoff bound, we know that this probability is at most
$e^{-c \ln c}$.  The new bound, $e^{-c^2/2}$, is noticably smaller as $c$
increases.  CHECK THIS.}

For example, suppose that the 6.042 final consists entirely of
true/false questions\footnote{Ha!  Fat chance.} and students guess
answers uniformly and mutually independently.  A student's score on
each question is a uniform Bernoulli variable (0 or 1).  A student's
exam score is a sum of these Bernoulli variables, and so is a random
variable with an unbiased binomial distribution.

\textbf{REVISE TO USE CHERNOFF NOT CHEBY:} Given these assumptions, what
is the probability that a student scores two standard deviations above the
mean?  By Chebyshev's Theorem the probability is at most 1 in 4.  However,
we can get a better bound using the fact above.
\begin{displaymath}
  \pr{R - \expect{R} \geq 2 \sigma_R} < e^{-2^2/2} = e^{-2}
\end{displaymath}
The probability that a student scores 2 standard deviations above the
mean on this exam is less than 1 in 7.

The difference is more striking if we look at greater deviations.  For
example, the probability that a student scores 6 standard deviations above
the mean is at most $e^{-6^2/2} = e^{-18}$, which is less than one in 65
million.  The corresponding bound from Chebyshev's Theorem is
$1/37$.

\begin{proof}
Let $X_i \eqdef 2R_i - 1$ and $X \eqdef \sum_{i=1}^n X_i$.  So $X=2R-n$.

Now
\begin{eqnarray*} 
\pr{R-\expect{R} \geq c \sigma_R} &=& \pr{R-\frac{n}{2} \geq c \frac{\sqrt{n}}{2}}\\
  &=& \pr{2R-n \geq c \sqrt{n}}\\
  &=& \pr{X \geq c \sqrt{n}}.
\end{eqnarray*}
So we need only show that
\begin{equation}\label{Xcn}
\pr{X \geq c \sqrt{n}} \leq e^{-c^2/2}.
\end{equation}

But $X \geq c\sqrt{n}$ iff $e^{tX} \geq e^{tc\sqrt{n}}$
for every $t > 0$.  Applying Markov's inequality to $e^{tX}$, yields
\begin{equation}\label{etX}
\pr{e^{tX} \geq e^{tc\sqrt{n}}} \leq \frac{\expect{e^{tX}}}{e^{tc\sqrt{n}}}.
\end{equation}
Now
\begin{align}
\expect{e^{tX}} & = \expect{e^{t\sum_{i=1}^nX_i}} & \text{(def of $X$)}\notag\\
     & =  \expect{\prod_{i=1}^n e^{tX_i}} & \text{(exponent algebra)}\notag\\
     & =  [\expect{e^{tX_i}}]^n & \text{(mutual independence of $X_i$'s and Lemma~\ref{RSfg})}.\label{En}
\end{align}
Notice that from the Taylor expansions of $e^t$ and $e^{-t}$, we have
\[
\frac{e^t + e^{-t}}{2} \leq e^{t^2/2}.  
\]
Therefore
\begin{equation}\label{sinh}
\expect{e^{tX_i}} = \frac{e^t + e^{-t}}{2} \leq e^{t^2/2}.
\end{equation}
Combining~(\ref{sinh}) with~(\ref{En}) yields
\begin{equation}\label{et2}
\expect{e^{tX}} \leq (e^{t^2/2})^n.
\end{equation}

Finally, from~(\ref{et2}) and our initial Markov inequality~(\ref{etX}),
we conclude
\begin{equation}\label{etn}
\pr{X \geq c\sqrt{n}} \leq \frac{(e^{\frac{t^2}{2}})^n}{e^{tc\sqrt{n}}} = 
e^{\frac{t^2n}{2} - tc\sqrt{n}}.
\end{equation}
Since we can choose any positive $t$, we choose $t$ to minimize the
exponent in~(\ref{etn}).  A little calculus shows that the desired value
is $t = c/\sqrt{n}$.  Substituting this value of $t$ into~(\ref{etn}) and
simplifying yields~(\ref{Xcn}), as required.

\end{proof}

\subsection{Generalized Chernoff}  

The theorem from the previous section can be generalized as follows.  \fi

Chernoff's Theorem applies only to sums of Bernoulli (0-1-valued) random
variables.  It can, however, be extended to apply to sums of random
variables with considerably more arbitrary distributions.  We state one
such generalization in Theorem~\ref{GenCh} below.  We omit its proof,
noting only that the proof is similar to that of the Chernoff bound of
Theorem~\ref{Chbnd}.  The bound of Theorem~\ref{GenCh} is not quite as
good as the Chernoff bound, but it is more general in what it covers.

\begin{theorem}
Let $R_1,\ldots,R_n$ be independent random variables with
$0\leq R_i \leq 1$. Let $R=\sum_{i=1}^n R_i$.
Then 
\begin{equation}
\pr{R - \expect{R} \geq c\sqrt{n}} \leq e^{-c^2/2}.\label{GenCh}
\end{equation}
\end{theorem}

\begin{example} Load balancing. 

A set of $n$ jobs have to be scheduled on a set of $m$ equally fast
processing machines.  The length (processing time) of the $i$th job is
some number $L_i$ in the range $[0,1]$.  We would like to schedule the
jobs on the machines so that the loadtime on the machines is reasonably
balanced.  This means we would like the loadtime on every machine to be
not much more than the average loadtime $L \eqdef \sum_{i=1}^n L_i/m$ per
machine.  Finding an optimally balanced assignment is a notoriously
time-consuming task even when we know all the processing times.  But
commonly, successive jobs have to be assigned to machines without knowing
how long the later jobs will take, and in that case it is impossible to
guarantee a balanced load.

We will approach this problem of load balancing using the simplest random
strategy: we independently assign each job to a randomly selected machine,
with each machine equally likely to be selected.  It turns out that for
many job scheduling problems, this strategy is almost certain to do very
well, even though it does not even take into account the number of jobs
nor their processing times.

To see why the simple random strategy does well, notice that, since each
job has probability $1/m$ of being assigned to any given machine, the
expected loadtime on a machine is precisely $1/m$th of the total time
required by the jobs.  That is, the \emph{expected} loadtime per machine
is precisely the \emph{average} loadtime, $L$.  Now consider any machine,
$M$, and define $R_i$ to be the time $M$ spends processing the $i$th job.
That is, $R_i = L_i$ if the $i$th job gets assigned to machine $M$,
otherwise $R_i = 0$.  So the total loadtime on machine $M$ is
$\sum_{i=1}^n R_i$.  From the generalized Chernoff bound~(\ref{GenCh}), we
conclude
\[
\pr{\mbox{(loadtime on machine $M$)} - L \geq c\sqrt{n}} \leq e^{-c^2/2}.
\]
Now by Boole's inequality,
\begin{eqnarray*}
\lefteqn{\pr{\mbox{the loadtime on some machine is } \geq L +  c\sqrt{n}}}\\
    &\leq &
 \sum_{k=1}^m \pr{\mbox{(loadtime on machine $k$)} \geq L + c\sqrt{n}} \\
&\leq & m e^{-c^2/2}.
\end{eqnarray*}

If we choose $c = \sqrt{2\ln m}+6$, say, so that $c^2/2 \geq \ln m + 18$, then
\begin{eqnarray*}
\lefteqn{\pr{\mbox{(loadtime on each machine)} \leq L + c \sqrt{n}}}\\
 & \geq & 1 - m e^{-\ln m -18}\\
 & = & 1 - e^{\ln m} e^{-\ln m -18}\\
 & = & 1 - e^{-18} = 0.99999998\dots.
\end{eqnarray*}
Hence, we can be 99.999998\% sure that every machine will have load at
most $L+(\sqrt{2\ln m }+6)\sqrt{n}$.  For many values of $n$ and $m$ this
is comes very close to balancing the loads on all the machines.  For
example, if $m=10$ machines, $n=5000$ jobs, and average load length
$L=300$ per machine, the maximum load on any machine will almost surely
not exceed 332.  (In fact it is likely to be even less---we have been
fairly crude in our bounds.)

\end{example}


\section{Review of Markov, Chebyshev, Chernoff and Binomial bounds}

Let us review the methods we have for bounding deviation from the mean via
the following example.  Assume that \IQ is made up of thinkatons; each
thinkaton fires independently with a $10\%$ chance. We have 1000
thinkatons in all, and \IQ is the number of thinkatons that fire.  What is
the probability of having Marilyn's IQ of 228?

So the \IQ is a Binomial distribution with $n=1000, p= 0.1$.  Hence,
$\expect{\text{I.Q.}} = 100, \sigma_{\text{I.Q.}} =\sqrt{0.09 \times 1000}
= 9.48$.

An \IQ of 228 is $128/9.48 > 13.5$ standard deviations away.

Let us compare the methods we have for bounding the probability of this \IQ.

\begin{enumerate}
\item Markov: 
\[
\pr{\text{I.Q.} \geq 228} \leq \frac{100}{228} < 0.44
\]

\item Chebyshev:
\[
\pr{\text{I.Q. } - 100 \geq 128 } \leq \frac{1}{13.5^2+1} < \frac{1}{183}
\]

\item Chernoff: 
\[
\pr{\text{I.Q. } \geq 2.28 \times 100} \leq e^{-(2.28\ln 2.28 - 2.28 +1)100} \leq e^{-59.9}
\]

\item Binomial tails:
\[
\pr{\text{I.Q. } \geq 228} = \pr{1000-\text{I.Q. } \leq 772} =
F_{0.9,1000}(772) \leq e^{-72.5}
\]
Here we used the formula for the binomial tail from
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln11-12.pdf}{Notes
11-12} with $p = 0.9, n = 1000, \alpha = 0.772$.

\end{enumerate}

Note that the more we know about the distribution the better are the 
bounds we can obtain on the probability.


\end{document}


\iffalse
Notice that the random variables $S_n/n$
and $S_n$ have the same normalized density function:
\begin{eqnarray*}
S^*_n  & \eqdef & \frac{S_n - \mu_{S_n}}{\sigma_{S_n}}\\
      & = & \frac{S_n - n\mu}{\sigma\sqrt{n}}\\
      & = & \frac{S_n/n - \mu}{\sigma/\sqrt{n}}\\
      & = & \frac{S_n/n - \mu_{S_n/n}}{\sigma_{S_n/n}}\\
      & = & (S_n/n)^*.
\end{eqnarray*}
So

\begin{eqnarray*}
\pr{\frac{S_n}{n} - \mu < \epsilon} & = &
      \pr{\frac{S_n/n - \mu}{\sigma_{S_n/n}} < \frac{\epsilon}{\sigma_{S_n/n}}\\
      & = & \pr{(S_n/n)^* < \frac{\epsilon}{\sigma/\sqrt{n}}}\\
      & = & \pr{(S_n/n)^* < \frac{\epsilon\sqrt{n}}{\sigma}}\\
      & = & \pr{(S_n)^* < \frac{\epsilon\sqrt{n}}{\sigma}}\\
\frac{\sigma}{\sqrt{n}}}\\

 \pr{(S_n)^* < \epsilon}\\
         & = & \pr{(S_n/n)^* < \epsilon}\\
         & = & \pr{\frac{S_n/n - \mu}{\sigma/\sqrt{n}}< \epsilon}\\

\end{eqnarray*}
\fi

\end{document}
