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

\begin{document}

\lecture{walds theorem}{Computing Expectation}{8 May 2001}

This lecture continues the discussion of expected value.
In the last lecture, we looked at the expected value of a \emph{sum} of
random variables.  The main result, called linearity of expectation,
says that the expected value of a sum is the sum of the expected
values; that is, $\Ex(R_1 + R_2) = \Ex(R_1) + \Ex(R_2)$.  The
wonderful thing about linearity of expectation is that $R_1$ and $R_2$
need not be independent.

In this lecture, we will first look at the expected value of a
\emph{product} of random variables.  If $R_1$ and $R_2$ are
\emph{independent}, then an analogous result holds.  Namely, the
expected value of a product is the product of the expected values.

We will then study the expectation of a sum containing a random number
of terms. It turns out that expectation is in some sense linear also
for those sums, provided that the random variables involved are not
too dependent.



\section{Conditional Expectation}

Just like event probabilities, expectations can be conditioned on some
event.
\begin{definition}
The \emph{conditional expectation of $X$ given event $A$}, written
$\Ex[X \mid A]$ is
\[
\sum_x x \cdot\Pr(X=x \mid A)
\]
\end{definition}
In other words, it is the expected value of the variable $X$ once we
skew the distribution of $X$ to be conditioned on event $A$.
\begin{example}
  Let $D$ be the outcome of a random fair die role.  What is $E[D \mid
  D \ge 4]$?
  \begin{displaymath}
    \sum_{i=1}^6 i \cdot \Pr(D=i \mid D \ge 4) 
    = \sum_{i=4}^6 i \cdot 1/3
    = 5
  \end{displaymath}
\end{example}
Since $E[X \mid A]$ is just an expectation over a different
probability distribution, it is unsurprising that the rules for
expectation extend to conditional expectation:
\begin{theorem}
  $\Ex(X+Y \mid A) = \Ex(X \mid A) + \Ex(Y \mid A)$.
\end{theorem}
A real benefit of conditional expectation is the way it lets you
divide complicated expectation calculations into simpler ones.
\begin{theorem}
  \label{thm:condexp}
  Let $A_1,A_2,\cdots$ be a partition of the sample space: that is,
  $\cup A_i$ is the entire sample space, but $A_i \cap A_j = \emptyset$
  for any $i \ne j$.  Then
  \[
  \Ex(X) = \sum_i \Ex(X \mid A_i) \Pr(A_i)
  \]
  provided that all the expectations exist and are finite.  
\end{theorem}
\begin{proof}
  \begin{align*}
    \Ex(X) &= \sum_x x \cdot\Pr(X=x)\\
    &= \sum_x x \cdot \sum_i \Pr(X=x \mid A_i) \Pr(A_i)\\
    &= \sum_i \sum_x x \cdot \Pr(X=x \mid A_i) \Pr(A_i)\\
    &= \sum_i \Pr(A_i) \sum_x x \cdot \Pr(X=x \mid A_i)\\
    &= \sum_i \Pr(A_i) \Ex(X \mid A_i)
  \end{align*}
\end{proof}
\begin{example}
  Half the people in the world are male, half female.  The expected
  height of a randomly chosen male is $5'11''$, while the expected
  height of a randomly chosen female is $5'5''$.  What is the expected
  height of a randomly chosen individual?
  
  Let $H(P)$ be the height of the randomly person $P$.  The events
  $M=$``$P$ is male'' and $F=$``$P$ is female'' are a partition of the
  sample space (at least for the moment---though with modern science
  you never know).  Then
  \begin{align*}
    \Ex(H) &= \Ex(H \mid M) \Pr(M) + \Ex(H \mid F) \Pr(F)\\
    &= 5'11'' \cdot \frac12 + 5'5'' \cdot \frac12\\
    &= 5'8''
  \end{align*}
\end{example}
We will see in the following sections that the law of total probability 
has much more power than one might think.



\section{The Expected Value of a Product}

In the previous lecture we saw that expectation is a linear operator,
i.e., that the expectation of a sum is the sum of the expectations.
The same is not always true for products, but it is true in an
important special case: when the random variables are independent.
\begin{theorem}
  \label{th:prod}
  For any two \emph{independent} random variables $R_1$ and $R_2$
  \[
  \Ex(R_1 \cdot R_2) = \Ex(R_1) \cdot \Ex(R_2)
  \]
