\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{15}{Milestones of Probability Theory}

\section{Introduction}

Many probabilistic processes can be understood as limits of processes with
binomial densities.  That is, their densities can be approximated
arbitrarily closely by a binomial density $f_{n,p}$ for suitable choices
of $n$ and $p$.  In these Notes, we consider two important results of this
kind.  First, we consider Poisson processes, which are limits of binomial
processes where $n \to \infty$ and $p\to 0$ while $np$ remains constant.
Second, by fixing $p$ and letting $n$ approach infinity, we arrive at a
profound result of probability theory: the Central Limit Theorem.

We also consider another fundamental result called the \emph{Strong} Law
of Large Numbers.  The Strong Law provides important information about how
the average of independent trials may vary during the course of the
trials.  The
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln13-14.pdf}
{ln13}{weaklaw}{Weak Law} we considered in Notes 13-14 is implied by the
Strong Law in most circumstances.  The Weak Law is also a simple Corollary
of the Central Limit Theorem.  However, neither the Central Limit Theorem
nor the Strong Law imply each other.

\iffalse


\section{The Exponential Distribution}

The exponential distribution is an important one that arises time and
again in the study of computer systems; you will see it in 6.033 for
example.  It arises naturally whenever you are interested in the
aggregate behavior of a large system.  So it's quite important to know
what it is.

\iffalse Unfortunately, this distribution is a \emph{continuous}
probability distribution.  We don't have time to develop the theory for
these distributions, so some of what we now present will have to be
accepted without proof.
\fi

\subsection{Derivation}

Let's consider a particular example.  Consider a system such as a computer
that each hour sees an average of $\lambda$ failures.  We want to model
the probability distribution associated with the failure time of the
system.  A particularly simple model is to break an hour up into small
intervals of, say, seconds, and to suppose that in each second, the
probability of the system failing, given that it has not yet failed, is
some constant $p$.  In other words, we flip an independent coin each
second, and the system fails when the coin comes up heads.

Specifically, lets consider a time period of $n$ seconds, where we expect
there to be failures in $np$ of these seconds.  To model the expectation
of $\lambda$ failures per hour, we need $p=\lambda/3600$.

Now we can determine the probability that no failures have occurred during
the first $n$ seconds of an hour.  Let $S_i$ denote the event that the
system stays working in the $i$th second, assuming that it was working
until then.  Then the probability that the system is still working at the
$n$th second is just the probability that there was no failure by that
time, which can be written as
\begin{align*}
\pr{S_1 \cap S_2\cap S_3\cap \cdots\cap  S_n}
&= \pr{S_1} \cdot \pr{S_2 \mid S_1} \cdot \pr{S_3 \mid S_1 \cap S_2}
  \cdots \pr{S_n \mid S_1 \cap S_2 \cdots \cap S_{n-1}}\\
&= (1 - p)^{n}\\
&= (1 - \lambda/3600)^{n}\\
& = ((1 - \lambda/3600)^{3600})^{\frac{n}{3600}}\\
& \approx e^{-\lambda \frac{n}{3600}}.
\end{align*}


ARM May 4, 2002: I STOPPED REVISING HERE.  See Spring '01 for last version
from Karger.  My idea is to define $X_{3600}$ to be RV with values
0,\dots,3600 describing how many seconds to before a first failure during
the hour.  Then improve approximation by considering milliseconds instead
of seconds and get $X_{3,600,000}$.  Generalize to $X_k$ with
range $ 0,\dots, k$ and
\[
\pr{X_k \geq \alpha k} \approx e^{-\lambda \alpha},
\]
for $0 \le \alpha \le 1$.  Handle expectation of exponential distribution
$\lim_{k\to\infty} \expect{X_k}$ ....

UNEDITED FROM SPRING '02:

Of course, there is no particularly ``natural'' choice for $n$.  It is
convenient to take $n$ arbitrarily large (resulting in infinitesimally
small intervals), and work with the limiting value:
\begin{align*}
\pr{S_1 \cap S_2\cap S_3\cap \cdots \cap  S_n}
&= (1-\lambda t/n)^{n} \\
&\approx e^{-\lambda t}.
\end{align*}
This formula meets some quick sanity checks.  In particular, the
probability that the failure time exceeds 0, \ie\ that the system is
initially working, is $e^{-0}=1$, while the probability of never
failing, \ie\ that the failure time is infinite, is $e^{-\infty}=0$.

Let us write $X$ for the time of first failure of our system.  We have
just argued that
\[
\pr{X > t} = e^{-\lambda t}.
\]
This distribution on $X$ is known as the \emph{exponential distribution}.
We're taking a bit of a leap here, by considering a probability
distribution on a continuous, real-valued random variable.  This raises
disturbing questions---for example, what is $\pr{X=t}$ for some particular
$t$?  Answering this question carefully would force a digression into
calculus and measure theory.  We'll leave that to another course, and
simply forge ahead.

\subsection{Expectation of the Distribution}

