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

\def\IQ{I.Q}

\onlylecture

\begin{document}

\lecture{more tail bounds}{More on Deviation from the Mean}{10 May 2001}

\begin{breakperiods}

\forlecture{
\noindent
Topics for today:
\begin{itemize}
\item
Variance
\item
Chebyshev's Theorem
\item
Law of large numbers
\item
Chernoff Bounds
\end{itemize}

\reading{Rosen Section 4.4, 4.5; \\
Ross, ``A First Course in Probability'', Prentice-Hall, Sections 4.6,
8.2, 8.5}
}



\forlecture{
\section{Variance}

It is a bit messy to use Markov's inequality directly to bound the
probabilty that $|R - E(R)| \geq x$, since we then would have to
compute $\Ex(|R - E(R)|)$. Note, however, that Markov's inequality
also applies to the event $\{|R|^k \geq x^k\}$---since $|R|$ is a
non-negative variable, this event is equivalent to the event $\{|R|
\geq x\}$.
\begin{corollary}
  \label{cor:Markov2}
  For any random variable~$R$, any positive integer~$k$ and any $x >
  0$,
  \begin{displaymath}
    \Pr(|R| \geq x) \leq \frac{\Ex(|R|^k)}{x^k}\,.
  \end{displaymath}
\end{corollary}
This corollary has an interesting consequence. Let us apply it to the
case $k = 2$:
\begin{displaymath}
  \Pr\bigl(|R - \Ex(R)| \geq x\bigr)
  = \Pr\bigl((R - \Ex(R))^2 \geq x^2\bigr)
  \leq \frac{\Ex\bigl((R - \Ex(R))^2\bigr)}{x^2}\,,
\end{displaymath}
where the inequality follows from Corollary~\ref{cor:Markov2} applied
to the random variable $|R - \Ex(R)|$ and $k = 2$. Apparently, we can
bound the probability that the random variable~$R$ deviates from its
mean by more than~$x$ by an expression decreasing as $1 / x^2$
multiplied by the constant $\Ex((R - \Ex(R))^2)$. This constant is
called the \emph{variance of~$R$}.
\begin{defin*}
  The variance of a random variable $R$ is denoted $\Var(R)$ and is
  defined as follows:
  \[
  \Var(R) = \Ex((R - \Ex(R))^2)
  \]
\end{defin*}
The expression $\Ex((R - \Ex(R))^2)$ is a bit cryptic; the best
approach is to work through it from the inside out.  The innermost
expression, $R - \Ex(R)$, is precisely the deviation of $R$ from the
mean.  Squaring this, we obtain, $(R - \Ex(R))^2$.  This is a random
variable that is near 0 when $R$ is close to the mean and is a large
positive number when $R$ deviates far above or below the mean.  The
variance is just the average of this random variable, $\Ex((R -
\Ex(R))^2)$.  Therefore, intuitively, if $R$ is always close to the mean,
then the variance will be small.  If $R$ is often far from the mean,
then the variance will be large.  For this reason, variance is useful
in studying the probability that a random variable deviates far from
the mean.

\subsection{Example: Gambling Games}

The relevance of variance is apparent when we compare the following
two gambling games.

\begin{description}
\item{Game A:} We win \$2 with probability $\frac{2}{3}$ and lose \$1
with probability $\frac{1}{3}$.
\item{Game B:} We win \$1002 with probability $\frac{2}{3}$ and lose
\$2001 with probability $\frac{1}{3}$.
\end{description}

Which game is more better financially?  We have the same probability
($\frac{2}{3}$) of winning each game, but that does not tell the whole
story.  What about the expected return for each game?  Let random
variables $A$ and $B$ be the payoffs for the two games.  For example,
$A$ is 2 with probability $\frac{2}{3}$ and -1 with probability
$\frac{1}{3}$.  We can compute the expected payoff for each game as
follows:

\begin{eqnarray*}
\Ex(A) = 2 \cdot \frac{2}{3} + (-1) \cdot \frac{1}{3} = 1 \\
\Ex(B) = 1002 \cdot \frac{2}{3} + (-2001) \cdot \frac{1}{3} = 1
\end{eqnarray*}

The expected payoff is the same for both games, but they are obviously
very different!  This difference is hidden by expected value, but
captured by variance.  We can compute the $\Var(A)$ and $\Var(B)$ by
working ``from the inside out'' as follows:

\begin{eqnarray*}
A - \Ex(A)
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        -2 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(A - \Ex(A))^2
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        4 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\Ex(A - \Ex(A))^2
        & = &   1 \cdot \frac{2}{3} + 4 \cdot \frac{1}{3} \\
\Var(A) & = & 2
\end{eqnarray*}

\begin{eqnarray*}
B - \Ex(B)
        & = &   \left\{
                \begin{array}{cl}
                        1001 & \text{ with probability } \frac{2}{3} \\
                        -2002 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(B - \Ex(B))^2
        & = &   \left\{
                \begin{array}{cl}
                        1,002,001 & \text{ with probability } \frac{2}{3} \\
                        4,008,004 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\Ex(B - \Ex(B))^2
        & = &   1,002,001 \cdot \frac{2}{3} + 4,008,004 \cdot \frac{1}{3} \\
\Var(A) & = & 2,004,002
\end{eqnarray*}

The variance of Game A is 2 and the variance of Game B is more than
two million!  Intuitively, this means that the payoff in Game A is
usually close to the expected value of \$1, but the payoff in Game B
can deviate very far from this expected value.

High variance is often associated with high risk.  For example, in ten
rounds of Game A, we expect to make \$10, but could conceivably lose
\$20 instead.  On the other hand, in ten rounds of game B, we also
expect to make \$10, but could actually lose more than \$20,000!

\subsection{Why Variance?}

The definition of variance looks rather arbitrary:
\[
\Var(R) = \Ex((R - \Ex(R))^2)
\]
This says that variance is the average \emph{of the square} of the
deviation from the mean.  (For this reason, variance is sometimes
called the ``mean squared deviation''.)  But why bother squaring?  Why
not simply compute the average deviation from the mean?  That is, why
not define variance to be $\Ex(R - \Ex(R))$?

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

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

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

\begin{defin*}
The \emph{standard deviation} of a random variable R is denoted
$\sigma_R$ and defined as the square root of the variance:

\[
\sigma_R = \sqrt{\Var(R)} = \sqrt{\Ex((R - \Ex(R))^2)}
\]      
\end{defin*}

The standard deviation is the square root of the mean of the square of
the deviation, or the ``root mean square'' for short.  It has the same
units (dollars in our example) as the original random variable and as
the mean.  Intuitively, it measures the ``expected (average) deviation
from the mean,'' since we can think of the square root on the outside
as cancelling the square on the inside.
\begin{example}
  The standard deviation of the payoff in Game B is:
  \begin{displaymath}
    \sigma_B  = \sqrt{\Var(B)} = \sqrt{2,004,002} \approx 1416
  \end{displaymath}
  The random variable~$B$ actually deviates from the mean by either
  positive 1000 or negative 2003; therefore, the standard deviation of
  1416 describes the situations reasonably well.
\end{example}
As can be seen in the next Figure~\ref{fig:stdev}, the standard
deviation measures the ``width'' of the main part of the distribution
graph.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/stdev}}
  \caption{The standad deviation of a distribution says how wide the
    ``main'' part of it is.}
  \label{fig:stdev}
\end{figure}



\subsection{An Alternative Definition of Variance}

There is an equivalent way to define the variance of a random variable
that is less intuitive, but often easier to use in both calculations
and proofs.  This alternative definition is stated below in the form of
a theorem.
\begin{theorem}
  \label{th:alt}
  If $R$ is a random variable, then $\Var(R) = \Ex(R^2) - \Ex(R)^2$.
\end{theorem}
Remember that $\Ex(R^2)$ is generally not equal to $\Ex(R)^2$.  The
expected value of a product is the product of the expected values only
for independent variables, and $R$ is generally not independent of
itself.
\begin{proof}
  Write $\mu = \Ex(R)$.  Then
  \begin{eqnarray*}
    \Var(R)
        & = &   \Ex((R - \mu)^2) \\
        & = &   \Ex(R^2 - 2 R \cdot \mu + \mu^2) \\
        & = &   \Ex(R^2) - \Ex(2 R \cdot \mu) + \Ex(\mu^2) \\
        & = &   \Ex(R^2) - 2 \Ex(R) \cdot \mu + \mu^2 \\
        & = &   \Ex(R^2) - 2 \Ex(R)^2 + \Ex(R)^2 \quad
           \text{(definition of $\mu$)}\\
        & = &   \Ex(R^2) - \Ex(R)^2
  \end{eqnarray*}
  The first step uses the definition of variance.  In the second step,
  we multiply out the squared term.  The third step uses linearity of
  expectation.  There are two transformations on the fourth line.  In
  the second term, we pull the constant $2 \mu$ out of the
  expectation.  In the third term, we use the fact that the
  expectation of a constant, namely $\mu^2$, is that constant.  The
  final step is simplification.
\end{proof}
This theorem gives a convenient way to compute the variance of a
random variable: find the expected value of the square and subtract
the square of the expected value.  For example, we can compute the
variance of the outcome of a fair die as follows:
\begin{gather*}
  \Ex(R^2) = \frac{1}{6} (1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2) = \frac{91}{6} \\
  \Ex(R)^2 = \left(3 \frac{1}{2}\right)^2 = \frac{49}{4} \\
  \Var(R)  = \Ex(R^2) - \Ex(R)^2
  = \frac{91}{6} - \frac{49}{4} = \frac{35}{12}
\end{gather*}



\subsection{Computing Variance on the Fly}

Suppose that there is a random variable $R$ defined on a uniform
sample space.  Now someone begins reading off the value of the random
variable at each sample point.  Each value is read exactly once.  How
can we compute the variance?

This problem might come up in practice if we wanted to compute the
variance of a huge set of numbers archived on tapes.  In effect, we
``hear'' each number just once, since we want to avoid multiple passes
through the data!

With our original definition of variance, this problem is difficult.  If
the values of the variable are $x_1, x_2, \ldots x_n$, then we must
compute:
\begin{displaymath}
  \Var(R)
  = \Ex((R - \Ex(R))^2)
  = \frac{(x_1 - \Ex(R))^2 + (x_2 - \Ex(R))^2 + \ldots + (x_n - \Ex(R))^2}{n}
\end{displaymath}
One approach would be to keep a running sum of the values in the
numerator.  When we are given value $x_i$, we compute $(x_i -
\Ex(R))^2$ and add it to the running sum.  At then end, we divide the
running sum by $n$ to obtain the variance.  The problem with this
approach is that we do not know the value of $\Ex(R)$ until after we
have seen all of the data!  Therefore, we need \emph{two} passes, one
to compute $\Ex(R)$ and a second to compute the variance.

A better approach is to use the second definition of variance.  This
requires that we compute:
\begin{eqnarray*}
\Var(R)
        & = & \Ex(R^2) - \Ex(R)^2 \\
        & = & \frac{x_1^2 + x_2^2 + \ldots + x_n^2}{n} -
                \left(\frac{x_1 + x_2 + \ldots + x_n}{n}\right)^2
\end{eqnarray*}
Now the problem is much easier.  We maintain a sum of all numbers seen
and also maintain a sum of the squares of all numbers seen.  That is,
we store two values, $x_1 + x_2 + \ldots + x_i$ and $x_1^2 + x_2^2 +
\ldots + x_i^2$.  Then, when we get the $(i+1)$-st number, we add $x_{i+1}$
to the first sum and $x_{i+1}^2$ to the second sum.  After all numbers
are heard, we can plug these two summations into the definition above
to find the variance.  Now finding the variance requires only a single
pass through the data!


\subsection{A Cute Corollary}

The alternate definition of variance given in Theorem~\ref{th:alt} has
a cute implication:
\begin{corollary}
  If $R$ is a random variable, then $\Ex(R^2) \geq \Ex(R)^2$.
\end{corollary}
\begin{proof}
  We first defined $\Var(R)$ as an average of a squared expression, so
  $\Var(R)$ is non-negative.  Then we proved that $\Var(R) = \Ex(R^2)
  - \Ex(R)^2$.  This implies that $\Ex(R^2) - \Ex(R)^2$ is
  non-negative.  Therefore, $\Ex(R^2) \geq \Ex(R)^2$.
\end{proof}
In words, the expectation of a square is at least the square of the
expectation. The two are equal exactly when the variance is zero:
\begin{displaymath}
  \Ex(R^2) = \Ex(R)^2 \iff \Ex(R^2) - \Ex(R)^2 = 0 \iff \Var(R) = 0
\end{displaymath}



\subsection{Zero Variance}

When does a random variable $R$ have zero variance?  When the random
variable \emph{never} deviates from the mean!
\begin{theorem}
  The variance of a random variable $R$ is zero if and only if $R =
  \Ex(R)$ for all outcomes with positive probability.
\end{theorem}
The final phrase is a technicality; for an outcome with zero
probability, $R$ can take on any value without affecting the variance.
\begin{proof}
  By the definition of variance, $\Var(R) = 0$ is equivalent to the
  condition $\Ex((R - \Ex(R))^2) = 0$.
  
  The inner expression, $(R - \Ex(R))^2$, is always non-negative
  because of the square.  As a result, $\Ex((R - \Ex(R))^2) = 0$ if an
  only if $(R - \Ex(R))^2 = 0$ for all outcomes with positive
  probability.  Now, the conditions $(R - \Ex(R))^2 = 0$ and $R =
  \Ex(R)$ are also equivalent.  Therefore, $\Var(R) = 0$ iff $R =
  \Ex(R)$ for all outcomes with positive probability.
\end{proof}



\subsection{Dealing with Constants}

The following theorem describes how the variance of a random variable
changes when it is scaled or shifted by a constant.
\begin{theorem}
  \label{th:const}
  Let $R$ be a random variable, and let $a$ and $b$ be constants. Then
  \[
  \Var(a R + b) = a^2 \Var(R)
  \]
\end{theorem}
This theorem makes two points.  First, adding a constant $b$ to a
random variable does not affect the variance.  Second, multiplying a
random variable by a constant $a$ changes the variance by an $a^2$
factor.
\begin{proof}
  We will transform the left side into the right side.  The first step
  is to expand $\Var(a R + b)$ using the alternate definition of
  variance.
  \begin{displaymath}
    \Var(a R + b) = \Ex((a R + b)^2) - \Ex(a R + b)^2
  \end{displaymath}
  We will work on the first term and then the second term.   For the
  first term, note that
  \begin{eqnarray*}
    \Ex((aR+b)^2) 
    & = &   \Ex(a^2 R^2 + 2 a b R + b^2) \\
    & = &   (\Ex(a^2 R^2) + \Ex(2 a b R) + \Ex(b^2))\\
    & = &   (a^2 \Ex(R^2) + 2 a b \Ex(R) + b^2)
  \end{eqnarray*}
  In the first step, we multiply out the squared expression in the
  first term.  The second step uses linearity of expectation, and in
  the third step, we pull all constants out of expectations.  Now we
  work on the second term:
  \begin{eqnarray*}
    \Ex(aR+b)^2
    & = &  (a \Ex(R) + b)^2 \\
    & = &  (a^2 \Ex(R)^2 + 2 a b \Ex(R) + b^2)
  \end{eqnarray*}
  In the first step, we pull the constants out of the expectation.  In
  the second step, we multiply out the square.

  Finally, we substract that (expanded) second term from the first.
  Cancelling terms, we find:
  \begin{eqnarray*}
    \Var(a R + b)
    & = &   a^2 \Ex(R^2) - a^2 \Ex(R)^2 \\
    & = &   a^2 (\Ex(R^2) - \Ex(R)^2) \\
    & = &   a^2 \Var(R)
  \end{eqnarray*}
\end{proof}
A similar rule holds for the standard deviation when a random variable
is adjusted by a constant.  Recall that standard deviation is the
square root of variance.  Therefore, adding a constant $b$ to a random
variable does not change the standard deviation.  Multiplying a random
variable by a constant $a$ multiplies the standard deviation by $a$.



\subsection{Variance of a Sum}

Earlier, we claimed that for independent random variables, the
variance of a sum is the sum of the variances.  This is stated formally
and proved below.
\begin{theorem}
  If $R_1$ and $R_2$ are independent random variables, then
  \[
  \Var(R_1 + R_2) = \Var(R_1) + \Var(R_2)
  \]
\end{theorem}
\begin{proof}
  We will transform the left side into the right side.  We begin by
  applying the alternate definition of variance.
  \begin{displaymath}
    \Var(R_1 + R_2) = \Ex((R_1 + R_2)^2) - \bigl(\Ex(R_1 + R_2)\bigr)^2
  \end{displaymath}
  We will work on the first term and then the second term separately.
  For the first term, note
  \begin{eqnarray*}
    \Ex((R_1+R_2)^2)
    & = &   \Ex(R_1^2 + 2 R_1 R_2 + R_2^2) \\
    & = &   (\Ex(R_1^2) + \Ex(2 R_1 R_2) + \Ex(R_2^2)) \\
    & = &   (\Ex(R_1^2) + 2 \Ex(R_1) \Ex(R_2) + \Ex(R_2^2)) 
  \end{eqnarray*}
  First, we multiply out the squared expression.  The second step uses
  linearity of expectation.  In the last step, we break the
  expectation of the product $R_1 R_2$ into a product of expectations;
  this is where we use the fact that $R_1$ and $R_2$ are independent.
  Now we work on the second term.
  \begin{eqnarray*}
    \bigl(\Ex(R_1+R_2)\bigr)^2
    & = & (\Ex(R_1) + \Ex(R_2))^2 \\
    & = & (\Ex(R_1)^2 + 2 \Ex(R_1) \Ex(R_2) + \Ex(R_2)^2) \\
  \end{eqnarray*}
  The first step uses linearity of expectation, and in the second step
  we multiply out the squared expression.  Now we subtract the
  (expanded) second term from the first. Cancelling and rearranging
  terms, we find that
  \begin{eqnarray*}
    \Var(R_1 + R_2)
    & = &   (\Ex(R_1^2) - \Ex(R_1)^2) +
    (\Ex(R_2^2)) - \Ex(R_2)^2) \\
    & = &   \Var(R_1) + \Var(R_2)
  \end{eqnarray*}
