\documentclass[11pt,twoside]{article}

\input{macros-course}

\usepackage{amsmath}

\newcommand{\range}{\operatorname{range}}
\newcommand{\sspace}{\mathcal{S}}

%%  \newcommand{\Pr}{\mathoperator{Pr}}



\begin{document}

\handout{notes-expectation}{Expectation and Variance: Further Notes}{May
11, 1999}

\section{Expectation}
We consider random variables over a sample space $\sspace$.

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

The next lemma gives an alternative way to define expectation.  This
version shows that the expectation of a random variable depends only on
the probability density function~(pdf) of the variable, rather than on the
behaviour of the variable on individual sample points.
\begin{lemma*}
\[
    \expect{R}  = \sum_{r \in \range(R)} r \prob{R = r}
\]

\begin{proof}

Let $[R = r]$ denote the event that~$R = r$.

\begin{align*}
    \sum_{r \in \range(R)} r \cdot \prob{R = r}
        &= \sum_r r \left( \sum_{s \in [R = r]} \prob{s} \right) \\
        &= \sum_r \sum_{s \in [R = r]} r \cdot \prob{s} \\
        &= \sum_r \sum_{s \in [R = r]} R(s) \prob{s} \\
        &= \sum_{s \in \sspace} R(s) \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}

\end{lemma*}

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

\begin{lemma*}[Linearity of Expectation]

Let $R_0$, $R_1$, \dots, be random variables such that the series
$\sum_{i = 0}^\infty R_i$ is absolutely convergent at every sample
point.  Then
\[
    \expect{\sum_{i = 0}^\infty R_i} = \sum_{i = 0}^\infty
    \expect{R_i}.
\]

\begin{proof}

\begin{align*}
\expect{\sum_{i = 0}^\infty R_i}
    &= \sum_{s \in \sspace}
        \left[ [\sum_{i = 0}^\infty R_i](s) \right] \cdot \prob{s} \\
    &= \sum_s \left[ \sum_i R_i(s) \right] \cdot \prob{s} \\
    &= \sum_s \sum_i R_i(s) \cdot \prob{s} \\
    &= \sum_i \sum_s R_i(s) \cdot \prob{s} \\
    &= \sum_i \expect{R_i}.
\end{align*}
\end{proof}

\end{lemma*}

\section{Wald's Theorem}

We want to compute the expected total cost of a process consisting of a
sequence of steps, where the number of steps is itself a random variable.

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 the 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
positive-integer-valued random variable equal to the number of steps to
complete the process, then the expected total cost is precisely the
expectation of $C_1 + C_2 + \dots + C_Q$.  So we would like to verify that
\[
    \expect{C_1 + C_2 + \dots + C_Q} = (\text{Expected cost of a step})
    \cdot \expect{Q}.
\]

One problem with this idea is that the $i$th step may have a different
expectation than the $j$th step.  Another problem is that the expected
cost of a step may depend on $Q$.  However, 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*}[Wald]
Let $C_1$, $C_2$, \dots, be an infinite sequence of random variables,
and let $Q$ be a positive-integer-valued random variable.  Suppose
that for all~$i \geq 1$,
\[
    \expect{ C_i \mid Q \geq i } = \expect{C_1}.
\]
Then
\[
    \expect{C_1 + C_2 + \dots + C_Q} = \expect{C_1} \cdot \expect{Q}.
\]

\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 + \dots + C_Q = \sum_{k = 1}^\infty C_k I_k,
\]
Since only finitely many terms in the infinite sum are nonzero, this series
is absolutely convergent at every sample point.  Therefore,
\begin{eqnarray*}
\lefteqn{\expect{ C_1 + C_2 + \dots + 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
Lecture~22.
\end{proof}

\end{theorem*}

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

\begin{proof}

Define the cost~$C_i$ of the $i$th trial to be zero if it succeeds,
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$, so Wald's Theorem applies:
\[
    1 = \expect{\sum_{i = 1}^Q C_i}
      = \expect{C_1} \cdot \expect{Q}
      = p \cdot \expect{Q},
\]
so
\[
    \expect{Q} = \frac{1}{p}.
\]
\end{proof}

\section{Variance}
For random variable $R$ with mean $\mu$,
\[
\variance{R} ::= \expect{(R - \mu)^2} = \expect{R^2} - \expectsq{R}.
\]

\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 \cdot Y} & = & \expect{X} \cdot \expect{Y},\\
\variance{X + Y} & = & \variance{X} + \variance{Y}.
\end{eqnarray*}
\end{lemma}

\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}[Markov's Bound]\label{markov}
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}[Chebyshev's Bound]\label{chebyshev}
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{\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}
\[
\prob{\abs{\frac{S_n}{n} - \expect{G}} \geq x} \leq \frac{\variance{G}}{nx^2}.
\]
\end{theorem}

This theorem, the first of many such, is a precise statement about how the
average of independent samples of a random variable approaches the mean.

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]
For any $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{S_n}{n} - \expect{G}} \geq \epsilon} = 0,
\]
or equivalently, 
\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{S_n}{n} - \expect{G}} < \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.  However, the Weak
Law is of little actual use---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.  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 remark, ``In the long run, we are all dead,'' is attributed
to the famous economist Keynes, commenting on based on undiscriminating
reliance on expectation in investment policy.)

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