\end{theorem}
\begin{proof}
  We will transform the left side into the right side.  We first use
  the definition of expected value.
  \begin{displaymath}
    \Ex(R_1 \cdot R_2)
    = \sum_{x \in \text{Range}(R_1 \cdot R_2)}
    x \cdot \Pr(R_1 \cdot R_2 = x)
  \end{displaymath}
  Next, we break the summation over the product $R_1 \cdot R_2$ into
  separate sums over $R_1$ and $R_2$.
  \begin{displaymath}
    \Ex(R_1 \cdot R_2) = \sum_{x_2 \in \text{Range}(R_2)} \quad
    \sum_{x_1 \in \text{Range}(R_1)}
    x_1 x_2 \cdot \Pr((R_1 = x_1) \cap (R_2 = x_2))
  \end{displaymath}
  We now use the fact that $R_1$ and $R_2$ are independent.  The
  probability of the intersection of the events $R_1 = x_1$ and $R_2 =
  x_2$ is the product of the probabilities of the two events.
  \begin{displaymath}
    \Ex(R_1 \cdot R_2)
    = \sum_{x_2 \in \text{Range}(R_2)}
    \sum_{x_1 \in \text{Range}(R_1)}
    x_1 x_2 \cdot \Pr(R_1 = x_1) \cdot \Pr(R_2 = x_2)
  \end{displaymath}
  In the remaining four steps, we alternate pulling a term out of a
  summation and applying the definition of expected value.
  \begin{eqnarray*}
    \Ex(R_1 \cdot R_2)
    & = &   \sum_{x_2 \in \text{Range}(R_2)} x_2 \cdot \Pr(R_2 = x_2)
    \sum_{x_1 \in \text{Range}(R_1)} x_1 \cdot \Pr(R_1 = x_1) \\
    & = &   \sum_{x_2 \in \text{Range}(R_2)} x_2 \cdot \Pr(R_2 = x_2)
    \cdot \Ex(R_1) \\
    & = &   \Ex(R_1) \sum_{x_2 \in \text{Range}(R_2)}
    x_2 \cdot \Pr(R_2 = x_2) \\
    \\
    & = &   \Ex(R_1) \cdot \Ex(R_2)
  \end{eqnarray*}
\end{proof}
There is also a slick proof of Theorem~\ref{th:prod} using the law of
total probability.
\begin{proof}[Proof of Theorem~\ref{th:prod}]
  We apply the law of total probability by conditioning on the value
  of~$R_1$.
  \begin{displaymath}
    \Ex(R_1 \cdot R_2)
    =
    \sum_{x \in \text{Range}(R_1)}
      \Ex(R_1 \cdot R_2 \given R_1 = x) \Pr(R_1 = x)
  \end{displaymath}
  Now notice that
  \begin{displaymath}
    \Ex(R_1 \cdot R_2 \given R_1 = x)
    =
    \Ex(x \cdot R_2 \given R_1 = x)
    =
    x \Ex(R_2 \given R_1 = x)
    =
    x \Ex(R_2),
  \end{displaymath}
  where the second step follows since~$x$ is a constant, i.e., not a
  random variable, and the last step follows since $R_1$ and~$R_2$ are
  independent. Putting everything together,
  \begin{displaymath}
    \Ex(R_1 \cdot R_2)
    =
    \sum_{x \in \text{Range}(R_1)} x \Ex(R_2) \Pr(R_1 = x)
    =
    \Ex(R_2) \sum_{x \in \text{Range}(R_1)} x \Pr(R_1 = x)
    =
    \Ex(R_1) \Ex(R_2).
  \end{displaymath}
  The reason we could pull $\Ex(R_2)$ out of the summation is that it
  it does not depend on the summation index~$x$.
\end{proof}



\subsection{The Product of Two Independent Dice}

Suppose we throw two independent, fair dice and multiply the numbers
that come up.  What is the expected value of this product?