\end{proof}
The independence condition in the theorem is necessary.  If we ignored
this condition and took $R_1$ and $R_2$ to be the same random
variable, then we would conclude that $\Var(R + R) = \Var(R) +
\Var(R)$.  However, by Theorem~\ref{th:const}, the left side is equal
to $4 \Var(R)$, whereas the right side is $2 \Var(R)$.  Therefore, if
we remove the condition that $R_1$ and $R_2$ be independent, then the
theorem is false.

The preceding theorem extends to a collection of \emph{pairwise
  independent} random variables.  Recall that pairwise independence is
actually a much weaker condition than mutual independence.
\begin{theorem}
  \label{th:varsum}
  If $R_1, R_2, \ldots, R_n$ are pairwise independent random variables,
  then
  \[
  \Var(R_1 + R_2 + \ldots + R_n) = \Var(R_1) + \Var(R_2) + \ldots + \Var(R_n)
  \]
\end{theorem}
\begin{proof}
  We use the formula $\Var(R) = \Ex(R^2) - (E(R))^2$.
  \begin{displaymath}
    \Ex\Biggl(\biggl(\sum_{i=1}^n R_i\biggr)^2\Biggr)
    = \Ex\biggl(\sum_{i=1}^n \sum_{j=1}^n R_i R_j\biggr)
    = \sum_{i=1}^n \sum_{j=1}^n \Ex(R_i R_j).
  \end{displaymath}
  If $i = j$, $\Ex(R_i R_j) = \Ex(R_i^2)$, and if $i \neq j$, $\Ex(R_i
  R_j) = \Ex(R_i) \Ex(R_j)$ since $R_1, R_2, \ldots, R_n$ are pairwise
  independent.
  \begin{displaymath}
    \Biggl(\Ex\biggl(\sum_{i=1}^n R_i\biggr)\Biggr)^2
    = \biggl(\sum_{i=1}^n Ex(R_i)\biggr)^2
    = \sum_{i=1}^n \sum_{j=1}^n \Ex(R_i) \Ex(R_j).
  \end{displaymath}
  Putting the pieces together, the terms containing $\Ex(R_i)
  \Ex(R_j)$ cancel, which gives
  \begin{displaymath}
    \Var\biggl(\sum_{i=1}^n R_i\biggr)
    = \sum_{i=1}^n \Ex(R_i^2) - \sum_{i=1}^n \bigl(\Ex(R_i)\bigr)^2
    = \sum_{i=1}^n \Var(R_i).
  \end{displaymath}
