\documentclass[11pt,twoside]{article}

\input{macros-course}

\usepackage{amsmath}

\newcommand{\range}{\operatorname{range}}
\newcommand{\sspace}{\mathcal{S}}
\newcommand{\covar}[1]{{\rm Cov}\left[ #1 \right]}


\begin{document}

\handout{notes-expectation}{Expectation and Variance: Further
Notes}{November 23, 1999}

\section{Real-valued Random Variables}
A \emph{real-valued random variable} over a probability space, $\sspace$,
is a function from $\sspace$ to the real numbers.  We restrict attention to
discrete spaces $\sspace$.

The \emph{probability density function (pdf)} of a random variable, $R$, is
the function $f_R: \reals \to \reals$ defined as:
\[
f_R(r) ::= \sum_{\set{s \mid R(s) = r}} \prob{s}.
\]
The \emph{cumulative density function} of $R$ is the function $F_R: \reals
\to \reals$ defined as:
\[
F_R(r) ::= \sum_{\set{s \mid R(s) \leq r}} \prob{s} = \sum_{\set{r' \in
\range(R) \mid r' \leq r}} f_R(r').
\]

When several random variables are mentioned in the same context, we
tacitly assume they are defined on the same probability space.

\section{Expectation}

\begin{defin*}
The \emph{expectation}, $\expect{R}$, of a random variable~$R$, is
\[
    \expect{R} ::= \sum_{s \in \sspace} R(s) \prob{s},
\]
providing this sum has a well-defined limit.
\end{defin*}

Absolute convergence of the sum on the right is necessary and sufficient
for the expectation to have a well-defined \emph{finite} value.  Another
way to say this is that $\expect{R}$ is finite iff $\expect{\abs{R}}$ is
finite.

A variable may also have a well-defined infinite or negative infinite
value.  For example, a random variable taking the value $-2^n$ with
probability $2^{-n}$ for all $n > 0$, has expectation $-\infty$.  On the
other hand, an random variable taking the values $2^n$ and $-2^n$, each
with probability $2^{-n}/2$ for $n > 0$ does not have a well-defined
expectation.

The next lemma gives an alternative formulation of expectation that many
texts take as its definition.  This formulation shows that the expectation
of a random variable depends only on the pdf of the variable rather than
on the behaviour of the variable on individual sample points.
\begin{lemma}\label{expect-lemma}
\[
    \expect{R}  = \sum_{r \in \range(R)} r \prob{R = r}.
\]
\end{lemma}
The equality above holds in the strong sense that the expectation is
well-defined iff the series on the right has a well-defined limit.

\begin{proof}
Let $[R = r]$ denote the event that~$R = r$.  We leave it to the reader to
verify that if any of the sums in the following derivation are
well-defined, then they all are:
\begin{align*}
    \sum_{r \in \range(R)} r \cdot \prob{R = r}
        &= \sum_r r \cdot [ \sum_{s \in [R = r]} \prob{s} ] \\
        &= \sum_r \sum_{s \in [R = r]} [r \cdot \prob{s}] \\
        &= \sum_r \sum_{s \in [R = r]} [R(s) \cdot \prob{s}] \\
        &= \sum_{s \in \sspace} R(s) \cdot \prob{s}
\end{align*}
The last equality follows from the fact that the events $[R = r]$ for
$r \in \range(R)$ are a partition of the sample space~$\sspace$.
\end{proof}

It follows easily from the definition that
\[
\expect{aR + b} = a \expect{R} + b
\]
for any $a,b \in \reals$.

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

\begin{corollary}\label{finlinexp} [Finite Linearity of Expectation]
Let $R_0, R_1, \dots, R_n$ be random variables with finite expectations.
Then
\[
   \expect{\sum_{i = 0}^n R_i} = \sum_{i = 0}^n \expect{R_i}.
\]
\end{corollary}
\begin{proof}
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.
\end{proof}

\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 two 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 one 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. Lecture 22 Notes.)  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 $10 2^i$ 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$
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$,
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 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.

}

\iffalse

\section{Wald's Theorem}

We want to compute the expected total 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.  Wald's Theorem confirms this.  To state it precisely,
we extend the definition of expectation to be conditional on an event~$A$.

\begin{defin*}
The conditional expectation, $\expect{R \mid A}$, of a random variable, $R$,
given event, $A$, is
\[
    \expect{R \mid A} ::= \sum_{s \in A} R(s) \prob{s \mid A}.
\]
\end{defin*}

We state two easy properties without proof:

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

\begin{theorem} \label{wald} [Wald]
Let $C_1, C_2, \dots,$ be a sequence of nonnegative random variables, and
let $Q$ be a integer-valued positive random variable, all with finite
expectations.  Suppose that
\[
    \expect{ C_i \mid Q \geq i } = \expect{C_1}
\]
for all~$i \geq 1$.  Then
\[
    \expect{C_1 + C_2 + \cdots + C_Q} = \expect{C_1} \cdot \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 \expect{C_k I_k \mid I_k = 1} \cdot \prob{I_k = 1}
                                + \expect{C_k I_k \mid I_k = 0} \cdot \prob{I_k = 0}\\
        &=& \sum_{k = 1}^\infty \expect{C_k \mid I_k = 1} \cdot \prob{I_k = 1} \\
        &=& \sum_{k = 1}^\infty \expect{C_k \mid Q \geq k} \cdot \prob{Q \geq k} \\
        &=& \sum_{k = 1}^\infty \expect{C_1} \cdot \prob{Q \geq k} \\
        &=& \expect{C_1} \cdot \sum_{i = 0}^\infty \prob{Q > i} \\
        &=& \expect{C_1} \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 for Lecture~22.
\end{proof}

As a simple application of Wald's Theorem, we can give another proof of
the result from lecture about mean time to failure:
\begin{corollary}\label{meantime}
In 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, $\expect{ C_i \mid 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,
\begin{eqnarray*}
\expect{\mbox{amount won}} & = & \expect{\mbox{gain on the first
spin}}\cdot \expect{\mbox{number of spins}}\\
& = & 0 \cdot 2 = 0,
\end{eqnarray*}
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.
\fi


\section{Variance}
For random variable $R$ with mean $\mu$,
\[
\variance{R} ::= \expect{(R - \mu)^2}.
\]
It follows from linearity of expectation, that
\[
\variance{R} = \expect{R^2} - \expectsq{R},
\]
as the reader can verify.

\begin{lemma}\label{a2var}
For any $a,b \in \reals$,
\[
\variance{aR+b} = a^2\variance{R}.
\]
\end{lemma}

\begin{proof}
Let $\mu = \expect{R}$, so $\expect{aR+b} = a\mu + b$.  Then
\begin{eqnarray*}
\variance{aR+b} & = & \expect{((aR + b) - (a\mu + b))^2}\\
       & = & \expect{(aR - a\mu)^2}\\
       & = & a^2\expect{(R-\mu)^2}\\
       & = & a^2 \variance{R}.
\end{eqnarray*}
\end{proof}


\begin{lemma}\label{indvar}
If $X,Y$ are independent,
\begin{eqnarray*}
\expect{X Y} & = & \expect{X} \expect{Y},\\
\variance{X + Y} & = & \variance{X} + \variance{Y}.
\end{eqnarray*}
\end{lemma}

\begin{proof}
See F97 Lecture 24 Notes.  \iffalse the next section or\fi
\end{proof}

The \emph{standard deviation}, sometimes just called the \emph{deviation},
of a random variable is the square root of its variance.  Sometimes it's
more convenient to work with the deviation than with the variance.  The
deviation is often denoted by the symbol $\sigma$ and the variance by
$\sigma^2$.


\iffalse
\section{Covariance}

The variance of a random variable is a measure of how it deviates from its
mean.  \emph{Covariance} is a related measure of the similarity between
the distributions of two random variables.

\begin{defin*}
The \emph{covariance} of random variables $X$ and $Y$ is  
\[
\covar{X,Y} = \expect{XY} - \expect{X}\expect{Y}.
\] 
\end{defin*}

An equivalent formulation is
\[
\covar{X,Y} = \expect{(X-\expect{X})(Y- \expect{Y})},
\]
as the reader should check.

If $X$ and $Y$ are positively correlated then their covariance is positive
and if they are negatively correlated their covariance is negative. Their
covariance is zero if they are uncorrelated.

{\em Examples: }
Let $X$ and $Y$ be uniform in the range $[1,6]$.
\begin{enumerate}
\item $X = Y$. In this case, 
\[
\covar{X,Y} = \expect{X^2} - \expectsq{X} = \variance{X} = 2\frac{11}{12}.
\]
The variables are positively correlated. This is not a surprise---they are
always equal.

\item $Y = 7 - X$.  Now,
\begin{eqnarray*}
\covar{X,Y} & =& \expect{X(7-X)} - \expect{X}\expect{7-X}\\
& =  & 7\expect{X} - \expect{X^2} - 7\expect{X}+\expectsq{X}\\
& = & - \expect{X^2} + \expectsq{X}\\
& = & - \variance{X} = -2\frac{11}{12}
\end{eqnarray*}
The variables are negatively correlated, i.e., when one is high the other
is low.  This is reflected by the negative covariance.

\item $X$ are $Y$ are independent, e.g. consecutive coin tosses.
Then 
\[
\covar{X,Y} = \expect{XY} - \expect{X}\expect{Y} = \expect{X}\expect{Y}-\expect{X}\expect{Y} =
0.
\]
The variables are uncorrelated.

\end{enumerate}

So if the variables are independent then, indeed their covariance is zero.
What about the converse?  If the covariance is zero, are the variables
independent?  The answer is no.  For example, let $X, Y$ be in the
range $[1,3]$ such that $\prob{X = i \intersect Y = j} = 1/8$ for all
$(i,j)$ except $(2,2)$, and $\prob{X = Y=2} = 0$.  We can check that this
gives valid probability distributions for $X$ and $Y$:
\begin{eqnarray*}
\prob{X =1} & = & \frac{3}{8},\\
\prob{X =2} & = & \frac{2}{8},\\
\prob{X =3} & = & \frac{3}{8},
\end{eqnarray*}
and these add up to 1. 

The distribution of $X$ is the same as the distribution of $Y$ but
since $\prob{X=2 \mid Y=2} = 0 \neq \prob{X=2}$, the variables $X$ and
$Y$ are not independent.  However,
\begin{eqnarray*}
\covar{X,Y} &=& \expect{XY} - \expect{X}\expect{Y} \\
&=& \sum_{i,j \in [1,3]} ij \prob{X = i \intersect Y = j} - (\sum_{i \in [1,3]}i \prob{X = i})^2\\
&=& \frac{1}{8} (1+2+3+2+6+3+6+9) - (\frac{3}{8}(1+3) + \frac{2}{8}2)^2\\
&=& 4-4 = 0.
\end{eqnarray*}


\begin{theorem}
For random variables $X$ and $Y$,
\[
\variance{X+Y} = \variance{X} + \variance{Y}  + 2\covar{X,Y}.
\]
\end{theorem}

\begin{proof}
\begin{eqnarray*}
\variance{X+Y} &=& \expect{(X+Y - \expect{X+Y})^2}\\
&=& \expect{X^2+Y^2 + 2XY -2(X+Y)\expect{X+Y} + \expectsq{X+Y}}\\
&=& \expect{X^2+Y^2 + 2XY -2(X+Y)(\expect{X}+\expect{Y})
+ \expectsq{X} + \expectsq{Y} + 2\expect{X}\expect{Y}}\\
&=& \expect{X^2} +\expect{Y^2} + 2\expect{XY} - 2\expectsq{X} -
\expectsq{Y} -4\expect{X}\expect{Y} +\\
&& \qquad \expectsq{X} + \expectsq{Y} + 2\expect{X}\expect{Y}\\
&=& \expect{X^2} - \expectsq{X} + \expect{Y^2} - \expectsq{Y} + 2\expect{XY}  -2\expect{X}\expect{Y}\\
&=& \variance{X} + \variance{Y} + 2\covar{X,Y}.
\end{eqnarray*}
\end{proof}

As a corollary we have:
\begin{corollary}
If $X$ and $Y$ are independent, then 
\[
\variance{X+Y} = \variance{X}+\variance{Y}.
\]
\end{corollary}

\begin{proof}
If $X,Y$ are independent, then $\covar{X,Y} = 0$.
\end{proof}

A similar result holds for the sum of many independent random variables ---
but only needs that the variables are {\em pairwise} independent.

\begin{theorem}
If $X,\ldots,R_n$ are pairwise independent random variables, then
\[
\variance{R_1+ \cdots +R_n} = \sum_{i=1}^n \variance{R_i}.
\]
\end{theorem}

The proof is simple and follows from the definition of variance.
We won't do it here.
\fi


\section{Markov and Chebyshev Bounds}
\subsection{Review}
The theorems of Markov and Chebyshev give upper bounds on the probability
that a random variable differs by a given amount from its mean.  The
Markov bound holds solely under the hypothesis that the variable is
nonnegative and the expectation exists, i.e., is finite.  The Chebyshev
bound holds solely under the hypothesis that the variance exists.
(Remember that the variance can exist only if the expectation does.)

\begin{theorem}\label{markov} [Markov's Bound]
If R is a non-negative random variable with finite expectation, then for
all $x > 0$,
\[
\prob{R \geq x} \leq  \frac{\expect{R}}{x}
\]
\end{theorem}

Setting $x = c \cdot \expect{R}$ allows Markov's Theorem to be expressed
in an alternate form:

\begin{corollary}
If R is a non-negative random variable with finite expectation, then for all $c > 0$
\[
\prob{R \geq c \cdot \expect{R}}  \leq  \frac{1}{c}
\]
\end{corollary}

\begin{theorem}\label{chebyshev}[Chebyshev's Bound]
Let $R$ be a random variable with finite variance, and let $x$ be a
positive real number.  Then
\[
\prob{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\end{theorem}

\subsection{The Weak Law of Large Numbers}

The intuition behind the definition of expectation is 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
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 yield 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 ::= \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 Lemma~\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 Lemma~\ref{a2var},}\\
& = & (\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}

This theorem 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.

A simple consequence of Theorem~\ref{devmean} is The Weak Law of Large
Numbers.  Let's first rename $x$ to be $\epsilon$---the traditional symbol
for a small positive quantity.  Then, with $\epsilon$ fixed, we can always
choose $n$ large enough to ensure that, with probability as close to one
as desired, the average of $n$ samples is within $\epsilon$ of the actual
average.  We can state this as a limit theorem:

\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$ are mutually
independent variables with the same mean and variance.  For any $\epsilon
> 0$,
\[
\lim_{n \rightarrow \infty}
 \prob{\abs{\frac{S_n}{n} - \expect{\frac{S_n}{n}}} \geq \epsilon}
 = 0,
\]
or equivalently, 
\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{S_n}{n} - \expect{\frac{S_n}{n}}} < \epsilon} = 1,
\]
\end{theorem}

This Weak Law of Large Numbers serves as a helpful reminder of how to
formulate estimation of the mean by average sampling.  It is the most
elementary of many such theorems.  However, the Weak Law as it stands has
no actual applications---first because it does not say anything about the
\emph{rate} at which the limits are approached (rate information is
essential in applications), and second, because it provides no 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.''

\subsection{Size of a Poll}
Chebyshev's Theorem~\ref{devmean} allows us to calculate how many voters
to poll if we want to get a reliable estimate of voters' preference for
Gore.

\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 $\pm0.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 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 would be 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$.''

By the way, polling 12,500 voters is wildly excessive.  We derived this
bound on poll size solely by applying Chebyshev's Theorem to 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 (cf. Lecture 21 Notes), we can
show that the poll size could be more than an order of magnitude smaller
than 12,500.

\end{document}