Let random variables $R_1$ and $R_2$ be the numbers shown on the two
dice.  We can compute the expected value of the product as follows:
\begin{displaymath}
  \Ex(R_1 \cdot R_2)
  = \Ex(R_1) \cdot \Ex(R_2)
  = 3\frac{1}{2} \cdot 3\frac{1}{2}
  = 12\frac{1}{4}
\end{displaymath}
The first step uses Theorem~\ref{th:prod} and the fact that the dice
are independent.  In the second step, we use the result from last
lecture that the expected value of one die is $3 \frac{1}{2}$.  The
last step is simplification.  The expected value of the product is
$12\frac{1}{4}$.



\subsection{The Product of Two Dependent Dice}

Suppose that the two dice are not independent; in fact, assume that
the second die is always the same as the first.  Now what is the
expected value of the product?

Because the dice are not independent, we can no longer apply
Theorem~\ref{th:prod}.  However, is the expected value of the product
really changed by this loss of independence?  As before, let random
variables $R_1$ and $R_2$ be the numbers shown on the two dice.  We
can compute the expected value of the product without
Theorem~\ref{th:prod} as follows:
\begin{eqnarray*}
\Ex(R_1 \cdot R_2)
        & = &   \Ex(R_1^2) \\
        & = &   \sum_{i=1}^6 i^2 \cdot \Pr(R_1 = i) \\
        & = &   \frac{1^2}{6} + \frac{2^2}{6} + \frac{3^2}{6} + 
                \frac{4^2}{6} + \frac{5^2}{6} + \frac{6^2}{6} \\
        & = &   15 \frac{1}{6}
\end{eqnarray*}
The first step uses the fact that the outcome of the second die is
always the same as the first.  In the second step, we expand
$\Ex(R_1^2)$ according to the definition of expected value.  In the
third step, we use the fact that the probability of each number coming
up is $\frac{1}{6}$, since the dice are fair.  The last step is
simplification.  The expected value of the product has changed to $15
\frac{1}{6}$.

The preceding two examples show that for \emph{dependent} variables,
the expected value of a product need not be the product of the
expected values; that is, $\Ex(R_1 \cdot R_2) \neq \Ex(R_1) \cdot
\Ex(R_2)$.  The general rules for expected values of sums and products
are summarized below:

\bigskip

\fbox{\parbox{6.25in}{
\vspace{.25cm}
For random variables $R_1$ and $R_2$:
\begin{itemize}
\item Regardless of whether $R_1$ and $R_2$ are independent,
$\Ex(R_1 + R_2) = \Ex(R_1) + \Ex(R_2)$.
\item If $R_1$ and $R_2$ are independent, then $\Ex(R_1 \cdot R_2) =
\Ex(R_1) \cdot \Ex(R_2)$.
\end{itemize}
}}

\subsection{Corollaries}

Theorem~\ref{th:prod} extends to a collection of mutually independent
variables.
\begin{corollary}
  If random variables $R_1, R_2, \ldots, R_n$ are mutually
  independent, then
  \[
  \Ex(R_1 \cdot R_2 \cdots R_n) = \Ex(R_1) \cdot \Ex(R_2) \cdots \Ex(R_n)
  \]
\end{corollary}
The proof of the corollary is an induction argument using
Theorem~\ref{th:prod} and the definition of mutual independence.
Details are omitted here.

Adjusting a random variable by an additive or multiplicative constant
adjusts the expected value in the same way.
\begin{corollary}
  If $R$ is a random variable and $a$ and $b$ are constants, then
  $\Ex(a R + b) = a \Ex(R) + b$.
\end{corollary}
This corollary is proved by regarding $a$ and $b$ as random variables
that take on a particular value with probability 1.  We can prove that
$a$ is always independent of $R$.  The result then follows from
linearity of expectation and Theorem~\ref{th:prod}.



\section{The Danger of Expectation of Quotients}

We now know the expected value of a sum or product of random
variables.  Unfortunately, the expected value of a reciprocal is not
so easy to characterize.  Here is a flawed attempt.
\begin{falsethm}
  \label{cor:false}
  If $Z$ and $R$ are independent random variables with $R\ne 0$ (that
  is, $R$ can never be 0) then $\Ex(Z/R) = \Ex(Z)/\Ex(R)$