\end{proof}



\subsection{Variance of a Binomial Distribution}

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

We can think of $R$ as the sum of $n$ independent Bernoulli variables.
For example, we can regard $R$ as the number of heads that come up
when we toss $n$ independent coins, where each coin comes up heads
with probability $p$.  Formally, we can write $R = R_1 + R_2 + \cdots
+ R_n$ where
\begin{displaymath}
  R_i = \begin{cases}
    1 & \text{with probability $p$,} \\
    0 & \text{with probability $1-p$.}
  \end{cases}
\end{displaymath}
Now we can compute the variance of the binomially distributed
variable~$R$.
\begin{eqnarray*}
\Var(R)
        & = &   \Var(R_1) + \Var(R_2) + \ldots + \Var(R_n) \\
        & = &   n \Var(R_i) \\
        & = &   n (\Ex(R_i^2) - \Ex(R_i)^2) \\
        & = &   n (\Ex(R_i) - \Ex(R_i)^2) \\
        & = &   n (p - p^2)
\end{eqnarray*}
The first equation uses Theorem~\ref{th:varsum}, and the second uses
the fact that all variables $R_i$ are identically distributed and
therefore have the same variance.  We then expand $\Var(R_i)$ using
the alternate definition of variance.  In the fourth step, we observe
that $R_i^2$ and $R_i$ are the same random variable.  This is always
true for a Bernoulli random variable, because $0^2 = 0$ and $1^2 = 1$.
The last step uses the fact that the expectation of a Bernoulli
variable is the probability that the variable is 1; in this case,
$R_i$ is 1 with probability $p$.

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