Given our model, it is natural to ask about the expected time $\expect{X}$
of the first failure of our system.  This quantity is known as the
system's \emph{Mean Time to Failure (MTTF)}.  We don't really know how
to compute the expectation of a continuous random variable, but the
following analogy turns out to be true: just as for a random variable
$Y$ over the natural numbers, $\expect{Y} = \sum_k \pr{Y \ge k}$, it turns
out that
\begin{align*}
\expect{X} &= \int_0^\infty  \pr{X>t} dt\\
&= \int_0^\infty  e^{-\lambda t}\,dt\\
&= \left. -\frac{1}{\lambda} e^{-\lambda t} \right|_0^\infty\\
&= \frac{1}{\lambda}.
\end{align*}
In other words, given a failure rate of $\lambda$, we expect a failure
every $1/\lambda$ time steps, which seems quite reasonable.  We'll
state this as a theorem:

\begin{theorem}
If $X$ is exponentially distributed with rate $\lambda$, then
$\expect{X}=1/\lambda$.
\end{theorem}

\subsection{Memorylessness}


The fundamental assumption of the exponential distribution is
\emph{memorylessness}: we assume that the failure within any
particular interval is \emph{independent} of all the past history.
This is an extremely strong assumption.  It is certainly convenient,
and sometimes it even turns out to be true.  For example, the decay
time of a radioactive particle (which can be thought of as a
``failure'' of the particle) follows an exponential distribution.  The
particle has no memory of how long it has been in a nondecayed state;
if it undecayed now it has a small probability of decaying in the next
interval, regardless of the past.  The MTTF for a particle is related
to its half-life.  The half life of an isotope is the time it takes
for the amount of particles of that isotope to be reduced by half in
expectation; this is just the time $t$ such that probability of the
particle surviving is 1/2.  This requires $e^{-\lambda t} = 1/2$, or
$t=(\ln 2)/\lambda$.

Exponential distributions are also used to model the arrival of ``new
events''---a new packet at a computer, a new bus at a bus-stop, a
birth at a hospital.  In these models, the key memoryless assumption
must be evaluated carefully.  For example, many hardware products
suffer from ``infant mortality''---undetected manufacturing defects
cause frequent early failures, after which any product that survuves
this early winnowing is likely to turn out more reliable.  But even
when the assumptions turns out to be false, the exponential
distribution often provides a good first approximation for getting a
handle on the problem.

Another way to look at the memoryless property is the following.
Suppose we are told that no failure occurs after time $t$.  What can
we say about the probability that the computer is operating after time
$t+s$?  This is simply a conditional probability calculation:
\begin{align*}
\pr{X > t+s \mid X > t} &= \frac{\pr{X > t+s}}{\pr{X>t}}\\
&= \frac{e^{-\lambda(t+s)}}{e^{-\lambda t}}\\
&= e^{-\lambda s}\\
&= \pr{X>s}
\end{align*}
If we know the system survives until time $t$, then its probability
distribution is simply an exponential distribution based at time $t$,
rather than time $0$.

\subsection{Redundancy}

In an attempt to make systems more reliable, people sometimes yoke
several identical systems together.  For example, the space shuttle
has three identical computers working at all times.  If a single
computer fails and starts producing wrong answers, the other two can
join together to outvote it.  But if two fail, all bets are off.
Supposing the failure distribution for each computer is independent
and exponential with rate $\lambda$, this raises two interesting
questions: first, when might we expect the first failure of one of the
three computers, and second, when might we expect two failures, which
puts the shuttle out of commission?

Let $X_1$, $X_2$, and $X_3$ denote the failure times of the three
computers, and let $Y_1$ denote the failure time of the first to fail,
that is $Y_1=\min X_1, X_2, X_3$.  Then since the three random
variables $X_i$ are independent,
\begin{align*}
\pr{Y_1 > t} &= \pr{X_1 > t \, \cap X_2 > t \, \cap \, X_3 > t}\\
&= \pr{X_1 >t}\cdot \pr{X_2 > t} \cdot \pr{X_3 > t}\\
&= e^{-\lambda t} \cdot e^{-\lambda t} \cdot e^{-\lambda t}\\
&= e^{-3\lambda t}
\end{align*}

In other words, the random variable $Y_1$ is exponentially
distributed with rate $3\lambda$.  This makes sense: if 3 systems
each expected $\lambda$ failures per time step, then the 3 together
should expect 3 times as many failures.  Our expectation calculation
above immediately yields the expected time of the first failure:
$1/3\lambda$.  This is a specific instance of a general theorem.  Note
that this theorem applies even if the random variables have
\emph{distinct} rates:

\begin{theorem}
If $X_1,\dots,X_n$ are independent exponential random variables with
rates $\lambda_1,\dots,\lambda_n$, then $\min X_1,\dots,X_n$
is an exponential random variable with rate
$\lambda_1+\cdots+\lambda_n$
\end{theorem}