\end{falsethm}
\begin{proof}[Incorrect proof]
  $\Ex(Z) = \Ex((Z/R) \cdot (R)) = \Ex(Z/R) \cdot \Ex(R)$ by
  Theorem~\ref{th:prod}. Now divide both sides by $\Ex(R)$.
\end{proof}
This proof is bogus!  We can not apply Theorem~\ref{th:prod} in the
second step, because $Z/R$ and $R$ are not necessarily independent.
Indeed, one can see the likely dependence: $R$ being large will make
$Z/R$ small. Of course, a bogus proof does not mean a false theorem,
so here is a counterexample:
\begin{example}
  Suppose the random variable $Z=1$ always (with probability 1), while
  the random variable $R$ is 1 with probability $\frac{1}{2}$ and is 2
  with probability $\frac{1}{2}$.  Then
  \begin{eqnarray*}
    \frac{1}{\Ex(R)}
    = \frac{1}{1 \cdot \frac{1}{2} + 2 \cdot \frac{1}{2}}
    = \frac{2}{3} \\
    \Ex(\frac{1}{R})
    = \frac{1}{1} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2}
    = \frac{3}{4}
  \end{eqnarray*}
  The two quantities are not equal, so the theorem is false.    
\end{example}



\subsection{A RISC Paradox}

Unfortunately, the fact that Corollary~\ref{cor:false} is false, does
not mean that it is never used!  The following data is taken from a
paper by some famous professors.  They wanted to show that programs on
a RISC processor are generally shorter than programs on a CISC
processor.  For this purpose, they made a table of program lengths for
some benchmark problems:
\[
\begin{array}{lccc}
\text{Benchmark}        & \text{RISC}   & \text{CISC}   & \text{CISC / RISC}\\
\hline
\text{E-string search}  & 150           & 120           & 0.8 \\
\text{F-bit test}       & 120           & 180           & 1.5 \\
\text{Ackerman}         & 150           & 300           & 2.0 \\
\text{Rec 2-sort}       & 2800          & 1400          & 0.5 \\
\hline
\text{Average}          &               &               & 1.2
\end{array}
\]
Each row contains the data for one benchmark.  The numbers in the
first two columns are program lengths for each type of processor.  The
third column contains the ratio of the CISC program length to the RISC
program length.  Averaging this ratio over all benchmarks gives the
value 1.2 in the lower right.  The authors conclude that ``CISC
programs are 20\% longer on average''.

This reasoning is wrong!  One problem is that the total amount of RISC
code for all benchmarks is $3220$ bytes versus $2000$ bytes for the
CISC processor.  In other words, the RISC code is much {\em longer}
overall.  One could argue, however, that this is a bad calculation,
since one large, atypical benchmark (e.g. Rec 2-sort) could skew the
whole result.

However, there is a second problem that can not be waved away.
Suppose we redo the final column, taking the other ratio, RISC /
CISC instead of CISC / RISC.
\[
\begin{array}{lccc}
\text{Benchmark}        & \text{RISC}   & \text{CISC}   & \text{RISC / CISC}\\
\hline
\text{E-string search}  & 150           & 120           & 1.25 \\
\text{F-bit test}       & 120           & 180           & 0.67 \\
\text{Ackerman}         & 150           & 300           & 0.5 \\
\text{Rec 2-sort}       & 2800          & 1400          & 2.0 \\
\hline
\text{Average}          &               &               & 1.1
\end{array}
\]
From this table, we would conclude that RISC programs are 10\% longer
than CISC programs on average!  We are using the same reasoning as in
the paper, so this conclusion is equally justifiable--- yet the result
is opposite!  What is going on?



\subsection{A Probabilistic Interpretation}

To shed some light on this paradox, we can model the RISC vs. CISC
debate with the machinery of probability theory.

Let the sample space be the set of benchmark programs.  Let the random
variable $R$ be the length of the RISC program, and let the random
variable $C$ be the length of the CISC program.  We would like to
compare the average length of a RISC program, $\Ex(R)$, to the average
length of a CISC program, $\Ex(C)$.