More generally, if we recall that a binomial distribution with
parameters $n$ and $p$ has mean $\mu=np$, we see that we can write the
standard deviation as $\sqrt{\mu(1-p)}$.  Thus, unless $p$ is huge, we
can estimate the standard deviation as the square root of the mean.
Notice that as the mean grows, so does the standard deviation.  But
the standard deviation as a \emph{fraction} of the mean goes to 0.
Rephrasing, we see that as the mean grows, the deviation we expect
becomes negligible compared to the mean: the distribution gets
narrower.

\section{Chebyshev's Theorem}

Markov's Theorem uses too little information about a random variable
to always give good bounds on deviation from the mean.  With more
information, we can obtain tighter bounds. 
Chebyshev's Theorem takes the variance into account.

\subsection{Theorem statement and proof}

%Chebyshev's Theorem formalizes the intuition that the variance
%describes the tendency of a random variable to deviate from the mean.  
\begin{theorem}
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\Pr(|R - \Ex(R)| \geq x) \leq \frac{\Var(R)}{x^2}
\]
\end{theorem}
\begin{proof}
The proof uses Markov's Theorem.
Note that the event $|R - \Ex(R)| \geq x$ is the same as the event $(R
- \Ex(R))^2 \geq x^2$, since the latter inequality is obtained by
squaring both sides of the former and both sides of the former are
positive.  Therefore, these two events have equal probability:
\begin{eqnarray*}
\Pr(|R - \Ex(R)| \geq x)
        & = &   \Pr((R - \Ex(R))^2 \geq x^2) \\
        &\leq&  \frac{\Ex((R - \Ex(R))^2)}{x^2} \\
        & = &   \frac{\Var(R)}{x^2}