Now let's consider the second failure.  This is more complicated.  Suppose
that we know the first failure is at time $t$, and that computer 3 is the
one that failed.  The second failure occurs when one of the remaining two
computers fails.  Let $Y_2$ denote the time of this second failure.  We
can analyze $Y_2$ by considering the \emph{difference} $Y_2-Y_1$.  Our
declaration that the first failure occurred at $t$ means that we know
$X_1>t$ and $X_2>t$.  By the memoryless property of the exponential
distribution, this means that the failure times of the two remaining
computers \emph{beyond time $t$} are exponentially distributed with rate
$\lambda$.  It follows that the \emph{minimum} of these two failure times
beyond time time is exponentially distributed with rate $2\lambda$.
Therefore, the expected time that the two computers survive beyond time
$t$ is $1/2\lambda$.  It follows that the expected survival time of the
overall system is
\begin{align*}
\expect{Y_2} &= \expect{Y_1}+\expect{Y_2-Y_1}\\
&= 1/3\lambda + 1/2\lambda\\
&= 5/6\lambda
\end{align*}

This isn't even as good as the MTTF of $1/\lambda$ for a single computer!
Perhaps the NASA builders are hoping that when computers fail, they stop
producing conflicting answers.  In this case the shuttle can keep flying
until the final computer fails.  Arguing as above, the time for the last
computer to fail once the other two have failed is exponentially
distributed with mean $\lambda$, meaning that the MTTF for the entire set
of 3 computers is $1/3\lambda+1/2\lambda+1/\lambda = 11/6\lambda$, a
modest improvement.  This type of replication has limited benefits,
however: it is easy to generalize and show that the MTTF for the last of
$n$ replicas of the system is only $H_n \approx \ln n$.
\fi


\section{The Poisson Approximation}

We've worked with the binomial distribution, which measures the
probability of $k$ successful outcomes occur in a sequence of $n$
independent trials.  In this section we'll consider a closely related and
widely applicable distribution known as the \emph{Poisson distribution}.
The Poisson distribution arises when $n$ is much larger than the expected
number of successful outcomes.

