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

%\renewcommand{\Ex}{\text{Ex}}

\begin{document}

\lecture{notes23}{Lecture Notes}{2 May 2000}

\begin{outline}
\section{The Expected Value of a Product}

This lecture continues the discussion of expected value.

In the last lecture, we looked at the expected value of a {\em 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 look at the expected value of a {\em product}
of random variables.  If $R_1$ and $R_2$ are independent, then an
analogous result holds.  Namely, the expected value of a product is
the product of the expected values.

\begin{theorem}
\label{th:prod}
For any two {\em 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{eqnarray*}
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{eqnarray*}

Next, we break the summation over the product $R_1 \cdot R_2$ into
separate sums over $R_1$ and $R_2$.

\begin{eqnarray*}
\quad \quad
        & = &   \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{eqnarray*}

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{eqnarray*}
\quad \quad
        & = &   \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) \cdot \Pr(R_2 = x_2)
\end{eqnarray*}

In the remaining four steps, we alternate pulling a term out of a
summation and applying the definition of expected value.

\begin{eqnarray*}
\quad \quad
        & = &   \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}

\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{eqnarray*}
\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{eqnarray*}

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 {\em 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.

\begin{nooutline}
\vspace{0.5cm}

\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}
}}
\end{nooutline}

\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}
\begin{align*}
\Ex(Z) &= \Ex((Z/R) \cdot (R))\\
&=\Ex(Z/R) \cdot \Ex(R)
\end{align*}
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:

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 we have:

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


\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''.

There is a nasty problem with this line of argument.  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?



The answer is that the English language is a wonderful source of
ambiguity in dealing with mathematical problems.  The main problem
here is that although what the paper says is technically true, the
English used is \emph{implying} something entirely different which is
\emph{not true} for the given data.
\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!

\subsection{A Probabilistic Interpretation}


We need to pin down exactly what is meant by the phrase ``20\% longer
on the average.''  To shed some light on this issue, we can model the
RISC vs. CISC debate with the machinery of probability theory, where
``on the average'' has a well defined meaning.

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.  

Now we see the potential confusion from the phrase ``20\% longer on
average.''  Are we talking about $\Ex(C/R)$, or are we talking about
$\Ex(C)/\Ex(R)$?  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$.  The authors then use fuzzy English to say that
``CISC programs are 20\% longer on average'' Similarly, our
calculation correctly showed that $\Ex(R/C) = 1.1$.

On the other hand, we can compute $\Ex(R)/\Ex(C)$ and state that ``RISC
programs at 61\% longer on the average.''

So which one is right?  Well that really depends.  If you imagine John
Smith being given a random program, and compiling RISC and CISC
versions, you might say that on average John will see that RISC is
shorter ($\Ex(C/R)=1.2$), and be very happy with RISC.  But we have
seen that this argument is kind of self contradictory, since also
$\Ex(R/C)>1$.  And it probably is \emph{not} what you would think if
someone told you you ``shorter on average.''  The measure
$\Ex(R)/\Ex(C)$ is a much closer match to our intuition.  It says that
if we compiled a lot of RISC programs, we would expect their total
length to be substantially greater than of the corresponding CISC
programs.


\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{align*}
\sum_{i=1}^6 i \cdot \Pr(D=i \mid D \ge 4) &= \sum_{i=4}^6 i \cdot
1/3\\
&= 5
\end{align*}
\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}
In other words, tree diagrams work for expectations too.
\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}

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

\subsection{Theorem Statement}