\end{eqnarray*}
We can apply Markov's Theorem on the second line, since the random
variable $(R - \Ex(R))^2$ is non-negative.  The third step follows
from the definition of variance.
\end{proof}
There is a nice reformulation of Chebyshev's Theorem in terms of
standard deviation.
\begin{corollary}
  \label{cor:cheby}
  Let $R$ be a random variable, and let $c$ be a positive real number.
  \[
  \Pr(|R - \Ex(R)| \geq c \sigma_R) \leq \frac{1}{c^2}
  \]
\end{corollary}
\begin{proof}
  Substituting $x = c \sigma_R$ in Chebyshev's Theorem gives:
  \begin{displaymath}
    \Pr(|R - \Ex(R)| \geq c \sigma_R)
    \leq
    \frac{\Var(R)}{(c \sigma_R)^2}
    =
    \frac{1}{c^2}\,.
  \end{displaymath}
  The last equality holds because variance is the square of standard
  deviation; in particular, $\Var(R) = \sigma_R^2$.
\end{proof}



\subsection{Example}

Suppose that the average \IQ. is 100 and the standard deviation is 10.
How rare is an \IQ. of 200 or more?

Let the random variable $R$ be the \IQ. of a random person.  We are
supposing that $\Ex(R) = 100$ and $\sigma_R = 10$.  Furthermore, let's
assume that everyone has an \IQ. that is positive.  We want to compute
$\Pr(R \geq 200)$.

Since $R$ is non-negative, we can get an upper bound using Markov's
Theorem as shown below.
\begin{displaymath}
  \Pr(R \geq 200) \leq \frac{\Ex(R)}{200} = \frac{100}{200} = \frac{1}{2}\,.
\end{displaymath}
Markov's Theorem says that at most half of the people have \IQ. 200 or
more; this sounds like a very loose upper bound!  Suppose that we now
apply Chebyshev's Theorem to the same problem.
\begin{displaymath}
  \Pr(R \geq 200) = \Pr(|R - 100| \geq 100) \leq \frac{\Var(R)}{100^2}
  = \frac{10^2}{100^2} = \frac{1}{100}\,.
\end{displaymath}
The purpose of the first step is to express the desired probability in
the form required by Chebyshev's Theorem.  (There is equality because
$R$ is positive.)  We actually apply Chebyshev's Theorem in the second
step.  The remaining work is substitution and simplification.

Chebyshev's Theorem says that at most one person in a hundred has an
\IQ. of 200 or more.  Chebyshev's Theorem gives a much tighter bound
because it uses additional information, the variance of $R$.

Where did we get the assumption of a standard deviation of 10?  Well,
if IQ is any kind of binomial distribution, we can use the intuition
that the standard deviation is the square root of the mean.

\subsection{A One-Sided Bound}

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

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

The error in this argument is that a random variable may be more
likely to deviate above the mean than below.  For example, in the \IQ.
question, some people deviate 100 points above the mean; that is,
there are people with \IQ. greater than 200.  However, by assumption
everyone has a positive \IQ.; no one deviates 100 points below the
mean.  (The argument above is correct, however, for a probability
distribution function that is symmetric about the mean.)

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



\subsubsection{Exam Problems}

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

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

\section{Laws of Large Numbers}

Using our few basic results on variance, we can finally prove a
theorem that justifies our intuition about the expectation being the
``average'' behavior of a random experiment.  This theorem is known as
the \emph{weak law of large numbers:}

\begin{theorem}
Let $R_1,R_2,\ldots$ be independent random variables, all drawn from
the same distribution with finite mean $\mu$ and finite variance
$\sigma^2$.  Let 
\[
S_n = \frac1n \sum_{i=1}^n R_i
\]
Then for any $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty} \Pr (| S_n - \mu| \ge \epsilon) = 0.
\]
\end{theorem}

Let's translate this into English.  $S_n$ is the average of the first
$n$ random variables (and is itself a random variable).  So the
probability we are looking at is the probability that the average
value $S_n$ deviates be more than $\epsilon$ from the expected value
of the random variable.  And the theorem says that for sufficiently
large $n$, this probability becomes tiny.

Turning the theorem around, we see that if we want to estimate the
expectation of a random variable, we can do so by averaging a number
of samples.  As the number of samples grows, we approach (but never
reach) certainty that the estimate will be accurate to within
$\epsilon$.

\begin{proof}
  The proof of this theorem applies Chebyshev's inequality to the
  random variable $S_n$.  To do that, we need to understand the mean
  and the variance of $S_n$.  The key difference between the
  expectation and the variance is as follows: as $n$ goes up, the
  expectation is unchanged but the variance \emph{drops}.  This will
  let us apply Chebyshev's theorem.