To compare average program lengths, we must assign a probability to
each sample point; in effect, this assigns a ``weight'' to each
benchmark.  One might like to weigh benchmarks based on how frequently
similar programs arise in practice.  Lacking such data, however, we
will assign all benchmarks equal weight; that is, our sample space is
uniform.  We can now compute $\Ex(R)$ and $\Ex(C)$ as follows:
\begin{eqnarray*}
\Ex(R)  & = &   \sum_{i \in \text{Range(R)}} i \cdot \Pr(R = i) \\
        & = &   \frac{150}{4}+\frac{120}{4}+\frac{150}{4}+\frac{2800}{4} \\
        & = &   805 \\
\\
\Ex(C)  & = &   \sum_{i \in \text{Range(C)}} i \cdot \Pr(C = i) \\
        & = &   \frac{120}{4}+\frac{180}{4}+\frac{300}{4}+\frac{1400}{4} \\
        & = &   500
\end{eqnarray*}
Since $\Ex(R)/\Ex(C) = 1.61$, we conclude that the average RISC
program is 61\% longer than the average CISC program.  This is a third
answer, completely different from the other two!  Furthermore, this
answer makes RISC look really bad in terms of code length.  In fact,
both of the earlier results are wrong, and this one is correct.

In terms of our probability model, the paper computes $C / R$ for each
sample point, and then averages to obtain $\Ex(C / R) = 1.2$.  This
much is correct.  However, the authors then conclude that ``CISC
programs are 20\% longer on average''; that is, they conclude that
$\Ex(C) = 1.2 \ \Ex(R)$.  The authors have applied
Corollary~\ref{cor:false}, which we know to be false!

Similarly, our calculation correctly showed that $\Ex(R/C) = 1.1$.
However, we then applied the false corollary to conclude that $\Ex(R)
= 1.1 \ \Ex(C)$; that is, a RISC program is 10\% longer than a CISC
program on average.  Since both arguments are false, it should come as
no surprise that they give contradictory conclusions!



\subsection{A Simpler Example}

The source of the problem is more clear in the following, simpler
example.  Suppose the data were as follows.
\[
\begin{array}{lcccc}
\text{Benchmark}        & \text{Processor A}    & \text{Processor B}
                        & B / A                 & A / B  \\
\hline
\text{Problem 1}        & 2                     & 1             
                        & 1/2                   & 2 \\
\text{Problem 2}        & 1                     & 2
                        & 2                     & 1/2 \\
\hline
\text{Average}          &                       &
                        & 1.25                  & 1.25
\end{array}
\]
Now the data for the processors A and B is exactly symmetric; the two
processors are equivalent.  Yet, from the third column we would
conclude that Processor B programs are 25\% longer on average, and
from the fourth column we would conclude that Processor A programs are
25\% longer on average.  Both conclusions are obviously wrong.  The
moral is that one must be very careful in summarizing data.  Do not
take an average of ratios blindly!



\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. Specifically it provides a formula that computes the
expectation of $X_1 + X_2 + \cdots + X_Q$ where $Q$~is a random
variable taking values in the positive integers and the $X_i$~are
independent identically distributed random variables. At first it
would seem that we just could use lineraity of expectation, but note
that the number of terms in the sum is itself a random variable. It
turns out that it is very important to specify the ways in which $Q$
can depend on the~$X_i$; we will study two setups, the first is a
special case of the second.



\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}
    \Ex(X_1 + X_2 + \ldots + X_Q) = \Ex(X) \cdot \Ex(Q),
  \end{displaymath}
  where $X$~is a random variable with the same distribution as
  the~$X_i$.