\subsection{Poisson Random Variables}
Let's consider a particular example.  Suppose that we want to model the
arrival of packets at an internet router.  We know that on average the
router handles $\lambda=10^7$ packets per second.  Given this expected
value, how can we model the actual distribution of packet arrivals in a
second?  One possible model is to break up each second into tiny intervals
of size $\delta>0$ seconds, so there are a large number, $n = 1/\delta$,
of tiny intervals.  Then we declare that in each tiny interval, a packet
arrives with probability $\lambda\delta$ (this gives the right expected
number of arrivals).  Under this model, the number, $X$, of intervals in
which a packet actually arrives has a binomial distribution:
\begin{equation}\label{pXk}
\pr{X=k} =
\binom{1/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{1/\delta-k}.
\end{equation}
Note that this is not quite the same as counting the number of arrivals,
since more than one packet may arrive in a given interval.  But if the
interval is tiny, this is so unlikely that we can ignore the possiblity.

Now we let $\delta$ become infinitesimally small (while holding $k$ fixed)
and make use of three approximations:
\begin{eqnarray*}
\binom{1/\delta}{k} &\approx & \frac{(1/\delta)^k}{k!}\\
(1-\lambda\delta)^{1/\delta} &\approx & e^{-\lambda}\\
1 - \delta k & \approx & 1.
\end{eqnarray*}
Plugging these approximations into~(\ref{pXk}) yields
\begin{align}
\pr{X=k}
   &=\binom{1/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{1/\delta-k}\notag\\
   &=\binom{1/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{(1-\delta k)/\delta}\notag\\
&\approx \frac{(1/\delta)^k}{k!} (\lambda\delta)^k(1-\lambda\delta)^{1/\delta}\notag\\
&= \frac{\lambda^k}{k!} (1-\lambda\delta)^{1/\delta}\notag\\
&\approx \frac{\lambda^k}{k!} e^{-\lambda}\label{Poisson density}
\end{align}
The probability distribution~(\ref{Poisson density}) is known as the
\emph{Poisson distribution}.  When system events appear according to a
Poisson density, the system is called a \emph{Poisson process}.

Another example where a Poisson distribution fits the facts is in
observing the number of misprints per page in a book.  In a well edited
book, there may be an average of one misprint on every three pages.  That
is, there is an average of $\lambda = 1/3$ misprints per page.  An average
page has about 40 lines of a dozen words, or about $n = 480$ words.  If we
suppose that each word has an independent probability of $1/(3 \cdot 480)$
of containing an uncorrected misprint, then the density function of errors
per page would be $f_{480,1/1440}$, which will be approximated to three
decimal places by the Poisson density with $\lambda = 1/3$.

Further examples of random variables which generally obey a Poisson
distribution include:
\begin{itemize}

\item the number of decaying particles in a radioactive sample in a
given time interval,

\item the distribution of the number of failures per day of a system,

\item the number of people in a community who are older than 100 years,

\item the number of vacancies occurring per year on the Supreme Court,

\item the number of wrong telephone numbers dialed in Boston per day.

\end{itemize}

\subsection{Properties of the Poisson Distribution}

As a sanity check on our distribution, the probability
values~(\ref{Poisson density}) had better sum to 1.  Using the Taylor
expansion for $e^{\lambda}$, we can verify that they do:
\[
\sum_{k \in \naturals} \pr{X=k} = \sum e^{-\lambda}\frac{\lambda^k}{k!}
= e^{-\lambda} \sum \frac{\lambda^k}{k!}
= e^{-\lambda}e^{\lambda} = 1.
\]

A further sanity check is that the expected number of arrivals in a second
is indeed $\lambda$, namely,
\begin{equation}\label{Elam}
\expect{X}= \lambda.
\end{equation}

Similarly, the binomial distribution $f_{n,p}$ has variance
$np(1-p)$.  Since the Poisson distribution is the limit
of $f_{1/\delta,\lambda\delta}$ as $\delta$ vanishes, it ought to have
variance
\[
(1/\delta)(\lambda\delta)(1- \lambda\delta) = \lambda(1 - \lambda\delta)
\approx \lambda.
\]
The final approximation holds since $1 - \lambda\delta \approx 1$ for
vanishing $\delta$.  In other words,
\begin{equation}\label{Vlam}
\variance{X}= \lambda.
\end{equation}

Also, suppose we have two independent Poisson processes $X_1, X_2$
contributing arrival events at the respective rates $\lambda_1,\lambda_2$.
Intuitively, this ought to be the same as having a single process
producing independent arrivals at the rate $\lambda_1 + \lambda_2$.  This
explains another useful property of the Poisson distribution:
\begin{lemma}\label{lamsum}
If $X_1$ are $X_2$ are Poisson processes, then so is $X_1+X_2$.
\end{lemma}

Both equations~(\ref{Elam}) and~(\ref{Vlam}), and Lemma~\ref{lamsum}, are
easy to verify formally from the definition~(\ref{Poisson density}) of the
Poisson distribution and the Taylor series for $e$.

\begin{optional}

Finally, we can develop a Chernoff style bound for the probability that a
Poisson process deviates from its mean.  As in the proof of the Chernoff
bound, we have for \emph{any} random variable, $R \geq 0$, and constants
$c,t \geq 0$, that
\[
R \geq c\text{  iff  } e^{tR} \geq e^{tc}.
\]
So by Markov's inequality
\begin{equation}%\label{moment Chernoff}
\pr{R \geq c} \leq \frac{\expect{e^{tR}}}{e^{tc}}
\end{equation}

For a Poisson process, $X$, we have
\begin{align*}
\expect{e^{tX}} & =  \sum_{k \in \naturals}
  \frac{e^{tk}e^{-\lambda}\lambda^k}{k!}\\ %\notag
  &=  e^{-\lambda} \sum\frac{(\lambda e^t)^k}{k!}\\ %\notag
  & =  e^{-\lambda} e^{\lambda e^t}\\ %\notag
  & =  e^{\lambda (e^t -1)}. %\label{Poisson moment}
\end{align*}
So if $X$ is a Poisson process,
\begin{equation}\label{Xgc}
\pr{X \geq c} \leq e^{\lambda (e^t -1)}e^{-tc} = e^{\lambda (e^t -1) - tc}.
\end{equation}
To minimize the exponent, we choose $t = \ln (c/\lambda)$, which will be
positive as long as $c > \lambda$.  Substituting this value for $t$
into~(\ref{Xgc}), we conclude
\begin{equation}\label{Poisson deviation}
\pr{X \geq c} \leq e^{c\ln (\lambda/c) + c - \lambda}.
\end{equation}

Now letting, $c= c'\lambda$ in~(\ref{Poisson deviation}) and
using~(\ref{Elam}) yields
\begin{align*}
\pr{X \geq c'\expect{X}} & \leq e^{c'\lambda\ln (1/c') + c'\lambda - \lambda}\\
   & = e^{-c'\lambda\ln c' + c'\lambda - \lambda}\\
   & = e^{-(c'\ln c' - c' + 1)\lambda}\\
   & = e^{-(c'\ln c' - c' + 1)\expect{X}}.
\end{align*}
Notice that this is exactly the same as the Chernoff bound.  So we have
yet another way in which a Poisson process behaves like a sum of
independent indicator variables.

\iffalse
Exercise: Show that $\variance{X} = \lambda$.  \textbf{Is there intuition for this?}
\fi

\iffalse  UNCOMMENT IF EXPONENTIAL DISTRIBUTION SECTION IS USED

Noteworthy is the probability that $X=0$, that is, that no arrivals occur
in time $t$.  Plugging in $k=0$, we find that this is $e^{-\lambda t}$.
This is consistent with our previous derivation of the exponential
distribution.
\fi

\end{optional}


\section{The Central Limit Theorem}

In the Weak Law of Large Numbers we had $S_n \eqdef \sum_{i=1}^n G_i$
where $G_1, \dots, G_i, \dots$ were mutually independent variables with
same mean, $\mu$, and deviation $\sigma$.  The Weak Law said that the
probability that $S_n/n$ was outside an interval of fixed size $\epsilon
>0$ around $\mu$ approached 0 as $n$ approached infinity.

The Central Limit Theorem describes not just the limiting behavior of
deviation from the mean of $S_n/n$, but actually describes a limiting
shape of the entire distribution for $S_n/n$.  So this theorem
substantially refines the Weak Law.

\begin{definition}
For any random variable $R$ with finite mean, $\mu_R$, and
deviation, $\sigma_R$, let $R^*$ be the random variable
\[
R^* \eqdef \frac{R-\mu_R}{\sigma_R}.
\]
$R^*$ is called the ``normalized'' version of $R$.
\end{definition}
Note that $R^*$ has mean 0 and deviation 1.  In other words, $R^*$ is just
$R$ shifted and scaled so that its mean is 0 and its deviation and
variance are 1.

The Central Limit Theorem says that \emph{regardless} of the underlying
distribution of the variables $G_i$, so long as they are independent, the
distribution of $S^*_n$ converges to the same, \emph{normal},
distribution.  It is not surprising that this normal distribution---also
known as a \emph{Gaussian} distribution---plays a fundamental role in the
study of probability and statistics: as long as you are summing enough
random variables, you can pretend that the result is Gaussian.

\begin{definition}
The \emph{normal density function} is the function 
\[
\eta(x) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2},
\]
and the \emph{normal distribution function} is its integral
\[
N(y) = \int_{-\infty}^y \eta(x)dx = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^y
e^{-x^2/2}dx.
\]
\end{definition}

The function $\eta(x)$ defines the standard \emph{Bell curve}, centered about
the origin with height $1/\sqrt{2\pi}$ and about two-thirds of its area
within unit distance of the origin.  The normal distribution function
$N(y)$ approaches 0 as $y \rightarrow -\infty$.  As $y$ approaches zero
from below, $N(y)$ grows rapidly towards $1/2$.  Then as $y$ continues to
increase beyond zero, $N(y)$ rapidly approaches 1.

\begin{theorem*}[Central Limit] \label{normal}
Let $S_n = \sum_{i=1}^n G_i$ where $G_1, \dots, G_i, \dots$ are mutually
independent variables with the same mean, $\mu$, and deviation, $\sigma$.
Let $\mu_n \eqdef \expect{S_n} = n\mu$, and $\sigma_n \eqdef \sigma_{S_n}
= n\sigma$.  Now let $S^*_n \eqdef (S_n-\mu_n)/\sigma_n$ be the normalized
version of $S_n$.  Then
\[
\lim_{n\rightarrow\infty} \pr{S^*_n \leq \beta}= N(\beta)
\]
for any real number $\beta$.
\end{theorem*}

\iffalse
It is clear that $N(x)$ is an increasing function of $x$, and that
$N(-\infty)=0$.  It can also be shown that $N(\infty)=1$.  Thus $N(x)$ can
be interpreted as the probability that a certain \emph{normally
distributed} random variable is less than $x$.  But this requires a study
of continuous distributions (with an uncountable number of sample points,
namely the real numbers).  We haven't developed the formal machinery for
that, so we will just think of $N(x)$ as a function.
\fi

To understand the Central Limit Theorem, it helps to see how it implies
the Weak Law of Large Numbers.

Note first that $\mu_{S_n} = n\mu$, $\variance{S_n} = n\sigma^2$, and so
$\sigma_{S_n} = \sigma\sqrt{n}$.  Now,
\begin{eqnarray*}
\abs{\frac{S_n}{n} - \mu} > \epsilon & \text{ iff } &
      \abs{S_n - n\mu} > n\epsilon\\
      & \text{ iff }  & \abs{\frac{S_n - n\mu}{\sigma_{S_n}}} > \frac{n\epsilon}{\sigma_{S_n}}\\
      &  \text{ iff } & \abs{S^*_n} > \dfrac{\sqrt{n}\epsilon}{\sigma}.
\end{eqnarray*}
But for any real number $\beta>0$,
\[
\frac{\sqrt{n}\epsilon}{\sigma} > \beta
\]
will hold for all large $n$.  Hence, for any $\beta >0$ and all large $n$,
\begin{equation} \label{Sne}
\pr{\abs{\frac{S_n}{n} - \mu} > \epsilon} = \pr{\abs{S^*_n} >
    \frac{\sqrt{n}\epsilon}{\sigma}} \leq \pr{\abs{S^*_n} > \beta}.
\end{equation}
So
\begin{align*}
\lim_{n\rightarrow\infty}
    \pr{\abs{\frac{S_n}{n} - \mu} > \epsilon}
 \leq & \lim_{n\rightarrow\infty}
    \pr{\abs{S^*_n} > \beta} & \text{(by~(\ref{Sne}))}\\
 = &  \lim_{n\rightarrow\infty} \pr{S^*_n > \beta} + \pr{S^*_n < -\beta}\\
 = &\  1 - N(\beta) + N(-\beta), & \text{(by the Central Limit Thm~(\ref{normal}))}
\end{align*}
for all real numbers $\beta >0$.  By choosing $\beta$ large enough, we can
ensure that $N(\beta)$ is arbitrarily close to 1 and $N(-\beta)$ is
arbitrarily close to 0, so that final term above is arbitrarily close to
1-1+0 = 0.  Hence,
\[
\lim_{n\rightarrow\infty} \pr{\abs{\frac{S_n}{n} - \mu} > \epsilon} = 0,
\]
which is the Weak Law of Large Numbers.

We will not prove the Central Limit Theorem, but will only note that a
standard proof rests on extending ideas we have already used in deriving
Chernoff bounds, in particular properties of $\expect{e^{tX}}$.  Regarded
as a function of $t$, $\expect{e^{tX}}$ is called the \emph{moment
generating function} of the random variable, $X$.  The Central Limit
Theorem can be proved using a more complete development of the properties
of moment generating functions, more than we have time for in 6.042.

Like the Weak Law of Large Numbers, the Central Limit Theorem as stated
cannot be applied to actual problems because the necessary information
about the rate of convergence is missing, that is, we need to know the
accuracy with which the limit $N(\beta)$ approximates the probability that
$S^*_n < \beta$.  For variables $G_1, G_2, \dots$ whose absolute value is
bounded by about 5, or are themselves are normal, a rule of thumb is
that~(\ref{normal}) holds to one or two decimal places when $\abs{\beta} <
3$ and $n>30$.  But in situations such as those we have seen for designing
overload tolerance into systems, and also for ensuring the quality of the
solution to an optimization problem by a probabilistic algorithm, we are
typically more concerned with events that differ from the mean by many
standard deviations.  For estimating probabilities at such distribution
tails, Chernoff bounds are more accurate than those based on normal
distributions.  For this reason, Chernoff bounds play a more prominent
role in Computer Science than the Central Limit Theorem.


\section{Strong Law of Large Numbers [Optional]}

\begin{optional}

We described the \emph{Weak} Law of Large Numbers in previous notes,
begging the question of what \emph{strong} law of large numbers we might
prove.  Roughly speaking, the strong law says that with probability 1, the
bound of the weak law will hold for all but a finite number of the $S_n$
\emph{simultaneously}---there will only be finitely many exceptions to it.

\begin{theorem}\label{Strong} [The Strong Law of Large Numbers]
\footnote{This section taken from Ross, \emph{A First Course in
Probability Theory}.}  Let $S_n \eqdef \sum_{i=1}^n X_i$ where $X_1, \dots,
X_i, \dots$ are mutually independent, identically distributed random
variables with finite expectation, $\mu$.  Then
\[
\pr{\lim_{n\to\infty}\frac{S_n}{n} = \mu} =1.
\]
\end{theorem}


\iffalse
As an application of the strong law of large numbers, suppose that a
sequence of independent trials of some experiment is performed.  Let $E$
be a fixed event of the experiment and denote by $\pr{E}$ the probability
that $E$ occurs on any particular trial.  Letting
\[
X_i = 
\begin{cases}
1 &\text{if $E$ occurs on the $i$th trial},
\\
0 &\text{if $E$ does not occur on the $i$th trial},
\end{cases}
\]
we have by the strong law of large numbers that with probability~1, 
\begin{equation}
\label{eq:1}
\frac{X_1+X_2+\cdots+X_n}{n}\to\expect{X}=\pr{E}.
\end{equation}
Since $X_1+X_2+\cdots+X_n$ represents the number of times that the
event $E$ occurs in the first $n$ trials, we may interpret
Equation~(\ref{eq:1}) as stating that, with probability~1, the
limiting proportion of time that the event $E$ occurs is just
$\pr{E}$. 
\fi

Although Theorem~\ref{Strong} can be proven without this assumption, we
will assume for simplicity that the random variables $X_i$ have a finite
fourth moment.  That is, we will suppose that
\begin{equation}\label{K}
\expect{X_i^4}=K<\infty.
\end{equation}

\begin{proof}
To begin, assume that $\mu$, the mean of the $X_i$, is equal to~0.  As
usual, let $S_n \eqdef \sum_{i=1}^n X_i$ and consider 
\begin{equation}\label{Sn4}
\expect{S_n^4} =
\expect{(X_1+\cdots+X_n)
\times
(X_1+\cdots+X_n)
\times
(X_1+\cdots+X_n)
\times
(X_1+\cdots+X_n)
}.
\end{equation}
Expanding the righthand side of~(\ref{Sn4}) results in terms of the forms
\[
X_i^4,\qquad
X_i^3X_j,\qquad
X_i^2X_j^2,\qquad
X_i^2X_jX_k,\qquad
X_iX_jX_kX_l
\]
where $i,j,k,l$ are all different.  As all the $X_i$ have mean~0, it
follows by independence that 
\begin{align*}
\expect{X_i^3X_j}
&=
\expect{X_i^3}\expect{X_j} = 0
\\
\expect{X_i^2X_jX_k}
&=
\expect{X_i^2}\expect{X_j}\expect{X_k} = 0
\\
\expect{X_iX_jX_kX_l}
&= 0.
\end{align*}
Now, for a given pair $i$ and $j$ there will be $\binom{4}{2}=6$ terms in
the expansion that will equal $X_i^2X_j^2$.  Hence, after expanding the
righthand side~(\ref{Sn4}), we have
\begin{align}
\expect{S_n^4} &= n\expect{X_i^4} + 6\binom{n}{2}\expect{X_i^2X_j^2}
      & \text{(linearity of expectation)}\\
  &= nK + 3n(n-1)\expect{X_i^2}\expect{X_j^2}.
      & \text{(by~(\ref{K}) and independence)} \label{nK}
\end{align}
Now,
since 
\[
0\leq \variance{X_i^2} = \expect{X_i^4} - \expectsq{X_i^2}
\]
we see that 
\[
\expectsq{X_i^2} \leq \expect{X_i^4} = K. 
\]
Therefore, from~(\ref{nK}) we have that 
\[
\expect{S_n^4} \leq nK + 3n(n-1)K
\]
which implies that 
\[
\expect{\frac{S_n^4}{n^4}} \leq \frac{K}{n^3} + \frac{3K}{n^2},
\]
and so
\[
\expect{\sum_{i=1}^\infty \frac{S_n^4}{n^4}} = 
\sum_{i=1}^\infty \expect{\frac{S_n^4}{n^4}} \leq
K \sum_{i=1}^\infty \frac{1}{n^3} + \frac{3}{n^2}
< \infty.
\]

But since the expected value is finite, the probability that
$\sum_{i=1}^\infty S_n^4/n^4$ is finite must be one.  (If there was a
positive probability that the sum is infinite, then its expected value
would be infinite.)  Now the convergence of a series implies that its
$n$th term goes to~0; so we can conclude that $\lim_{n\to\infty}
S_n^4/n^4 = 0$ with probability~1.  But if $S_n^4/n^4 = (S_n/n)^4$
goes to~0, then so must $S_n/n$; so we have completed the proof that with
probability~1,
\[
\frac{S_n}{n} \to~0 \qquad \text{as }n\to\infty.
\]

When $\mu$, the mean of the $X_i$, is not equal to~0, we can apply the
preceding argument to the random variables $X_i-\mu$ to obtain that with
probability~1,
\[
\lim_{n\to\infty} \sum_{i=1}^n \frac{X_i-\mu}{n} = 0
\]
or, equivalently,
\[
\lim_{n\to\infty} \sum_{i=1}^n \frac{X_i}{n} = \mu
\]
which proves the result.
\end{proof}

We remark that as in the Weak Law, full mutual independence of $\set{X_i}$
is not necessary.  The proof above only requires that $\set{X_i}$ are
4-way independent.

\subsection{A Failure of the Strong Law}

To clarify the somewhat subtle difference between the Weak and Strong Laws
of Large Numbers, we will construct an example of a sequence
$X_1,X_2,\dots$ of mutually independent random variables that satisfies
the Weak Law of Large Numbers, but not the Strong Law.  The distribution
of $X_i$ will have to depend on $i$, because otherwise both laws would be
satisfied.\footnote{This problem is adapted from Grinstead \& Snell,
\emph{Intro. to Probability}, Ch.8, exercise 16, pp314--315, where it is
credited to David Maslen.}

In particular, let $X_1,X_2,\dots$ be the sequence of mutually independent
random variables such that $X_1=0$, and for each integer $i > 1$,
\[
\pr{X_i=i} = \frac{1}{2i\log i},\quad
\pr{X_i=-i} = \frac{1}{2i\log i},\quad
\pr{X_i=0} = 1 - \frac{1}{i\log i}.
\]
Note that $\mu = \expect{X_i} = 0$ for all $i$.

\begin{problem*}
\bparts

\problempart
Show that $\variance{S_n} = \Theta(n^2/\log n)$.
\hint $n/\log n > i/\log i$ for $2 \leq i \leq n$. %$\int x/\log x\, dx = ???$

\solution{\begin{align}
\variance{S_n} & = \sum_{i=1}^\infty \variance{X_i} &\text{(independent variance
additivity)}\notag\\
  & = \variance{X_1}+ \sum_{i=2}^n \expect{X_i^2} - \expectsq{X_i}\notag\\
  & =  0+ \sum_{i=2}^n i^2\left( \frac{1}{i\log i} - 0\right)\notag\\
  & =  \sum_{i=2}^n \frac{i}{\log i}.\notag\\
  & = \Theta(n^2/\log n). & \text{(see below)}\label{Theta}
\end{align}

To justify~(\ref{Theta}), note that $x/\log x$ is increasing for $x>e$
since its derivative $(1/\log x) (1- 1/\log x)$ is positive.  So $n/\log n
\geq i/\log i$ for $2 \leq i \leq n$.  Therefore,
\begin{align*}
\frac{n^2}{\log n} & = \sum_{i=1}^n \frac{n}{\log n}\\
  & \geq \sum_{i=2}^n \frac{i}{\log i}\\
  & \geq \sum_{i=\ceil{n/2}}^n \frac{i}{\log i}\\
  & \geq \sum_{i=\ceil{n/2}}^n \frac{n/2}{\log n}\\
  & \geq \frac{n+1}{2} \frac{n/2}{\log n}\\
  & \geq \frac{1}{4}\frac{n^2}{\log n}.
\end{align*}
}

\problempart
Show that the sequence $X_1,X_2,\dots$ satisfies the Weak Law of Large
Numbers, \ie prove that for any $\epsilon>0$ 
\[
\lim_{n \to \infty} \pr{ \abs{\frac{S_n}{n}} \geq \epsilon } = 0.
\]

\solution{
\begin{align*}
\pr{\abs{\frac{S_n}{n}} \geq \epsilon} & =
  \pr{\abs{\frac{S_n}{n}-0} \geq \epsilon}\\
  &  \leq \variance{\frac{S_n}{n}}\frac{1}{\epsilon^2} & \text{(Chebychev Bound)}\\
  & = \frac{\variance{S_n}}{n^2}\frac{1}{\epsilon^2}\\
  & = \Theta(\frac{1}{\epsilon^2\log n}), & \text{(by~(\ref{Theta}))}
\end{align*}
which goes to zero as $n$ goes to $\infty$.
}

\end{problemparts}

We now show that the sequence $X_1,X_2,\dots$ does not satisfy the Strong
Law of Large Numbers.

\begin{problemparts}

\problempart\label{BC}
(The first Borel-Cantelli lemma.) 
Let $A_1,A_2,\dots$ be any infinite sequence of mutually independent
events such that
\begin{equation}\label{sai}
\sum_{i=1}^\infty \pr{A_i} = \infty.
\end{equation}
Prove that
\[
\pr{\text{infinitely many $A_i$ occur}} = 1.
\]
\hint We know that the probability that
no $A_i$ with $i \geq r$ occurs is
\begin{equation}\label{-eT}
\leq  e^{-\expect{T_r}}
\end{equation}
where $T_r \eqdef \sum_{i=r}^\infty I_{A_i}$ is the number of events $A_i$
with $i\geq r$ that occur.

\solution{
\begin{align*}
\expect{T_r} & = \sum_{i=r}^\infty \expect{I_{A_i}}
         &\text{(linearity of expectation)} \\
  & = \sum_{i=r}^\infty \pr{A_i} & \text{(expectation of indicator
         variable)}\\
  & = \infty & \text{(by~(\ref{sai}))}.
\end{align*}
So it follows from~(\ref{-eT}) that the probability that no $A_i$ with $i
\geq r$ occurs is zero.  That is, the probability that only finitely many
$A_i$'s occur is zero, and hence the probability that infinitely many
occur is 1.
}

\problempart\label{divsum}
Show that
$\sum_{i=1}^\infty\pr{\abs{X_i}\geq i}$ diverges.  \hint $\int dx/(x
log x) = \log\log x$.

\solution{
$\pr{\abs{X_i}\geq i}= 1/(i\log i)$, so
\begin{align*}
\sum_{i=1}^n \pr{\abs{X_i}\geq i} & = 0+ \sum_{i=2}^n \frac{1}{i\log i}\\
  & \geq \int_2^{n+1} \frac{dx}{x\log x}\\
  & = \log\log (n + 1 ) - \log\log 2,
\end{align*}
and this last term approaches infinity and $n$ approaches infinity.
}

\problempart
Conclude that
\begin{equation}\label{sm0}
\pr{\lim_{n \to \infty} \frac{S_n}{n} = \mu} = 0.
\end{equation}
and hence that the Strong Law of Large Numbers \emph{completely} fails for
the sequence $X_1,X_2,\dots$.

\hint
\[
\frac{X_n}{n} = \frac{S_n}{n} - \frac{n-1}{n}\frac{S_{n-1}}{n-1},
\]
so if $\lim_{n \to \infty} S_n/n =  0$, then also
$\lim_{n \to \infty} X_n/n = 0$.

\solution{By parts~(\ref{BC}) and~(\ref{divsum}), the probability that
$\abs{X_i}\geq i$ for infinitely many $i$ is 1.  But if $\abs{X_i}\geq i$
for infinitely many $i$, then by definition of the limit, $\lim_{n \to
\infty} X_n/n \neq 0$.  Hence,
\[
\pr{\lim_{n \to \infty} X_n/n  \neq 0} = 1,
\]
which means
\begin{equation}\label{xn0}
\pr{\lim_{n \to \infty} X_n/n = 0} = 0,
\end{equation}
But the hint implies that
\begin{equation}\label{slx}
\pr{\lim_{n \to \infty} \frac{S_n}{n} =  0} \leq
\pr{\lim_{n \to \infty}  \frac{X_n}{n} = 0}.
\end{equation}
Now~(\ref{xn0}) and~(\ref{slx}) immediately imply~(\ref{sm0}).
}

\end{problemparts}
\end{problem*}

\end{optional}

\end{document}