Lets begin with the mean.  This follows from linearity of expectation:
\begin{align*}
\Ex(S_n) &= \Ex(\frac1n\sum_{i=1}^n R_i)\\
&= \frac1n \sum_{i=1}^n \Ex(R_i)\\
&= \frac1n \sum_{i=1}^n \mu\\
&= \frac1n (n\mu)\\
&= \mu
\end{align*}

Now let's look at the variance.  Because the random variables in the
sum are independent, we can apply linearity of variance:
\begin{align*}
\Var(S_n) &= \Var(\frac1n\sum_{i=1}^n R_i)\\
&= \frac1{n^2} \sum_{i=1}^n \Var(R_i)\\
&= \frac1{n^2} \sum_{i=1}^n \sigma^2\\
&= \frac1{n^2} (n\sigma^2)\\
&= \sigma^2/n
\end{align*}

Note the key difference between the expectation and the variance: as
$n$ goes up, the expectation is unchanged but the variance
\emph{drops}.  This lets us apply Chebyshev's theorem.  That theorem
says that 
\begin{align*}
\Pr(|S_n-\Ex(S_n)| \ge \epsilon) &\le \frac{\Var(S_n)}{\epsilon^2}\\
\Pr(|S_n-\mu| \ge \epsilon) &\le \frac{\sigma^2/n}{\epsilon^2}\\
                            &=\frac{\sigma^2}{\epsilon^2 n}
\end{align*}
The final bound is $O(1/n)$, so has limit 0 as $n\rightarrow\infty$.
\end{proof}

Notice the key points in the proof: we rely on the finite variance of
the distribution, and rely on the fact that our sum involves
\emph{independent} random variables, so we can apply linearity to our
variance calculation.  In fact, the theorem even holds when the
variance is not finite, but the proof is much messier.

This theorem is known as the \emph{weak} law of large numbers, 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.


\subsection{The Central Limit Theorem}

There's an even stronger result known as the central limit theorem
that not only shows convergence to the mean but also measures
\emph{how much divergence} from the mean will occur:

\begin{definition}
The \emph{normal density function} is the function 
\[
n(x) = \frac{1}{\sqrt{2\pi}}e^{-\frac12x^2}
\]
and the \emph{normal distribution function} is its integral
\[
N(x) = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^x e^{-\frac12y^2}dy
\]
\end{definition}

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.

\begin{theorem}
Let $R_i$ and $S_i$ be defined as in the weak law above.  Consider
the ``scaled'' random variable
\[
T_n = \sqrt{n}\cdot\frac{S_n-\mu}{\sigma}.
\]
Then
\[
\lim_{n\rightarrow\infty} \Pr(T_n < \beta)= N(\beta)
\]
\end{theorem}

Again, this theorem requires some interpretation.  In the law of large
numbers, we saw that $S_n$ had mean $\mu$, so that $S_n-\mu$ has mean
0.  We also saw that $S_n$ had variance $\sigma^2/n$, which means that
$\sqrt{n}(S_n-\mu)/\sigma$ has variance 1.  In other words, $T_n$ is
just $S_n$ scaled so that its mean is 0 and its variance is 1.

The theorem then measures the probability of the event $T_n < \beta$.
This is just the cumulative distribution function for the random
variable $T_n$.  So the theorem is telling us what the distribution of
the random variable $T_n$ looks like.

The central limit theorem says that \emph{regardless} of the underlying
distribution of the variables $R_i$, so long as they are independent,
the distribution of $T_n$ converges to the same, normal distribution.
It is therefore unsurprising that this normal distribution (also known
as a \emph{Gaussian} distribution) plays a critical 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.

The proof of this result is relatively complex, requiring the use of
\emph{exponential generating functions}.  So we will skip it.  We will
see a closely related technique applied in the proof of the Chernoff
bound later.