\end{theorem}
\begin{proof}
  We rewrite $\Ex(X_1 + X_2 + \ldots + X_Q)$ using the law of total
  probability.
  \begin{displaymath}
    \Ex(X_1 + X_2 + \ldots + X_Q)
    =
    \sum_{q=1}^{\infty} \Ex(X_1 + X_2 + \ldots + X_Q \given Q = q) \Pr(Q = q).
  \end{displaymath}
  For every~$q$,
  \begin{displaymath}
    \Ex(X_1 + X_2 + \ldots + X_Q \given Q = q) = 
    \Ex(X_1 + X_2 + \ldots + X_q \given Q = q) = q \Ex(X \given Q = q),
  \end{displaymath}
  and since we assumed that the~$X_i$ are independent of~$Q$,
  \begin{displaymath}
     q \Ex(X \given Q = q) = q \Ex(X).
  \end{displaymath}
  Therefore,
  \begin{displaymath}
    \Ex(X_1 + X_2 + \ldots + X_Q)
    =
    \sum_{q=1}^{\infty} q \Ex(X) \Pr(Q = q)
    =
    \Ex(X) \sum_{q=1}^{\infty} q \Pr(Q = q)
    =
    \Ex(X) \Ex(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) = \frac{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:
  \begin{displaymath}
    \Ex(R_1 + \ldots + R_Q)
    = \Ex(R) \cdot \Ex(Q)
    = \frac{7}{2} \cdot \frac{5}{2}
    = \frac{35}{4}\,.
  \end{displaymath}
\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 $\Ex(|X_i|) \leq \infty$ and let $Q$~be a
  stopping time with respect to this sequence. Then, if $\Ex(Q) <
  \infty$,
  \begin{displaymath}
    \Ex(X_1 + X_2 + \ldots + X_Q) = \Ex(X) \cdot \Ex(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\{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
  $\Ex(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 $\Ex(|X_i|) \leq \infty$ and let $Q$~be a random variable
  taking values in the positive integers. Then, if $\Ex(Q) < \infty$,
  \begin{displaymath}
    \Ex(X_1 + X_2 + \ldots + X_Q)
    = \sum_{i=1}^{\infty} \Ex(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 $\Ex(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, $\Ex(X_i I_{\{Q \geq i\}})
  = \Ex(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}
    \Ex(X_i I_{\{Q \geq i\}}) =
    \Ex(X_i) - \sum_{q=0}^{i-1} \Ex(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 $\Ex(X_i I_{\{Q = q\}}) = \Ex(X_i) \Ex(I_{\{Q = q\}})$
  for all $q < i$, which implies that
  \begin{displaymath}
    \Ex(X_i I_{\{Q \geq i\}}) =
    \Ex(X_i) - \sum_{q=0}^{i-1} \Ex(X_i) \Pr(Q = q) =
    \Ex(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}
    \Ex(X_1 + X_2 + \ldots + X_Q)
    =
    \Ex\biggl(\sum_{i=1}^{\infty} X_i I_{\{Q \geq i\}}\biggr)
    =
    \sum_{i=1}^{\infty} \Ex(X_i I_{\{Q \geq i\}})
  \end{displaymath}
  By Lemma~\ref{lem:wald-independence}, $\Ex(X_i I_{\{Q \geq i\}}) =
  \Ex(X) \Pr(Q \geq i)$. Putting this together gives
  \begin{displaymath}
    \Ex(X_1 + X_2 + \ldots + X_Q)
    =
    \sum_{i=1}^{\infty} \Ex(X) \Pr(Q \geq i)
    =
    \Ex(X) \sum_{i=1}^{\infty} \Pr(Q \geq i)
    =
    \Ex(X) \Ex(Q),
  \end{displaymath}
  where we used the ``alternative'' formula for the expected value in
  the last step.
\end{proof}



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

\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 $\Ex(T)$, the expected number of steps needed
to complete the system. We want to apply Wald's Theorem to obtain that
\begin{displaymath}
  \Ex(T) = \Ex\biggl(\sum_{k=1}^Q R_k\biggr) = \Ex(Q) \cdot \Ex(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, $\Ex(|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 $\Ex(Q)$ is finite by actually
computing it.



\subsection{Computing the Expected Number of Tries}

Let's compute $\Ex(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 encountered this
question in another guise during the last lecture.  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
$\frac{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 $\frac{1}{(1-p)^n}$.  Therefore, we have:
\[
\Ex(Q) = \frac{1}{(1-p)^n}
\]
This also shows that $Q$ is finite, provided $p \neq 1$.



\subsection{Computing Expected Length of a Try}

Now let's compute $\Ex(R)$, the expected number of steps in a try.
Since the number of steps in a try is always a non-negative integer,
we can write:
\begin{displaymath}
  \Ex(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*}
\Ex(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*}
Now we can compute the expected number of steps needed to complete the
system.
\begin{eqnarray*}
\Ex(T)  & = & \Ex(Q) \cdot \Ex(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 completed 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 time 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 time 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!

\end{document}
% LocalWords:  CISC Rec vs Wald's Mir's np