\begin{theorem}[Wald's Theorem]
Let $Q$ be a random variable with range $\mathbb{N}$, and let 
$R_1, R_2, R_3, \ldots$ be random variables with countable ranges such
that
\begin{enumerate}
\item All $R_i$ have the same distribution.
\item For all $i$, random variable $R_i$ is independent of the event
  $Q \ge i$
\end{enumerate}
Then
\begin{eqnarray*}
  \Ex(R_1 + R_2 + \ldots + R_Q) & = & \Ex(R_1) \cdot \Ex(Q) \\ 
\end{eqnarray*}

\noindent provided that the expectations on the right exist and are finite.
\end{theorem}
The condition in the theorem requires that every random variable $R_i$
appearing in the sum $R_1 + R_2 + \ldots + R_Q$ to have the same
distribution as a ``reference'' random variable $R$.

The second, ``independence'' condition in the theorem needs to be
explained.  It mixes our previous notions of independence of events
and independence of random variables in a natural way.  It means that
that each event $R_i=x$ is independent of the event $Q \ge i$.

The coin-and-dice problem is solved easily using 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{eqnarray*}
\Ex(R_1 + \ldots + R_Q)
        & = &   \Ex(R) \cdot \Ex(Q) \\
        & = &   \frac{7}{2} \cdot \frac{5}{2} \\
        & = &   \frac{35}{4} \\
\end{eqnarray*}

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

\subsection{Proof Preliminary}

The proof of Wald's Theorem requires a fact, which we state without
proof.  It generalizes linearity of expectation to the case of an
infinite sum.

\begin{fact}
\label{fact:linexp}
Let $R_1, R_2, R_3, \ldots$ be random variables with countable ranges.
If the summation

\[
\sum_{i=1}^{\infty} | R_i |
\]

converges for all points in the sample space, then

\begin{eqnarray*}
\Ex\left(\sum_{i=1}^{\infty} R_i\right) & = & \sum_{i=1}^{\infty} \Ex(R_i). \\
\end{eqnarray*}
\end{fact}



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

\subsection{Proof of Wald's Theorem}

We want to prove that

\begin{eqnarray*}
\Ex(R_1 + R_2 + \ldots + R_Q) & = & \Ex(R) \cdot \Ex(Q).
\end{eqnarray*}

The sum $R_1 + R_2 + \ldots + R_Q$ is awkward, because the final
subscript $Q$ is a random variable.  We eliminate this awkwardness by
introducing some indicator random variables.  In particular, let $I_i$
be an indicator for the event that $R_i$ appears in the sum $R_1 +
R_2 + \ldots + R_Q$; that is, $I_i$ is the event that $Q \geq i$.
With this definition, we can rewrite the sum as follows.

\begin{eqnarray*}
R_1 + R_2 + \ldots + R_Q        & = &   \sum_{i=1}^{\infty} R_i \cdot I_i
\end{eqnarray*}

In effect, the indicator variables $I_i$ ``mask out'' random variables
$R_i$ that do not appear in the sum $R_1 + R_2 + \ldots + R_Q$.
The proof of Wald's Theorem begins by taking the expected value of
both sides of this equation.  Then
\begin{eqnarray*}
\Ex(R_1 + R_2 + \ldots + R_Q)
        & = &   \Ex\left( \sum_{i=1}^{\infty} R_i \cdot I_i \right) \\
\end{eqnarray*}

According to Fact~\ref{fact:linexp}, we can apply linearity of
expectation to break up this infinite sum provided that the sum

\[
\sum_{i=1}^{\infty} | R_i \cdot I_i |
\]

\noindent always converges.  At each point in the sample space, the random
variable $Q$ takes on some value in $\mathbb{N}$.  Thus, at each point
in the sample space, only finitely many of the indicator variables
$I_i$ are non-zero.  Consequently, for each point in the sample space,
the sum contains of only finitely many non-zero terms, and so the sum
always converges.  Thus, we can apply linearity of expectation and
continue reasoning as follows.

\begin{eqnarray*}
\Ex(R_1 + R_2 + \ldots + R_Q)
        & = &   \sum_{i=1}^{\infty} \Ex\left( R_i \cdot I_i \right) \\
        & = &   \sum_{i=1}^{\infty} \left(
                \Ex\left( R_i \cdot I_i \mid I_i=1\right) \cdot \Pr(I_i=1) +
                \mbox{} \right. \\
        &   & \quad \quad \left.
                \Ex\left( R_i \cdot I_i \mid I_i=0\right) \cdot \Pr(I_i=0)
                \right) \\
        & = &   \sum_{i=1}^{\infty}
                \Ex\left( R_i \mid I_i = 1\right) \cdot \Pr(I_i=1)
\end{eqnarray*}

The second equation uses Theorem~\ref{thm:condexp}, and the third
equation follows by simplifying.  The next step is to simplify the
conditional expectation in the last expression above.  We break out
and simplify this term below and then return to the main line of the
argument.

\begin{eqnarray*}
\Ex\left( R_i \mid I_i = 1\right)
        & = &   \sum_x x \cdot \Pr(R_i = x \mid I_i = 1) \\
        & = &   \sum_x x \cdot \Pr(R_i = x \mid Q \geq i) \\
        & = &   \sum_x x \cdot \Pr(R_i = x) \\
        & = &   \Ex(R_1)
\end{eqnarray*}
since all the $R_i$ have the same distribution, so same expectation.

The first step uses the definition of expectation, the second step
uses the definition of the indicator variable $I_i$, the third step
uses the technical assumption in the theorem statement, and the final
step uses the definition of expectation again.  All summations are
over $x$ in the range of $R_i$.

Using this result, we can wrap up the proof of Wald's Theorem.

\begin{eqnarray*}
\Ex(R_1 + R_2 + \ldots + R_Q)
        & = &   \sum_{i=1}^{\infty} \Ex(R_1) \cdot \Pr(I_i=1) \\
        & = &   \Ex(R_1) \cdot
                        \sum_{i=1}^{\infty} \Pr(I_i=1) \\ \\
        & = &   \Ex(R_1) \cdot
                        \sum_{i=1}^{\infty} \Pr(Q \geq i) \\
        & = &   \Ex(R_1) \cdot \Ex(Q)
\end{eqnarray*}

The constant $\Ex(R_1)$ is pulled out in the second equation.  The third
step uses the definition of the indicator variable $I_i$, and the
final step uses an identity for the expectation of a random variable
with range $\mathbb{N}$.

\section{Building a System}

Wald's Theorem turns out to be useful in analyzing algorithms and
systems.  The following example was taught incorrectly in 6.033 for
several years.  The problem-- and erroneous solution-- originated in a
paper by Herbert Simon, who won the Nobel Prize in economics.

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.  The first step is to apply Wald's Theorem:

\begin{eqnarray*}
\Ex(T)  & = & \Ex\left(\sum_{k=1}^Q R_k\right) \\
        & = & \Ex(Q) \cdot \Ex(R) \\
\end{eqnarray*}

Here $R$ is a random variable indicating the number of steps in a try.

To verify the second step, we must check the three conditions in
Wald's Theorem.  First, the number of tries, $Q$, is always a
non-negative integer.  We will show that $\Ex(Q)$ is finite later.
Second, all tries are symmetric, so all random variables $R_k$ have
the same distribution.  Furthermore, $\Ex(|R|)$ is finite because
every try lasts at most $n$ steps.  Third, the number of steps in try
$k$ is independent of the event that $k$ or more tries are required;
that is, $R_k$ is independent of an indicator variable for the event
that $Q \geq k$.

(Note that we are using the general form of Wald's Theorem, not the
restricted form that we proved.  The number of tries $Q$ is not
bounded above by any constant $c$.)

To solve the problem, we must still find $\Ex(Q)$ and $\Ex(R_1)$.

\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{eqnarray*}
\Ex(R)  & = & \sum_{i=0}^{\infty} \Pr(R > i) \\
                & = & \sum_{i=0}^{n-1} \Pr(R > i)
\end{eqnarray*}

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*}
\quad \quad     & = & \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.57.  For $n = 100$ components, the number of steps is about 173.20.
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!


\section{An Ethernet Example}

We've now learned enough probability to look at an interesting
application of randomization in computer science.  This is the math
behind another paper you will read in 6.033.  The most common way to
build a local area network nowadays is an Ethernet: basically, a
single wire to which we can attach any number of computers.  The
communication protocol is quite simple: anyone who wants to talk to
another computer broadcasts a message on the wire, hoping the other
computer will hear it.  The problem is that if \emph{more} than one
computer broadcasts at once, a \emph{collision} occurs that garbles
all messages we are trying to send.  The transmission only works if
\emph{exactly one} machine broadcasts at one time.

Let's consider a simple example.  There are $n$ machines connected by
an Ethernet, and each wants to broadcast a message.  We can imagine
time divided into a sequence of \emph{slots}, each of which is long
enough for one message broadcast.  What we would like is for each
machine to take one of the slots and use it to broadcast their
message.  All $n$ broadcasts can finish with $n$ time slots.  There's
one big problem with this approach: how do they decide who goes first?
Note that they can't coordinate a strategy since they can't
communicate in the first place!  Each computer needs to make its own
decision about whether to broadcast or not.  Some thought suggests a
big problem: whatever algorithm is used by the various machines to
decide whether to broadcast, they will all make the same decision!
They will all broadcast, or all stay silent.  Either way, we can't get
a message through.  The problem is symmetry: from every machine's
perspective, the environment looks the same, so they all act the same.
One can prove (using invariants) that there is no \emph{deterministic}
way around this problem.

A simple way to get around this problem by breaking symmetry is
\emph{randomization}.  Suppose each computer flips an independent
coin, and decides to broadcast with probability $p$.  What is the
probability that exactly one message gets through?  This in a binomial
distribution question.  Let $A_i$ be the probability that machine $i$
transmits but no other does.  The $\Pr(A_i)=p(1-p)^{n-1}$.  The event
of a successful single transmission is the event $\cup A_i$.  Since
the events $A_i$ are disjoint, we have
\begin{align*}
\Pr(\cup A_i) &= \sum_i \Pr(A_i)\\
&= np(1-p)^{n-1}
\end{align*}
which is positive for any $0<p<1$.

Can we identify a good $p$?  Well, we want to maximize the above
expression as a function of $p$.  Differentiating the above expression
with respect to $p$ and setting to zero gives the equation
\begin{align*}
(1-p)^{n-1} - (n-1)p(1-p)^{n-2} &= 0\\
(1-p)-(n-1)p &= 0\\
p &= 1/n
\end{align*}
Plugging in this value of $p$, we find the probability  that exactly
one broadcast occurs is
\[
np(1-p)^{n-1} = (1-1/n)^{n-1} \approx 1/e
\]

In other words, a single transmission goes through with roughly $37\%$
probability.  

Of course, Ethernet can't work \emph{quite} this way because the
number $n$ of machines wanting to transmit is not hard wired into the
system.  So each computer observes the wire to try to guess $n$.  The
computer maintains some estimate $n'$ of $n$. If in a slot it observes
no traffic, it decreases (halves) its estimate $n'$.  If it observes a
collision, it increases (doubles) its estimate.  As we will see in the
last lecture, this lets each computer home in (probably) on a good
estimate, at which point the system will be able to transmit.

And of course, time isn't really divided into slots: when you take
6.033, you'll find out how machines are able to agree on when a
particular transmission slot is beginning and ending.
\end{outline}
\end{document}
% LocalWords:  CISC Rec vs Wald's Mir's np