\forlecture{
\section{Chernoff Bounds}


\subsection{Deviation of an Unbiased Binomial Distribution}

Chebyshev's Theorem applies to any random variable.  However, for a
specific distribution, we can sometimes prove a stronger bound on
deviation from the mean.  For example, a very strong bound is possible
for an unbiased binomial distribution.
\begin{fact}
  \label{fct:binom}
  For a random variable $R$ with an unbiased binomial distribution
  \[
  \Pr(R - \Ex(R) \geq c \sigma_R) < e^{-c^2/2}
  \]
\end{fact}
Note that the bound in Chebyshev's Theorem is polynomial
($\frac{1}{c^2}$), but the bound above is exponential ($e^{-c^2/2}$).

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.

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 - \Ex(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
Corollary~\ref{cor:cheby1} is $\frac{1}{37}$.

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

Now let $A_1, A_2, \ldots, A_N$ be mutually independent events over
the same sample space.  Let the random variable $T$ be the number of
these events that occur.  What is the probability that at least $k$
events occur?  That is, what is $\Pr(T \geq k)$?  (This generalizes
the question asked previously about 1 event to $k$ events rather than
$1$; however, note that we have also added the assumption of mutual
independence.)  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.  The
first example is a special case in that all events $A_i$ have equal
probability; that is, the coin is as likely to come up heads on one
flip as on another.  In particular, suppose that the coin comes up
heads with probability $p$.  Then all events $A_i$ have probability
$p$, and $T$ has the now-familiar binomial distribution:
\[
\Pr(T = k) = \binom{n}{k} p^k (1-p)^{n-k} = f_{n,p}(k)
\]
We studied the binomial distribution extensively two weeks ago.
Therefore, we already have an answer to the question posed above in
the special case where all events $A_i$ have equal probability.

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$.  This section focuses on questions of this more general
type 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 $\frac{N}{2}$ heads.  The Chernoff Bound implies that for
sufficiently large $N$, the number of heads is almost always not much
greater than $\frac{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{The theorem}

The theorem is stated below 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]
  Let $T_1, T_2, \ldots, T_N$ be mutually independent Bernoulli
  variables, and let $T = T_1 + T_2 + \ldots + T_N$.  Then for all $c
  \geq 1$, we have
  \[
  \Pr(T \geq c \Ex(T)) \leq e^{- \alpha c \Ex(T)}
  \]
  where $\alpha = \ln c + \frac{1}{c} - 1$.
\end{theorem}
%(A similar bound holds for $\Pr(T \leq c \Ex(T))$, where $c < 1$; we
%omit this here.)
%[[[What's the exact statement of this?]]]
The formula for $\alpha$ is a little awkward.  The situation is
simpler when $c = e = 2.718\ldots$, as in the following corollary.
\begin{corollary}
  \label{cor:ebound}
  Let $T_1, T_2, \ldots, T_N$ be mutually independent Bernoulli
  variables, and let $T = T_1 + T_2 + \ldots + T_N$.
  \[
  \Pr(T \geq e \Ex(T)) \leq e^{- \Ex(T)}
  \]
\end{corollary}
\begin{proof}
  Setting $c = e$ in the Chernoff Bound gives:
  \begin{displaymath}
    \Pr(T \geq e \Ex(T))
    \leq e^{- (\ln e + \frac{1}{e} - 1) e \Ex(T)}
    = e^{- \Ex(T)}.
  \end{displaymath}
\end{proof}
We will prove the Chernoff Bound shortly.  First, let's see an
example of how it is used.



\subsection{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 +
\ldots + 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 $\Ex(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\Ex(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 constant $\alpha=\ln c +
\frac1c-1$ in the exponent?  First, note that when $c=1$, the constant
$\alpha=0$: the Chernoff bound cannot say anything useful about the
probability of exceeding the mean.  However, the constant is
increasing with $c>1$: the derivative with respect to $c$ is
\[
\frac{d\alpha}{dc} = \frac{1}{c}-\frac{1}{c^2} > 0
\]
when $c>1$.  Therefore, for \emph{any} $c>1$, you get some $\alpha>0$
in the exponent.  

In particular, consider the case of $c$ close to 1; let's say
$c=1+\epsilon$.  Then a Taylor expansion of $\alpha$ gives:
\begin{align*}
  \alpha &= \ln(1+\epsilon) + \frac{1}{1+\epsilon}-1\\
  &= (\epsilon-\epsilon^2/2+\epsilon^3/3-\cdots) +
  (1-\epsilon+\epsilon^2-\epsilon^3+\cdots) -1\\
  &= \frac12\epsilon^2-\frac23\epsilon^3-\frac34\epsilon^4+\cdots
\end{align*}
In particular, for very small $\epsilon$, we have 
$\alpha \approx \epsilon^2/2$.
In fact one can prove the following:
\begin{lemma}
  For any $\epsilon < 1$, 
  $\Pr(T \geq (1+\epsilon \Ex(T)) < e^{-\epsilon^2 \Ex(T)/3}$.
\end{lemma}
In other words, the probability of deviation by $\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{\Ex(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$,
our roughly the square root of the expectation. 



\subsection{Proof of the Chernoff Bound}

The Chernoff Bound has the most difficult proof of the course.
The intuition is in the first two steps; the rest is algebraic
chicanery.
\begin{displaymath}
  \Pr(T \geq c \Ex(T)) = \Pr(c^T \geq c^{c \Ex(T)})
  \leq \frac{\Ex(c^T)}{c^{c \Ex(T)}}
\end{displaymath}
The first step is a shocker; we raise both sides of the inequality in
the probability to the power $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 $\Ex(c^T)$.  This leads to a lot of
algebra.
\begin{eqnarray*}
\Ex(c^T)
        & = &   \Ex(c^{T_1 + T_2 + \ldots + T_N}) \\
        & = &   \Ex(c^{T_1}) \cdot \Ex(c^{T_2}) \cdots \Ex(c^{T_N}) \\
        & = &   \prod_{i=1}^N \Ex(c^{T_i})
\end{eqnarray*}
In the first step, we expand $T$ according to its definition.  The
second step is where we use the crucial independence assumption: since
the variables $T_i$ are independent, the variables $e^{cT_i}$ are also
independent, which means the expectation of the product is the product
of the expectations.  To simplify the product, we can rewrite
$\Ex(c^{T_i})$ as follows.
\begin{eqnarray*}
\Ex(c^{T_i})
        & = &   c^1 \Pr(T_i = 1) + c^0 \Pr(T_i = 0) \\
        & = &   c^1 \Pr(T_i = 0) + c^0 (1 - \Pr(T_i = 1)) \\
        & = &   1 + (c - 1) \Pr(T_i = 0) \\
        & \leq &
                e^{(c-1) \Pr(T_i = 1)} \\
        & = &
                e^{(c-1) \Ex(T_i)}
\end{eqnarray*}
The first step uses the definition of expected value.  The second step
uses the fact that the probability of an event is one minus the
probability of the complement.  The third step is simplification.  The
fourth line uses the inequality $1 + x \leq e^x$ which follows from
the Taylor series $e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} +
\ldots$.  The last line relies on the fact that the expected value of
a Bernoulli variable is equal to the probability that the variable is
1.

We can now substitute this bound on $\Ex(c^{T_i})$ into the product for
$\Ex(c^T)$.  The motivation for the approximation $1 + x \leq e^x$
used above is that terms of the form $e^x$ are easy to work with
inside a product.
\begin{eqnarray*}
\Ex(c^T)
        &\leq&  \prod_{i=1}^N e^{(c-1) \Ex(T_i)} \\
        & = &   e^{\sum_{i=1}^N (c-1) \Ex(T_i)} \\
        & = &   e^{(c-1) \sum_{i=1}^N \Ex(T_i)} \\
        & = &   e^{(c-1) \Ex\left(\sum_{i=1}^N T_i\right)} \\
        & = &   e^{(c-1) \Ex(T)}
\end{eqnarray*}
In the first step, we substitute the bound on $\Ex(c^{T_i})$ into the
expression for $\Ex(c^T)$.  The second equality follows from an
exponent rule.  In the third step, we pull the constant $(c-1)$ out of
the summation.  The fourth step uses linearity of expectation, and the
last step uses the definition of the random variable $T$.

Now we can substitute this bound on $\Ex(c^T)$ into the expression
derived from Markov's Theorem.  All of the remaining steps are
simplifications.
\begin{eqnarray*}
\Pr(T \geq c \Ex(T))
        & \leq &        \frac{e^{(c-1) \Ex(T)}}{c^{c \Ex(T)}} \\
        & = &   e^{(c-1) \Ex(T) - c \ln c \Ex(T)} \\
        & = &   e^{-(\ln c + \frac{1}{c} - 1) c \Ex(T)} \\
        & = &   e^{-\alpha c \Ex(T)} \quad \quad \text{ where }
                        \alpha = \ln c + \frac{1}{c} - 1
\end{eqnarray*}



\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 + \ldots + 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, $\Ex(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 $\Ex(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 + \frac{1}{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.

Previosuly, 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, however.  One
problem is that calls 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{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.  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.

\subsection{Derivation}

Let's consider a particular example.  Consider a system such as a
computer that has a certain chance of failure at any given time.  We
are told that on average this system sees $\lambda$ failures per year,
and want to model the probability distribution associated with the
failure time of the system.  A particularly simple model is to break
time up into small intervals of some length $\delta$, and to suppose
that in each interval, 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 in each interval, and the system fails when
the coin comes up heads.

Specifically, lets consider a time period of length $t$ (in which we
expect to see $\lambda t$ failures).  Let us break it up into $n$
intervals of length $t/n$.  If we declare a failure probability of $p$
in each interval, then the expected number of failures over our $n$
intervals will be $np$.  So in order to meet our goal of modelling
$\lambda t$ failures in time $t$, we set $np=\lambda t$, or $p=\lambda
t/ n$.

Now we can determine the probability that no failures have occurred by
time $t$ (small interval number $n$).  Let $S_i$ denote the event that
the system stays working in the $i^{th}$ interval, assuming that it
was working until then.  Then the probability that the system is
still working at interval $n$ is just the probability that it has 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 t/n)^{n}.
\end{align*}
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 class, and simply forge ahead.

\subsection{Expectation of the Distribution}

Given our model, it is natural to ask about the expected time $E[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, $E[Y] = \sum_k \Pr[Y \ge k]$, it turns
out that
\begin{align*}
E[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
$E[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
distribution 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,\ldots,X_n$ are independent exponential random variables with
rates $\lambda_1,\ldots,\lambda_n$, then $\min X_1,\ldots,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*}
E[Y_2] &= E[Y_1]+E[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$.


\section{The Poisson Approximation}

We've used the exponential distribution to study the time of first
failure of a system; a similar approach can let us study the
distribution of \emph{number of failures} of the system over a
particular time interval.  The same analysis can be applied to model,
for example, the number of decaying particles in a radioactive sample
in a given time interval, or the number of communication packets
arriving at a computer in a given time interval.

We've worked with the binomial distribution, which measures the
probability of $k$ special outcomes occur in a sequence of $n$
trials.  For the purpose of this topic we will calls those events
``arrivals.''  If the trials are independent, and each results in an
arrival with probability $p$, then the probability of $k$ arrivals is
\[
\binom{n}{k}p^k(1-p)^{n-k}.
\]
This is a somewhat messy quantity to work with.  There is a nice
approximation that can be worked out when $n$ is large.  In
particular, we can combine the following two approximations:
\begin{align*}
\binom{n}{k} &\approx \frac{n^k}{k!}\\
(1-p)^{t} \approx e^{-tp}\\
\intertext{to rewrite}\\
\binom{n}{k}p^k(1-p)^{n-k} &\approx e^{-np}\frac{(np)^k}{k!}
\end{align*}
Note that the quantity $np$ is simply the expected number of arrivals
in the distribution.

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 our second up
into tiny intervals---say $t/\delta$ tiny intervals of length
$\delta$---and declare that in each interval, a packet arrives with
probability $\lambda\delta$ (this gives the right expected number of
arrivals).  Under this model, the number of intervals $X$ in which a
packet actually arrives has a binomial distribution:\footnote{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.}
\begin{align*}
\Pr[X=k] &=
\binom{\lambda t/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{t/\delta-k}\\
\end{align*}
If we now allow $\delta$ to become infinitesimally small (while
holding $k$ fixed) we can make use of two approximations:
\begin{align*}
\binom{\lambda t/\delta}{k} &\approx \frac{(t/\delta)^k}{k!}\\
(1-\lambda\delta)^{1/\delta} &\approx e^{-\lambda}.
\end{align*}
Plugging these two approximations into our formula yields
\begin{align*}
\Pr[X=k] &=
\binom{t/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{t/\delta-k}\\
&=\binom{t/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{(t-\delta k)/\delta}\\
&\approx \frac{(t/\delta)^k}{k!} (\lambda\delta)^k e^{-\lambda t}\\
&= e^{-\lambda t}\frac{(\lambda t)^k}{k!}
\end{align*}
This probability distribution is known as the \emph{Poisson
  distribution}.  When talking as we are now about arrivals in a
system, we refer to the model as a \emph{Poisson process}.

Again we can sanity check our distribution.  The probability values
should sum to 1 over all $k$, and they do:
\begin{align*}
\sum \Pr[X=k] &= \sum  e^{-\lambda t}\frac{(\lambda t)^k}{k!}\\
&= e^{-\lambda t} \sum \frac{(\lambda t)^k}{k!}\\
&= e^{-\lambda t}e^{\lambda t}
\end{align*}
based on the Taylor expansion for $e^{\lambda t}$.

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

\end{breakperiods}
\end{document}
