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

\lectureformat

\showsolutionstrue

\newcommand{\expcond}[2]{\expect{#1\mid#2}}
\newcommand{\range}[1]{\mathop{\textup{range}}\nolimits(#1)}
\newcommand{\sspace}{\mathcal{S}}
\newcommand{\IQ}{I.Q.\@\xspace}
\newcommand{\ok}{\marginpar{OK?}}

\begin{document}
\lecture{notes13}{Variance and Deviation from the Mean}{November 26,
2001}{\stamp}

\section{Infinite Linearity of Expectation}

We know that expectation is linear over finite sums.  It's useful to
extend this result to infinite summations.  This works as long as we avoid
sums whose values may depend on the order of summation.

\begin{theorem}\label{linexp} [Linearity of Expectation]
Let $R_0$, $R_1$, \dots, be random variables such that
\[
\sum_{i = 0}^\infty \expect{\abs{R_i}}
\]
converges.  Then
\[
   \expect{\sum_{i = 0}^\infty R_i} = \sum_{i = 0}^\infty \expect{R_i}.
\]
\end{theorem}

\begin{proof}
We leave it to the reader to verify that, under the given convergence
hypothesis, all the sums in the following derivation are absolutely
convergent, which justifies rearranging them as follows:
\begin{align*}
\sum_{i=0}^\infty \expect{R_i}
    &= \sum_{i=0}^\infty \sum_{s \in \sspace} [R_i(s) \cdot \prob{s}] \\
    &= \sum_{s \in \sspace} \sum_{i=0}^\infty [R_i(s) \cdot \prob{s}] \\
    &= \sum_{s \in \sspace} \left[ \sum_{i=0}^\infty R_i(s) \right] \cdot \prob{s} \\
    &= \sum_{s \in \sspace} \left[ [\sum_{i = 0}^\infty R_i](s) \right] \cdot \prob{s} \\
    &= \expect{\sum_{i = 0}^\infty R_i}.
\end{align*}
\end{proof}

Note that the finite linearity of expectation we established in Notes 12
follows as a special case of Theorem~\ref{linexp}: since $\expect{R_i}$ is
finite, so is $\expect{\abs{R_i}}$, and therefore so is their sum for $0
\leq i \leq n$.  Hence the convergence hypothesis of Theorem~\ref{linexp}
is trivially satisfied if there are only finitely many $R_i$'s.

\textbf{Exercise:} Show that linearity of expectation fails for the sum of
two variables, one with expectation $+\infty$ and the other with
$-\infty$.

\subsection{A Paradox}
One of the simplest casino bets is on ``red'' or ``black'' at the roulette
table.  In each play at roulette, a small ball is set spinning around a
roulette wheel until it lands in a red, black, or green colored slot.
The payoff for a bet on red or black matches the bet; for example, if you bet
$\$10$ on red and the ball lands in a red slot, you get back your original
$\$10$ bet plus another matching $\$10$.

In the US, a roulette wheel has 2 green slots among 18 black and 18 red
slots, so the probability of red is $p::= 18/38 \approx 0.473$.  In
Europe, where roulette wheels have only 1 green slot, the odds for red
are a little better ---that is, $p = 18/37 \approx 0.486$---but still less
than even.  To make the game fair, we might agree to ignore green, so that
$p = 1/2$.

There is a notorious gambling strategy which seems to guarantee a profit
at roulette: bet $\$10$ on red, and keep doubling the bet until a red
comes up.  This strategy implies that a player will leave the game as a
net winner of $\$10$ as soon as the red first appears.  Of course the
player may need an awfully large bankroll to avoid going bankrupt before
red shows up---but we know that the mean time until a red occurs is $1/p$,
so it seems possible that a moderate bankroll might actually work out.
(In this setting, a ``win'' on red corresponds to a ``failure'' in a
mean-time-to-failure situation, cf. Notes 12.)  In any case, we
won't worry about bankruptcy and will assume we can keep doubling our bets
indefinitely until a red comes up.

Suppose we have the good fortune to gamble against a fair roulette wheel.
In this case, our expected win on any spin is zero, since at the $i$th
spin we are equally likely to win or lose $2^{i-1} 10$  dollars.
So our expected win after any finite number of spins remains zero, and
therefore our expected win using this gambling strategy is zero.  This
is just what we should have anticipated in a fair game.

But wait a minute.  As long as there is a fixed, positive probability of
red appearing on each spin of the wheel---even if the wheel is
unfair---it's \emph{certain} that red will eventually come up.  So with
probability one, we leave the casino having won $\$10$, and our expected
dollar win is obviously $\$10$, not zero!

Something's wrong here.  What?

\solution{The expected amount won is indeed $\$10$.

The argument claiming the expectation is zero is flawed by an invalid use
of linearity of expectation for an infinite sum.  To pinpoint this flaw,
let's first make the sample space explicit: a sample point is a sequence
$B^nR$ representing a run of $n \geq 0$ black spins terminated by a red
spin.  Since the wheel is fair, the probability of $B^nR$ is $2^{-(n+1)}$.

Let $C_i$ be the number of dollars won on the $i$th spin.  So 
$C_i = 2^{i-1} 10$ 
when red comes up for the first time on the $i$th spin, that is, at
precisely one sample point, namely $B^{i-1}R$.  Similarly, 
$C_i = - 2^{i-1} 10$ 
when the first red spin comes up after the $i$th spin, namely, at the
sample points $B^nR$ for $n \geq i$.  Finally, we will define $C_i$ by
convention to be zero at sample points in which the session ends before the
$i$th spin, that is, at points $B^nR$ for $n < i-1$.

The dollar amount won in any gambling session is the value of the sum
$\sum_{i = 1}^\infty C_i$.  At any sample point $B^nR$, the value of this
sum is
\[-(1 + 2 + 2^2 + \dots + 2^{n - 1}) \cdot 10 + 2^n \cdot 10 = 10,
\]
which trivially implies that its expectation is ten as well.  That is, the
amount we are certain to leave the casino with, as well as expectation of
the amount we win, is $\$10$.

Moreover, our reasoning that $\expect{C_i} = 0$ is sound, so 
\[
\sum_{i = 1}^\infty \expect{C_i} = \sum_{i = 1}^\infty 0 = 0.
\]

The flaw in our argument is the claim that, since the expectation at each
spin was zero, therefore the final expectation would also be zero.
Formally, this corresponds to concluding that
\[
\expect{\mbox{amount won}}  =  \expect{\sum_{i = 1}^\infty C_i}
  =  \sum_{i = 1}^\infty \expect{C_i} = 0.
\]
The flaw lies exactly in the second equality.  This is a case where
linearity of expectation fails to hold---even though both $\sum_{i =
1}^\infty \expect{C_i}$ and $\expect{\sum_{i = 1}^\infty C_i}$ are
finite---because the convergence hypothesis needed for linearity is false.
Namely, the sum
\[
\sum_{i = 1}^\infty \expect{\abs{C_i}}
\]
does not converge.  In fact, the expected value of $\abs{C_i}$ is $10$
because $\abs{C_i} = 2^{i-1} 10$  with probability $2^{-i}$ and
otherwise is zero, so this sum rapidly approaches infinity.

Probability theory truly leads to this apparently paradoxical conclusion: a
game allowing an unbounded---even though always finite---number of ``fair''
moves may not be fair in the end.  In fact, our reasoning leads to an even
more startling conclusion: even against an \emph{unfair} wheel, as long as
there is some fixed positive probability of red on each spin, we are
certain to win $\$10$!

This is clearly a case where naive intuition is unreliable: we don't
expect to beat a fair game, and we do expect to lose when the odds are
against us.  Nevertheless, the ``paradox'' that in fact we always win by
bet-doubling cannot be denied.

But remember that from the start we chose to assume that no one goes
bankrupt while executing our bet-doubling strategy.  This assumption is
crucial, because the expected loss while waiting for the strategy to
produce its ten dollar profit is actually infinite!  So it's not
surprising, after all, that we arrived at an apparently paradoxical
conclusion from an unrealistic assumption.

This example also serves a warning that in making use of infinite
linearity of expectation, the convergence hypothesis which justifies it
had better be checked.
}

\section{Wald's Theorem}

Wald's Theorem concerns the expected sum of a random number of random
variables.  For example, suppose that I flip a coin.  If I get heads, then
I roll two dice.  If I get tails, then I roll three dice.  What is the
expected sum of the dice that I roll?  Wald's Theorem supplies a simple
answer: the average number of dice I roll is 2 1/2, and the average value
of a single die roll is (1+2+\dots+6)/6 = 3 1/2, so the expected sum is (2
1/2)(3 1/2) = 8 3/4.

In the previous example, we are summing up only two or three values.  In
the next example, there is no bound on how many values we sum up:
\begin{example}
\label{ex:wald-dice} Repeatedly roll a die until it shows~6.  What is
the expected sum of the numbers shown in this process?

We can think of each die roll as a random variable: for every positive
integer $i$, let $X_i$ be the outcomes of the $i$th roll.  For
definiteness, say $X_i = 0$ if we roll a 6 in fewer than $i$ rolls.  So
each $X_i$ is a random variable taking values 0,1,\dots,6.  Define $Q =
\min\set{i \mid X_i = 6}$.  So $Q$ is another random variable whose
possible values are \emph{all positive integers}.

The random variable whose expectation we want to calculate is the sum
\[
X_1 + X_2 + \cdots + X_Q = \sum_{i=1}^Q X_i.
\]
Now we know the expected value of each $X_i$ is 3.5, and we also know the
expected number of rolls to roll a 6 is 6 (as with the earlier Mir
example).  Wald's theorem allows us to conclude that the expected sum is
$6\cdot 3.5=21$.
\end{example}

\iffalse
\begin{example}
  Suppose I modify the previous example: each time I roll a 6, I flip
  a coin and stop if heads comes up.  What is the expected sum of
  numbers now?
  
  We have $X_i$ and $Q$ as before.  Notice that $Q$ is no longer
  completely determined by $X_1,\ldots,X_Q$, but that $Q$ is still a
  stopping time because it is independent of all future $X_i$.
  
  We stop only if we roll a 6 \emph{and} then flip a head, which
  happens with probability $1/12$.  So I expect 12 rolls instead of 6,
  which increases the expected sum to $42$.
\end{example}
\fi

The general situation to which Wald's Theorem applies is in computing the
total expected cost of a step-by-step probabilistic process, where the
cost of a step and the number of steps to complete the process may depend
on what happens at each step.

Suppose the expected cost of each step is the same.  Then it's reasonable
to think that the expected cost of the process is simply this expected
cost of a step, times the expected number of steps.  In particular, if the
cost of the $i$th step is a random variable, $C_i$, and $Q$ is the
integer-valued positive random variable equal to the number of steps to
complete the process, then the total cost for completing the process is
precisely $C_1 + C_2 + \cdots + C_Q$.  So we reason that
\[
    \expect{C_1 + C_2 + \cdots + C_Q} = (\text{Expected cost of a step})
    \cdot \expect{Q}.
\]

Actually we don't care about the cost of steps which are not performed.
What we really want to say is that if the expected cost of each step is
the same, \emph{given that the step is performed}, then the equation above
seems reasonable.  That is, we only require that $\expcond{C_i}{Q \geq i}$
is the same for all $i$.

\iffalse

To state it precisely,
we extend the definition of expectation to be conditional on an event~$A$.

\begin{definition}
The conditional expectation, $\expcond{R}{A}$, of a random variable, $R$,
given event, $A$, is
\[
    \expcond{R}{A} ::= \sum_{s \in A} R(s) \prcond{s}{A}.
\]
\end{definition}

We state two easy properties without proof:

\begin{lemma}
\begin{eqnarray*}
\expcond{R}{A} & = & \sum_{r \in \range(R)} r \prcond{R = r}{A}.\\
\expect{R} & = & \expcond{R}{A} \cdot \prob{A} +
                 \expcond{R}{\overline{A}} \cdot \prob{\overline{A}}.
\end{eqnarray*}
\end{lemma}
\fi

\begin{theorem} \label{wald} [Wald]
Let $C_1, C_2, \dots,$ be a sequence of nonnegative random variables, and
let $Q$ be a positive integer-valued random variable, all with finite
expectations.  Suppose that
\[
\expcond{ C_i}{Q \geq i} = \mu
\]
for some $\mu \in \reals$ and for all~$i \geq 1$.  Then
\[
\expect{C_1 + C_2 + \cdots + C_Q} = \mu \expect{Q}.
\]
\end{theorem}
\begin{proof}

Let $I_k$ be the indicator variable for the event $[Q \geq k]$.  That is,
$I_k = 1$ if the process runs for at least $k$ steps, and $I_k = 0$ if the
process finishes in fewer than $k$ steps.  So
\[
    C_1 + C_2 + \cdots + C_Q = \sum_{k = 1}^\infty C_k I_k.
\]
Since all the variables are nonnegative, all the sums and expectations in
the following derivation are well-defined, and if any of them is finite,
then they all are:
\begin{eqnarray*}
\lefteqn{\expect{C_1 + C_2 + \cdots + C_Q}}\\
        &=& \expect{\sum_{k = 1}^\infty C_k I_k}\\
        &=& \sum_{k = 1}^\infty \expect{C_k I_k} \\
        &=& \sum_{k = 1}^\infty \expcond{C_k I_k}{I_k = 1} \cdot \prob{I_k = 1}
                                + \expcond{C_k I_k}{I_k = 0} \cdot \prob{I_k = 0}\\
        &=& \sum_{k = 1}^\infty \expcond{C_k}{I_k = 1} \cdot \prob{I_k = 1} \\
        &=& \sum_{k = 1}^\infty \expcond{C_k}{Q \geq k} \cdot \prob{Q \geq k} \\
        &=& \sum_{k = 1}^\infty \mu \cdot \prob{Q \geq k} \\
        &=& \mu \cdot \sum_{i = 0}^\infty \prob{Q > i} \\
        &=& \mu \cdot \expect{Q}.
\end{eqnarray*}
The last equality follows from the fact that
\[
    \expect{Q} = \sum_{i = 0}^\infty \prob{Q > i}
\]
for \emph{any} natural-number valued random variable, $Q$, as shown in
Notes 12.
\end{proof}

As a simple application of Wald's Theorem, we can give another proof of
the result about mean time to failure:
\begin{corollary}\label{meantime}
In a series of independent trials with probability~$p>0$ of failure at any
given trial, the expected number of trials until the first failure
is~$1/p$.
\end{corollary}

\begin{proof}
Define the cost~$C_i$ of the $i$th trial to be zero if it succeeds and
one if it fails.  Let $Q$ be the time to the first failure.  So
$\sum_{i = 1}^Q C_i = 1$.

Since the trials are independent, $\expcond{C_i}{Q \geq i} = p$ for
all~$i$.  Now Wald's Theorem applies:
\[
    1 = \expect{\sum_{i = 1}^Q C_i}
      = \expect{C_1} \cdot \expect{Q}
      = p \cdot \expect{Q},
\]
and so
\[
    \expect{Q} = \frac{1}{p}.
\]
\end{proof}

\subsection{The Paradox Again}
Played on a fair roulette wheel, our bet-doubling strategy is a
step-by-step random process, where the expected cost of a step and the
expected number of steps are both finite.  In this case, the expected cost
is the expected amount won on the step, namely zero, and the expected
number of steps is the expected number of spins until red occurs, which we
know is $1/(1/2) = 2$.  So applying Wald's Theorem,
\[
\expect{\mbox{amount won}}  =  \expect{\mbox{gain on the first
spin}}\cdot \expect{\mbox{number of spins}} =  0 \cdot 2 = 0,
\]
which is again what we naively would have anticipated in a fair game.

Of course, we know this isn't so.  The problem this time is that the cost
of a step is negative half the time, and we have proved Wald's Theorem
only for nonnegative random variables.  Indeed, bet-doubling is an example
where the conclusion of Wald's Theorem fails to hold for random variables
that are not nonnegative.

\iffalse

\section{Wald's Theorem}

\subsection{A Special Case}

As a warmup, we first consider the case when $Q$~is independent of
the~$X_i$.
\begin{theorem}
  Let $Q$~be a random variable taking values in the positive integers
  and let $X_1, X_2, X_3, \ldots$ be independent identically
  distributed random variables. Then, if the~$X_i$ are independent
  of~$Q$,
  \begin{displaymath}
    \expect{X_1 + X_2 + \ldots + X_Q} = \expect{X} \cdot \expect{Q},
  \end{displaymath}
  where $X$~is a random variable with the same distribution as
  the~$X_i$.
\end{theorem}
\begin{proof}
  We rewrite $\expect{X_1 + X_2 + \ldots + X_Q}$ using the law of total
  probability.
  \begin{displaymath}
    \expect{X_1 + X_2 + \ldots + X_Q}
    =
    \sum_{q=1}^{\infty} \expcond{X_1 + X_2 + \ldots + X_Q}{Q = q} \pr{Q = q}.
  \end{displaymath}
  For every~$q$,
  \begin{displaymath}
    \expect{X_1 + X_2 + \ldots + X_Q \given Q = q} = 
    \expect{X_1 + X_2 + \ldots + X_q \given Q = q} = q \expect{X \given Q = q},
  \end{displaymath}
  and since we assumed that the~$X_i$ are independent of~$Q$,
  \begin{displaymath}
     q \expect{X \given Q = q} = q \expect{X}.
  \end{displaymath}
  Therefore,
  \begin{displaymath}
    \expect{X_1 + X_2 + \ldots + X_Q}
    =
    \sum_{q=1}^{\infty} q \expect{X} \pr{Q = q}
    =
    \expect{X} \sum_{q=1}^{\infty} q \pr{Q = q}
    =
    \expect{X} \expect{Q}.
  \end{displaymath}
\end{proof}
\begin{example}  
  \label{ex:coin-and-dice}
  The coin-and-dice problem is solved easily using the above version
  of Wald's Theorem.  Based on the outcome of a coin toss, I roll
  either two or three dice.  Thus, we define $Q$ so that $\pr{Q = 2} =
  \pr{Q = 3} = 1/2$, and we define $R, R_1, R_2, \ldots$ to
  take on values in the range $1$ to $6$ uniformly.  The sum of the
  dice that I roll is equal to $R_1 + \ldots + R_Q$.  By Wald's
  Theorem, this sum is equal to:
\[
\expect{R_1 + \cdots + R_Q} = \expect{R} \cdot \expect{Q}
= \frac{7}{2} \cdot \frac{5}{2} = \frac{35}{4}.
\]
\end{example}

\subsection{The General Case}

The special case of Wald's theorem from the above section is very nice
and applies to a wide variety of situations. It turns out, however,
that in many of the applications that are important in practice
$Q$~actually depends on the~$X_i$. Fortunately, it is possible to
generalize Wald's theorem to many of these cases by defining the
interaction between~$Q$ and the~$X_i$ in the proper way.
\begin{definition}
  Let $X_1, X_2, X_3, \ldots$ be a sequence of independent random
  variables and let~$Q$ be a random variable taking values in the
  positive integers. $Q$~is a \emph{stopping time with respect to
    $X_1, X_2, X_3, \ldots$} if the event $[Q = q]$ is independent
  of $X_{q+1}, X_{q+2}, \ldots$.
\end{definition}
It turns out that the concept of a stopping time captures precisely
the assumptions needed to prove Wald's Theorem.
\begin{theorem}[Wald's Theorem]
  Let $X_1, X_2, X_3, \ldots$ be a sequence of identically distributed
  random variables such that $\expect{\abs{X_i}} \leq \infty$ and let $Q$~be a
  stopping time with respect to this sequence. Then, if $\expect{Q} <
  \infty$,
  \begin{displaymath}
    \expect{X_1 + X_2 + \ldots + X_Q} = \expect{X} \cdot \expect{Q},
  \end{displaymath}
  where $X$~is a random variable with the same distribution as
  the~$X_i$.
\end{theorem}
Intuitively, $Q$ is a stopping time if the event $[Q = q]$ depends
only on $X_1, X_2, \ldots, X_q$ . The term stopping time comes from
the following interpretation. We observe some sequence of random
variables, and after each one we make a decision about whether to
stop.  The decision to stop after $q$ variables, \ie, to set $Q=q$,
can be based on what we've seen so far, \ie, $X_1,\ldots,X_q$, and on
separate, random choices, but \emph{cannot} be based on the variables
we have not yet seen.

Another intuitive description of a stopping time comes from the fact
that independence is a symmetric relation: $Q$~is a stopping time if
the event $[Q = q]$ does not affect the distribution of $X_{q+1},
X_{q+2}, \dots$.
\begin{example}
  The $Q$~defined in Example~\ref{ex:coin-and-dice} is a stopping
  time; it doesn't depend on the~$X_i$ at all.
\end{example}
\begin{example}
  \label{ex:wald-dice}
  Suppose I repeatedly roll a die until it shows~6. What is the
  expected sum of the numbers shown in this process?

  Let $X_1, X_2, X_3, \ldots$ be the outcomes of the rolls and define
  $Q = \min\set{i \given X_i = 6}$.  Note that $Q$ is definitely
  \emph{not} independent of the $X_i$.  But $Q$~is nevertheless a
  stopping time since the event $[Q = q]$ only depends on the values
  $X_1, \ldots, X_q$.  So we can write the sum as $X_1 + X_2 + \cdots
  + X_Q$ where $Q$~is a stopping time. Therefore the expected sum is
  $\expect{X_1 + X_2 + \cdots + X_Q}$.  Thus Wald's Theorem applies.
  The expected value of each $X_i$ is 3.5.  The expected number of
  rolls to roll a 6 is 6 (as with the earlier Mir example).  So the
  expected sum is $6\cdot 3.5=21$.
\end{example}
\begin{example}
  Suppose I modify the previous example: each time I roll a 6, I flip
  a coin and stop if heads comes up.  What is the expected sum of
  numbers now?
  
  We have $X_i$ and $Q$ as before.  Notice that $Q$ is no longer
  completely determined by $X_1,\ldots,X_Q$, but that $Q$ is still a
  stopping time because it is independent of all future $X_i$.
  
  We stop only if we roll a 6 \emph{and} then flip a head, which
  happens with probability $1/12$.  So I expect 12 rolls instead of 6,
  which increases the expected sum to $42$.
\end{example}
Now we'll embark on a proof of Wald's theorem.  The idea in the proof
is to convert the sum $X_1 + X_2 + \cdots + X_Q$, which contains a
random number of terms, into a sum containing an infinite number of
terms. This is done by defining indicator random variables that ``mask
out'' all terms after the $Q$'th one.
\begin{lemma}
  \label{lem:wald-indicators}
  Define the indicator random variables
  \begin{displaymath}
    I_{[Q \geq q]} = \begin{cases}
      1 & \mbox{if $Q \geq q$,} \\
      0 & \mbox{otherwise.}
    \end{cases}
  \end{displaymath}
  Then we can rewrite $X_1 + X_2 + \cdots + X_Q$ as
  \begin{displaymath}
    X_1 + X_2 + \ldots + X_Q = \sum_{i=1}^{\infty} X_i I_{[Q \geq i]}.
  \end{displaymath}
\end{lemma}
\begin{proof}
  Look at the $i$th term in the sum. If $i \leq Q$, $I_{[Q \geq i]}
  = 1$ and the term is simply~$X_i$. Otherwise, $I_{[Q \geq i]} = 0$
  and the term is~$0$.
\end{proof}
\begin{corollary}
  Let $X_1, X_2, X_3, \ldots$ be a sequence of random variables such
  that $\expect{\abs{X_i}} \leq \infty$ and let $Q$~be a random variable
  taking values in the positive integers. Then, if $\expect{Q} < \infty$,
  \begin{displaymath}
    \expect{X_1 + X_2 + \ldots + X_Q}
    = \sum_{i=1}^{\infty} \expect{X_i I_{[Q \geq i]}}.
  \end{displaymath}
\end{corollary}
So instead of taking the expectation of a random number of terms, we
can take the expectation of a countably infinite number of terms, many
of which are zero. It turns out that we can use the fact that $Q$~is a
stopping time to compute $\expect{X_i I_{[Q \geq i]}}$.
\begin{lemma}
  \label{lem:wald-independence}
  If $Q$~is a stopping time with respect to a sequence $X_1, X_2, X_3,
  \ldots$ of independent random variables, $\expect{X_i I_{[Q \geq i]}}
  = \expect{X_i} \pr{Q \geq i}$.
\end{lemma}
\begin{proof}
  Note that $X_i I_{[Q \geq i]} = X_i (1-I_{[Q < i]}) = X_i (1 -
  \sum_{q=0}^{i-i}I_{[Q = q]})$; this implies that
  \begin{displaymath}
    \expect{X_i I_{[Q \geq i]}} =
    \expect{X_i} - \sum_{q=0}^{i-1} \expect{X_i I_{[Q = q]}}.
  \end{displaymath}
  Since $Q$~is a stopping time with respect to $X_1, X_2, X_3,
  \ldots$, the event $[Q = q]$ is independent of~$X_i$ for all $q <
  i$. Therefore $\expect{X_i I_{[Q = q]}} = \expect{X_i} \expect{I_{[Q = q]}}$
  for all $q < i$, which implies that
  \begin{displaymath}
    \expect{X_i I_{[Q \geq i]}} =
    \expect{X_i} - \sum_{q=0}^{i-1} \expect{X_i} \pr{Q = q} =
    \expect{X_i}\biggl(1 - \sum_{q=0}^{i-1} \pr{Q = q}\biggr).
  \end{displaymath}
  Since $1 - \sum_{q=0}^{i-1} \pr{Q = q} = 1 - \pr{Q < i} = \pr{Q
  \geq i}$, the proof is complete.
\end{proof}
We are now ready to give the proof of Wald's Theorem.
\begin{proof}[Proof of Wald's Theorem]
  By Lemma~\ref{lem:wald-indicators}, we can rewrite $X_1 + X_2 +
  \cdots + X_Q$ as
  \begin{displaymath}
    X_1 + X_2 + \ldots + X_Q = \sum_{i=1}^{\infty} X_i I_{[Q \geq i]}.
  \end{displaymath}
  We take expectation of both sides and obtain
  \begin{displaymath}
    \expect{X_1 + X_2 + \ldots + X_Q}
    =
    \expect{\sum_{i=1}^{\infty} X_i I_{[Q \geq i]}}
    =
    \sum_{i=1}^{\infty} \expect{X_i I_{[Q \geq i]}}
  \end{displaymath}
  By Lemma~\ref{lem:wald-independence}, $\expect{X_i I_{[Q \geq i]}} =
  \expect{X} \pr{Q \geq i}$. Putting this together gives
  \begin{displaymath}
    \expect{X_1 + X_2 + \ldots + X_Q}
    =
    \sum_{i=1}^{\infty} \expect{X} \pr{Q \geq i}
    =
    \expect{X} \sum_{i=1}^{\infty} \pr{Q \geq i}
    =
    \expect{X} \expect{Q},
  \end{displaymath}
  where we used the ``alternative'' formula for the expected value in
  the last step.
\end{proof}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Building a System}

Wald's Theorem turns out to be useful in analyzing algorithms and
systems.  The following problem was incorrectly solved in a well-known
1962 paper, \emph{The Architecture of Complexity}, by Herbert Simon,
who later won the Nobel Prize in economics.  The paper is one of the
regular readings in~6.033.

Suppose that we are trying to build a system with $n$~components.  We
add one component at a time.  However, whenever we add a component,
there is a probability~$p$ that the whole system falls apart and we
must start over from the beginning.  Assume that these collapses occur
mutually independently.  What is the expected number of steps required
to finish building the system?

\subsection{The Sample Space}

We can regard the sample points in this experiment as infinite strings
of $S$'s and $F$'s.  An $S$ in the $i$-th position indicates that a
component is successfully added in the $i$-th step.  An $F$ in the
$i$-th position indicates that the system falls apart in the $i$-th
step.  For example, in outcome $SSFSF\ldots$ we add two components,
and then the system collapses while we are adding the third.  So we
start over from scratch.  We then add one component successfully, but
the system collapses again while we are adding the second.  We start
over again, etc.

Using this notation, the system is completed after we encounter a
string of $n$ consecutive $S$'s.  This indicates that all $n$
components were added successfully without the system falling apart.
For example, suppose we are building a system with $n=3$ components.
In outcome $SSFSFF\underbar{SSS}FSF\ldots$, the system is completed
successfully after 9 steps, since after 9 steps we have encountered a
string of three consecutive $S$'s.

\subsection{Tries}

Define a ``try'' to be a sequence of steps that starts with a system
of zero components and ends when the system is completed or collapses.
Let $R_k$ be the number of steps in the $k$-th try, and let $Q$ be the
number of tries required to complete the system.  The number of steps
needed to build the system is then $T = \sum_{k=1}^Q R_k$.  For
example, if we are building a system with $n = 3$ components, then we
can break outcome $SSFSFFSSSFSF\ldots$into tries as shown below:
\[
\underbrace{S \quad S \quad F}_{
        \begin{array}{c} R_1 = 3 \\ \text{failure} \end{array}}
\underbrace{S \quad F}_{
        \begin{array}{c} R_2 = 2 \\ \text{failure} \end{array}}
\underbrace{F}_{
        \begin{array}{c} R_3 = 1 \\ \text{failure} \end{array}}
\underbrace{S \quad S \quad S}_{
        \begin{array}{c} R_4 = 3 \\ \text{success!} \end{array}}
\underbrace{F}_{
        \begin{array}{c} R_5 = 1 \\ \text{failure} \end{array}}
\underbrace{S \quad F}_{
        \begin{array}{c} R_6 = 2 \\ \text{failure} \end{array}}
\ldots
\]
(Note that we regard an outcome as an infinite string of $S$'s and
$F$'s, and so an outcome formally consists of an infinite number of
tries.  However, the remainder of the string after the first
successful try is not relevant.)

In the above example, four tries are required to complete the system,
so we have $Q = 4$.  The number of steps needed to complete the system
is:
\[
T = \sum_{k=1}^Q R_k = R_1 + R_2 + R_3 + R_4 = 3 + 2 + 1 + 3 = 9
\]



\subsection{Applying Wald's Theorem}

Our goal is to determine $\expect{T}$, the expected number of steps needed
to complete the system. We want to apply Wald's Theorem to obtain that
\begin{displaymath}
  \expect{T} = \expect{\sum_{k=1}^Q R_k} = \expect{Q} \cdot \expect{R}.
\end{displaymath}
To do this we need to verify that the conditions in Wald's Theorem are
satisfied. Firstly, all tries are symmetric, so all random variables
$R_k$ have the same distribution. Secondly, $\expect{\abs{R}}$ is finite
because every try lasts at most $n$ steps. Thirdly, $Q$~is a stopping
time since the event $[Q = q]$ does not depend on $R_{q+1}, R_{q+2},
R_{q+3}, \ldots$ We will now show that $\expect{Q}$ is finite by actually
computing it.



\subsection{Computing the Expected Number of Tries}

Let's compute $\expect{Q}$, the expected number of tries needed to
complete the system.

First, we will compute the probability that a particular try is
successful. A successful try consists of $n$ consecutive $S$'s.  The
probability of an $S$ in each position is $1-p$.  The probability of
$n$ consecutive $S$'s is therefore $(1-p)^n$; we can multiply
probabilities, since system collapses occur mutually independently.

Now, if a try is successful with probability $(1-p)^n$, what is the
expected number of tries needed to succeed?  We already encountered this
question in another guise.  Then we asked the expected number of hours
until Mir's main computer went down, given that it went down with
probability $q$ in each hour.  We found that the expected number of hours
until a main computer failure was $1/q$.  Here we want the number
of tries before the system is completed, given that a try is successful
with probability $(1-p)^n$.  By the same analysis, the expected number of
tries needed to succeed is $1/(1-p)^n$.  Therefore, we have:
\[
\expect{Q} = \frac{1}{(1-p)^n}.
\]
This also shows that $Q$ is finite, provided $p \neq 1$.


\subsection{Computing the Expected Length of a Try}

Now let's compute $\expect{R}$, the expected number of steps in a try.
Since the number of steps in a try is always a nonnegative integer,
we can write:
\begin{displaymath}
  \expect{R} = \sum_{i=0}^{\infty} \pr{R > i} = \sum_{i=0}^{n-1} \pr{R > i}.
\end{displaymath}
The second equality holds because a try never lasts for more that
$n$~steps; if the system does not collapse within $n$~steps, then the
system is completed, and the try is done anyway.  Therefore, $\pr{R >
n} = 0$, and so only the first $n$ terms of the infinite sum can be
non-zero.

Now we must evaluate $\pr{R > i}$, the probability that a try
consists of more than $i$ steps.  This is just the probability that
the system does not collapse in the first $i$ steps, which is
$(1-p)^i$.  Therefore, $\pr{R > i} = (1-p)^i$.  Substituting this
into the equation above and summing the resulting geometric series
gives the expected number of steps in a try:
\begin{eqnarray*}
\expect{R}     & = & \sum_{i=0}^{n-1} (1-p)^i \\
           & = & \frac{1 - (1-p)^n}{1 - (1-p)} \\
           & = & \frac{1 - (1-p)^n}{p} \\
\end{eqnarray*}


\subsection{Computing the Expected Number of Steps} 

Now we can compute the expected number of steps needed to complete the
system.
\begin{eqnarray*}
\expect{T}  & = & \expect{Q} \cdot \expect{R} \\
        & = & \frac{1}{(1-p)^n} \cdot \frac{1 - (1-p)^n}{p} \\
        & = & \frac{1 - (1-p)^n}{p (1-p)^n} \\
        & = & \frac{1}{p (1-p)^n} - \frac{1}{p}\\
\end{eqnarray*}
For example, suppose that there is only a 1\% chance that the system
collapses when we add a component ($p = 0.01$).  The expected number
of steps to complete a system with $n = 10$ components is about
10.  For $n = 100$ components, the number of steps is about 173.
But for $n=1000$ components, the number is about 2,316,257.  As the
number of components increases, the number of steps required increases
exponentially!  The intuition is that adding, say, 1000 components
without a single failure is very unlikely; therefore, we need a
tremendous number of tries!


\subsection{A Better Way to Build Systems}

The moral of this analysis is that one should build a system in pieces
so that all work is not lost in a single accident.

For example, suppose that we break a 1000 components system into 10
modules, each with 10 submodules, each with 10 components.  Assume
that when we add a component to a submodule, the submodule falls apart
with probability $p$.  Similarly, we can add a submodule to a module
in one step, but with probability $p$ the module falls apart into
submodules.  (The submodules remain intact, however.)  Finally, we
can add a module into the whole system in one step, but the
system falls apart into undamaged modules with probability $p$.

Altogether, we must build a system of 10 modules, build 10 modules
consisting of 10 submodules each, and build 100 submodules consisting
of 10 components each.  This is equivalent to building 111 systems of
10 components each.  The expected time to complete the system is $111
\cdot 10.57\ldots \approx 1173$ steps.  This compares very favorably
with the 2.3 million steps required in the direct method!


\section{Deviation from the Mean}

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

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

But what is true is that the number of heads is likely to be \emph{close}
to half the number of flips, and the more flips, the closer the percentage
of heads is likely to be to 1/2.  For example, the chance that the number
of heads is within 5\% of the expected number is
\begin{itemize}
\item more than 24\% in 10 flips,
\item more than 70\% in 100 flips,
\item more than 86\% in 200 flips, and
\item more than 99.8\% in 1000 flips.
\end{itemize}

The fact that the average value from repeated experiments is likely to be
\emph{close} to the expected value of one experiment is the single most
important phenomenon of probability.  Many of the major applications of
probability theory hinge on calculation of the probability that a random
variable will differ by a given amount from its mean.  For example:
\begin{itemize}

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

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

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

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

\end{itemize}

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

In many situations, we not only know the mean, but also another numerical
quantity called the \emph{variance} of the random variable.  Our second
basic result is Chebyshev's Theorem, which gives more refined bounds by
taking the variance into account.

As an easy corollary of Chebyshev's Theorem, we will obtain our third
basic result called The (Weak) Law of Large Numbers.  This provides a
general, precise formulation of the intuitive idea that we began with,
namely, that the average of many meaurements of a random variable is
likely to be close to its expectation.

\iffalse 

Finally, we give ``Chernoff Bounds'', which give still more
refined results, taking into account still more information. 
These deal with the situation where the distribution is of a particular
form---resulting from a series of independent experiments (e.g.,
voters all tossing independent coins).
\fi

\subsection{Markov's Theorem}

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

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

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

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

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

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

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

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

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


\subsection{Theorem Statement and Some Applications}
\fi

\begin{theorem}[Markov's Theorem]\label{markovthm}
  If R is a nonnegative random variable, then for all $x > 0$
  \begin{displaymath}
    \pr{R \geq x} \leq \frac{\expect{R}}{x}.
  \end{displaymath}
\end{theorem}

\iffalse

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

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

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

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



\subsection{Proof of Markov's Theorem}

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

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

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

\begin{proof}%[Proof of Markov's Theorem]

  We must prove that if R is a nonnegative random variable, then for
  all $x > 0$,
  \begin{displaymath}
    \pr{R \geq x} \leq \frac{\expect{R}}{x}\,.
  \end{displaymath}
  We will show that $\expect{R} \geq x \cdot \pr{R \geq x}$.  Dividing
  both sides by $x$ gives the desired result.

So let $I_{[R \geq x]}$ be the indicator variable for the event $[R \geq
x]$, and consider the random variable $x I_{[R \geq x]}$.  Clearly, $R
\geq x I_{[R \geq x]}$: if $R(w) \geq x$ then $x I_{[R \geq x]}(w) = x$,
and if $R(w) < x$ then $x I_{[R \geq x]}(w) = 0$.  Therefore,
\[
\expect{R} \geq \expect{x I_{[R \geq x]}} = x \expect{I_{[R \geq x]}}
= x \pr{R \geq x}.
\]
  The inequality follows since $R \geq x I_{[R \geq x]}$. Then we
  pull~$x$ out of the expectation, and finally we use the fact that
  the expectation of an indicator variable for some event is equal to
  the probability of that event.
\end{proof}

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


\subsubsection{Examples of Markov's Theorem}

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

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

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

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

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

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

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

The proof of Markov's Theorem requires that the random variable, $R$, be
nonnegative.  The following example shows that the theorem is false
if this restriction is removed.  Let $R$ be -10 with probability
$1/2$ and 10 with probability $1/2$.  Then we have:
\[
\expect{R} = -10 \cdot \frac{1}{2} + 10 \cdot \frac{1}{2} = 0
\]
Suppose that we now tried to compute $\pr{R \geq 5}$ using Markov's
Theorem:
\begin{displaymath}
  \pr{R \geq 5} \leq \frac{\expect{R}}{5} = \frac{0}{5} = 0.
\end{displaymath}
This is the wrong answer!  Obviously, $R$ is at least 5 with
probability $1/2$.  Remember that Markov's Theorem applies
only to nonnegative random variables!

On the other hand, we can still apply Markov's Theorem to bound the
probability that an arbitrary variable like $R$ is 5 more.  Namely, given
any random variable, $R'$, that, like $R$, has expectation 0 and values
$\geq -10$, we can conclude that $\pr{R' \geq 5} \le 2/3$.
\begin{proof}
Let $T \eqdef R'+10$.  Now $T$ is a nonnegative random variable with
expectation $\expect{R' + 10} = \expect{R'}+10= 10$, so Markov's Theorem
applies and tells us that $\pr{T \geq 15} \le 10/15 = 2/3$.  But $T \geq
15$ iff $R' \geq 5$, so $\pr{R' \geq 5} \leq 2/3$, as claimed.
\end{proof}

\subsubsection{Deviation Below the Mean}

Markov's Theorem says that a random variable is unlikely to greatly
exceed the mean.  There a similar theorem that says a random variable
is unlikely to be very small.

\begin{theorem}
  \label{th:below}
  Let $L$ be a real number and let $R$ be a random variable such that $R
  \leq L$.  For all $x < L$, we have:
  \[
  \pr{R \leq x} \leq \frac{L - \expect{R}}{L - x}.
  \]
\end{theorem}

\begin{proof}
  The event that $R \leq x$ is the same as the event that $L - R \geq L
  - x$.  Therefore:
  \begin{displaymath}
    \pr{R \leq x} = \pr{L - R \geq L - x} \leq \frac{\expect{L - R}}{L - x}\,.
  \end{displaymath}
  In the second step, we applied Markov's Theorem.  This is
  permissible since $L - R$ is a nonnegative random variable and $L -
  x > 0$.
\end{proof}

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

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

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


\subsubsection{Using Markov To Analyze Non-Random Events}

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

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

\section{Chebyshev's Theorem}

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

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

\begin{corollary}\label{cor:Markov2}
For any random variable~$R$, any positive integer~$k$ and any $x > 0$,
\[
\pr{\abs{R} \geq x} \leq \frac{\expect{\abs{R}^k}}{x^k}.
\]
\end{corollary}

The special case of this corollary when $k=2$ can be applied to bound the
random variable, $\abs{R - \expect{R}}$, that measures $R$'s
deviation from its mean.  Namely
\begin{equation}\label{chebE2}
\pr{\abs{R - \expect{R}} \geq x}
  = \pr{(R - \expect{R})^2 \geq x^2} \leq \frac{\expect{(R - \expect{R})^2}}{x^2},
\end{equation}
where the inequality follows from Corollary~\ref{cor:Markov2} applied to
the random variable, $\abs{R - \expect{R}}$.  So we can bound the
probability that the random variable~$R$ deviates from its mean by more
than~$x$ by an expression decreasing as $1/x^2$ multiplied by the constant
$\expect{(R - \expect{R})^2}$.  This constant is called the \emph{variance
of~$R$}.

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

So we can restate~(\ref{chebE2}) as
\begin{theorem}[Chebyshev]\label{chebthm}
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\pr{|R - \expect{R}| \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\end{theorem}

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

\subsection{Example: Gambling Games}

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

Game A: We win \$2 with probability $2/3$ and lose \$1 with probability
$1/3$.

Game B: We win \$1002 with probability $2/3$ and lose \$2001 with
probability $1/3$.

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

The expected payoff is the same for both games, but they are obviously
very different!  This difference is hidden by expected value, but
captured by variance.  We can compute the $\variance{A}$ by
working ``from the inside out'' as follows:
\begin{eqnarray*}
A - \expect{A}
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        -2 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(A - \expect{A})^2
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        4 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\expect{(A - \expect{A})^2}
        & = &   1 \cdot \frac{2}{3} + 4 \cdot \frac{1}{3} \\
\variance{A} & = & 2.
\end{eqnarray*}

Similarly, we have for $\variance{B}$:
\begin{eqnarray*}
B - \expect{B}
        & = &   \left\{
                \begin{array}{cl}
                        1001 & \text{ with probability } \frac{2}{3} \\
                        -2002 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(B - \expect{B})^2
        & = &   \left\{
                \begin{array}{cl}
                        1,002,001 & \text{ with probability } \frac{2}{3} \\
                        4,008,004 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\expect{(B - \expect{B})^2}
        & = &   1,002,001 \cdot \frac{2}{3} + 4,008,004 \cdot \frac{1}{3} \\
\variance{B} & = & 2,004,002.
\end{eqnarray*}

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

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

\section{Properties of Variance}

\subsection{Why Variance?}

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

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

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

\subsection{Standard Deviation}

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

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

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

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

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

As can be seen in 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}
\[
\variance{R} = \expect{R^2} - \expectsq{R},
\]
for any random variable, $R$.
\end{theorem}

Remember that $\expect{R^2}$ is generally not equal to $\expectsq{R}$.
The expected value of a product is the product of the expected values only
for independent variables, and $R$ is not independent of itself unless it
is constant.
\begin{proof}
  Write $\mu = \expect{R}$.  Then
  \begin{eqnarray*}
    \variance{R}
        & = &   \expect{(R - \mu)^2} \\
        & = &   \expect{R^2 - 2 R \cdot \mu + \mu^2} \\
        & = &   \expect{R^2} - \expect{2 R \cdot \mu} + \expect{\mu^2} \\
        & = &   \expect{R^2} - 2 \expect{R} \cdot \mu + \mu^2 \\
        & = &   \expect{R^2} - 2 \expectsq{R} + \expectsq{R} \quad
           \text{(definition of $\mu$)}\\
        & = &   \expect{R^2} - \expectsq{R}.
  \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*}
  \expect{R^2} = \frac{1}{6} (1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2) = \frac{91}{6}, \\
  \expectsq{R} = \left(3 \frac{1}{2}\right)^2 = \frac{49}{4}, \\
  \variance{R}  = \expect{R^2} - \expectsq{R}
  = \frac{91}{6} - \frac{49}{4} = \frac{35}{12}.
\end{gather*}


\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{eqnarray*}
\variance{R} &=& \expect{(R - \expect{R})^2}\\
&=& \frac{(x_1 - \expect{R})^2 + (x_2 - \expect{R})^2
                     + \cdots + (x_n - \expect{R})^2}{n}.
\end{eqnarray*}

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 -
\expect{R})^2$ and add it to the running sum.  At the 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 $\expect{R}$ until after we
have seen all of the data!  Therefore, we need \emph{two} passes, one
to compute $\expect{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*}
\variance{R}
        & = & \expect{R^2} - \expectsq{R} \\
        & = & \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!

\iffalse

\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 $\expect{R^2} \geq \expectsq{R}$.
\end{corollary}
\begin{proof}
  We first defined $\variance{R}$ as an average of a squared expression, so
  $\variance{R}$ is nonnegative.  Then we proved that $\variance{R} = \expect{R^2}
  - \expectsq{R}$.  This implies that $\expect{R^2} - \expectsq{R}$ is
  nonnegative.  Therefore, $\expect{R^2} \geq \expectsq{R}$.
\end{proof}
In words, the expectation of a square is at least the square of the
expectation. The two are equal exactly when the variance is zero:
\begin{displaymath}
\expect{R^2} = \expectsq{R} \text{  iff  } \expect{R^2} - \expectsq{R} = 0
\text{  iff  } \variance{R} = 0.
\end{displaymath}
\fi


\subsection{Zero Variance}

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

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

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

\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
\begin{equation}\label{aRb}
\variance{a R + b} = a^2 \variance{R}.
\end{equation}
\end{theorem}

This theorem makes two points.  First, adding a constant $b$ to a
random variable does not affect the variance.  Second, multiplying a
random variable by a constant $a$ changes the variance by an $a^2$
factor.

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

Finally, we substract that (expanded) second term from the first.
Cancelling terms, we find:
\begin{eqnarray*}
\variance{a R + b} & = & a^2 \expect{R^2} - a^2 \expectsq{R}\\
& = & a^2 (\expect{R^2} - \expectsq{R})\\
& = & a^2 \variance{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}\label{indvar}
If $R_1$ and $R_2$ are independent random variables, then
\[
\variance{R_1 + R_2} = \variance{R_1} + \variance{R_2}.
\]
\end{theorem}
\begin{proof}
We will transform the left side into the right side.  We begin by
applying the alternate definition of variance.
\[
\variance{R_1 + R_2} = \expect{(R_1 + R_2)^2} - \expectsq{R_1 + R_2}.
\]

We will work on the first term and then the second term separately.
For the first term, note
\begin{eqnarray*}
\expect{(R_1+R_2)^2}
& = &   \expect{R_1^2 + 2 R_1 R_2 + R_2^2} \\
& = &   \expect{R_1^2} + \expect{2 R_1 R_2} + \expect{R_2^2} \\
& = &   \expect{R_1^2} + 2 \expect{R_1} \expect{R_2} + \expect{R_2^2}.
\end{eqnarray*}
First, we multiply out the squared expression.  The second step uses
linearity of expectation.  In the last step, we break the
expectation of the product $R_1 R_2$ into a product of expectations;
this is where we use the fact that $R_1$ and $R_2$ are independent.
Now we work on the second term.
\begin{eqnarray*}
\expectsq{R_1+R_2} & = & (\expect{R_1} + \expect{R_2})^2 \\
& = & \expectsq{R_1} + 2 \expect{R_1} \expect{R_2} + \expectsq{R_2}.
\end{eqnarray*}
The first step uses linearity of expectation, and in the second step
we multiply out the squared expression.  Now we subtract the
(expanded) second term from the first. Cancelling and rearranging
terms, we find that
\begin{eqnarray*}
\variance{R_1 + R_2} & = &   (\expect{R_1^2} - \expectsq{R_1}) +
(\expect{R_2^2}) - \expectsq{R_2}) \\
& = &   \variance{R_1} + \variance{R_2}.
\end{eqnarray*}
\end{proof}

The independence condition in the theorem is necessary.  If we ignored
this condition and took $R_1$ and $R_2$ to be the same nonconstant random
variable, then we would conclude that $\variance{R + R} = \variance{R} +
\variance{R}$.  However, by Theorem~\ref{th:const}, the left side is equal
to $4 \variance{R}$, whereas the right side is $2 \variance{R}$.  This
implies that $\variance{R}=0$, which, by Lemma~\ref{zvar}, contradicts the
fact that $R$ is nonconstant.  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 \emph{pairwise} independent random
variables, then
\[
\variance{R_1 + R_2 + \ldots + R_n} = \variance{R_1} + \variance{R_2} +
  \ldots + \variance{R_n}.
\]
\end{theorem}
\begin{proof}
  We use the formula $\variance{R} = \expect{R^2} - \expectsq{R}$.
  \begin{displaymath}
    \expect{\biggl(\sum_{i=1}^n R_i\biggr)^2}
    = \expect{\sum_{i=1}^n \sum_{j=1}^n R_i R_j}
    = \sum_{i=1}^n \sum_{j=1}^n \expect{R_i R_j}.
  \end{displaymath}
  If $i = j$, $\expect{R_i R_j} = \expect{R_i^2}$, and if $i \neq j$, $\expect{R_i
  R_j} = \expect{R_i} \expect{R_j}$ since $R_1, R_2, \ldots, R_n$ are pairwise
  independent.
  \begin{displaymath}
    \expectsq{\sum_{i=1}^n R_i}
    = \biggl(\sum_{i=1}^n \expect{R_i}\biggr)^2
    = \sum_{i=1}^n \sum_{j=1}^n \expect{R_i} \expect{R_j}.
  \end{displaymath}
  Putting the pieces together, the terms containing $\expect{R_i}
  \expect{R_j}$ cancel, which gives
  \begin{displaymath}
    \Var\biggl(\sum_{i=1}^n R_i\biggr)
    = \sum_{i=1}^n \expect{R_i^2} - \sum_{i=1}^n \expectsq{R_i}
    = \sum_{i=1}^n \variance{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*}
\variance{R}
        & = &   \variance{R_1} + \variance{R_2} + \ldots + \variance{R_n} \\
        & = &   n \variance{R_i} \\
        & = &   n (\expect{R_i^2} - \expectsq{R_i}) \\
        & = &   n (\expect{R_i} - \expectsq{R_i}) \\
        & = &   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 $\variance{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 = 1/2$), the variance is $n/4$ and the
standard deviation is $\sqrt{n}/2$.


\section{Applications of Chebyshev's Theorem}

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

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

\subsection{I.Q. Example}

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

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

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

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

\subsection{A One-Sided Bound}

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

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

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 - \expect{R} \geq x} \leq \frac{\variance{R}}{\variance{R} + x^2}, \\
    \pr{R - \expect{R} \leq -x} \leq \frac{\variance{R}}{\variance{R} + x^2}.
  \end{gather*}
\end{theorem}
This theorem has a corollary analogous to Corollary~\ref{cor:cheby}.
\begin{corollary}
  \label{cor:cheby1}
  Let $R$ be a random variable, and let $c$ be a positive real number.
  \begin{gather*}
    \pr{R - \expect{R} \geq c \sigma_R} \leq \frac{1}{1 + c^2}, \\
    \pr{R - \expect{R} \leq - c \sigma_R} \leq \frac{1}{1 + c^2}.
  \end{gather*}
\end{corollary}
\begin{proof}
  Substitute $x = c \sigma_R$ in the preceding theorem.
\end{proof}
We can use this theorem to improve our solution to the \IQ problem
just slightly.  Recall that $R$ is the \IQ of a random person and
that $\expect{R} = 100$ and $\sigma_R = 10$.
\begin{eqnarray*}
\pr{R \geq 200}
        & = &           \pr{R - 100 \geq 100} \\
        & \leq &        \frac{\variance{R}}{\variance{R} + 100^2} \\
        & = &           \frac{10^2}{10^2 + 100^2} \\
        & = &           \frac{1}{101}.
\end{eqnarray*}
This shows that at most 1 person in 101 has an \IQ of 200 or more.

\subsection{Problem Scores}

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

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


\section{Deviation of Repeated Trials}

We have repeatedly suggested the intuitive idea that the average of a
large number of random samples of a variable will be close to the
expectation of the variable.  This will happen even if the random variable
itself never actually takes a value close to its expectation.  Using
Chebyshev's Theorem and the facts about variance and expectation, we are
finally in a position to be more precise about this intuitive idea.

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

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

This estimate $S_n/n$ is a random variable with two critical properties:
\begin{eqnarray*}
\expect{\frac{S_n}{n}} & = & \expect{G},\\
\variance{\frac{S_n}{n}} & = & \frac{\variance{G}}{n}.
\end{eqnarray*}

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

Also, by Theorem~\ref{indvar}, since the $G_i$'s are independent, the
variances will add, so
\begin{eqnarray*}
\variance{\frac{S_n}{n}} & = & (\frac{1}{n})^2 \variance{S_n} \hspace{1in}
                             \mbox{by Theorem~\ref{th:const},}\\
& = & (\frac{1}{n})^2 \sum_{i=1}^n \variance{G_i}\\
& = & (\frac{1}{n})^2 n\variance{G}\\
& = & \frac{\variance{G}}{n}.
\end{eqnarray*}

Now Chebyshev's Bound tells us that
\begin{theorem}
\label{devmean}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent variables with the same mean, $\mu$, and deviation, $\sigma$.
Then
\[
\prob{\abs{\frac{S_n}{n} - \mu} \geq x} \leq \frac{1}{n} \left(\frac{\sigma}{x}\right)^2.
\]
\end{theorem}

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

\subsection{Size of a Poll}

Theorem~\ref{devmean} allows us to calculate poll size.  How many people
should we poll to get a reliable estimate of voters' preference?  The
results will be weaker than we previously derived using approximations to
the binomial distribution, but they are still illustrative.

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

Suppose, in particular, we want to know within 0.02 what fraction of the
voters favor Gore.  So we let $x = 1/50$ and conclude from
Theorem~\ref{devmean} that we can, by choosing $n$ large enough, reduce
the probability that our estimate is off by more than $\pm 0.02$ to as close
to zero as we please.

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

Note again that this bound on poll size holds regardless of how large the
total voting population may be---whether we are trying to determine the
preferences of a few tens of thousands of Cambridge voters, or of the tens
of millions of all American voters, the same poll size is adequate.

Now suppose a pollster dutifully checks with 12,500 randomly chosen voters
and finds that 6,300 prefer Gore.  It's tempting, but sloppy, to say that
this means ``With probability 0.95, the fraction of voters who prefer Gore
is $0.504 \pm 0.02$.''  What's objectionable about this statement is that
it talks about the probability of a real world fact, namely the actual
value of the fraction $p$.  But $p$ is what it is, and it simply makes no
sense to talk about the probability that it is something else.  For
example, suppose $p$ is actually 0.53; then it's nonsense to ask about the
probability that it is within 0.02 of 0.504---it simply isn't.

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

Actually, polling 12,500 voters is wildly excessive.  We derived this
bound on poll size solely by applying Chebyshev's Theorem to the value
of the variance of $S_n/n$.  But in fact we know the exact
distribution of $S_n/n$, namely, it has a binomial distribution with
parameters $n,p$.  By a more detailed calculation of probabilities of
deviation from the mean specifically for the binomial distribution, we
can show that the poll size could be more than an order of magnitude
smaller than~12,500. 

\section{The Weak Law of Large Numbers}

The Weak Law of Large Numbers is just a less detailed version of
Theorem~\ref{devmean}.  The Weak Law captures the qualitative behavior of
average of a large number of independent trials: it gets closer and closer
to the expectation as more and more trials are performed.

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

\begin{proof}
Choose $x$ in Theorem~\ref{devmean} to be $\epsilon$---the traditional
symbol for a small positive quantity.  Then, with $\epsilon$ fixed, we can
always choose $n$ large enough to make $(\sigma/x)^2/n$ as small as we
please.  This ensures that, with probability as close to zero as desired, the
average of $n$ samples is within $\epsilon$ of the actual average.  So the
limiting probability must equal zero.
\end{proof}

The Weak Law as it stands has no actual applications.  One problem with
the Weak Law as stated is that, in contrast to Theorem~\ref{devmean} for
example, it does not say anything about the \emph{rate} at which the
limits are approached.  We have just seen that this rate information is
essential in applications such as determining the appropriate size of a
poll.  A second problem with both the Weak Law \emph{as well as}
Theorem~\ref{devmean} is that neither provides any information about the
way the value of the average may be expected to \emph{oscillate} in the
course of an experiment.  There is a Strong Law of Large Numbers which
deals with the oscillations.  Such oscillations may not be important in
our example of polling about Gore's popularity, but they are critical in
gambling situations, where large oscillations can bankrupt a player, even
though the player's average winnings are assured if he survives long
enough.  The problem here with the long run view, as the famous economist
Keynes is alleged to have remarked, is that ``In the long run, we are all
dead.''

\end{document}
