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

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}
%\renewcommand{\coursecopyrightyear}{2002}

\begin{document}
\lecturenotes{13}{Bounding Large Deviations from the Mean}

\newcommand{\IQ}{I.Q.\@\xspace}

\iffalse
\reading{Ross, ``A First Course in Probability'', Prentice-Hall, Sections 4.8,
8.3, 8.5; Motwani \& Raghavan 4.1--3.}
\fi

\section{Introduction}

These Notes cover two topics: a basic result about deviation from the mean
called the Chernoff Bound, and the behavior of Random Walks.

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 Notes 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/spring02/handouts/lectures/ln10.pdf}{Notes
10}.  In particular, the Chernoff bound is exponentially smaller than
bound given by the Pairwise Independent Sampling Theorem.

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

\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/spring02/handouts/lectures/ln9.pdf}{Notes
9}, \S 13, and in
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/miscellaneous/cp9W.pdf}{Class
Problems 9W}, Problem 2, 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


One 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
even will occur at least once in $m$ independent trials is approximately
$1- 1/e \approx 63\%$.  There is a 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/spring02/handouts/lectures/ln10.pdf}{Notes
10}.

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 terrorist attack on Albany Street during an
earthquake 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/spring02/handouts/lectures/ln10.pdf}{Notes
10} 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.


\section{Random Walks and Gamblers' Ruin}

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-dimensinal 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 zero, 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 $\epsilon >0$
such that
\[
\pr{\text{the walk is of length } \geq i} \leq (1 - \epsilon)^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{
\begin{lemma*}
If $0 < a < b$, then
\[
\frac{a}{b} < \frac{a+1}{b+1}.
\]
\end{lemma*}
\begin{proof}
\[
\frac{a}{b} = \frac{a(1+1/b)}{b(1+1/b)} = \frac{a+a/b}{b+1} < \frac{a+1}{b+1}.
\]
\end{proof}}, 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 tail bounds 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 a way to confirm it other than by
induction.

\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 the probability
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 he can expect to play forever.
\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, he can
expect to play forever!  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(\sum_{m=1}^\infty m\cdot m^{-3/2}) = 
\Theta(\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(\sum_{m=1}^\infty m^{-13/10})
\]
and
\[
\expect{R^2}  = \Theta(\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.


\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
