\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}
\begin{document}

\handout{wald}{Wald's Theorem}{November 3, 1998}

\newcommand{\comment}[1]{}
\newcommand{\Ex}{\textup{Ex}}
\newtheorem{invariant}{Invariant}
\newtheorem{thrm}{Theorem}
\newtheorem{fact}{Fact}

\section{Theorem Statement}

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.

\begin{thrm}[Wald's Theorem]
Let $Q$ be a random variable with range $\mathbb{N}$, and let \\ $R,
R_1, R_2, R_3, \ldots$ be random variables such that

\begin{eqnarray*}
\Pr(R_i = r \mid Q \geq i) & = & \Pr(R = r) \\
\end{eqnarray*}

\noindent for all $i \geq 1$ and all $r$ in the range of $R$.  Then

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

\noindent provided that the expectations on the right are finite.
\end{thrm}

Informally, the first equation requires 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$.

We can now solve the coin-and-dice problem.  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, R_3$ 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*}

\section{Linearity of Expectation for Infinite Sums}

The proof of Wald's Theorem uses a generalization of linearity of
expectation to the case of an infinite sum.  We state this
generalization without proof.

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

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

is finite, then

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

\section{Proof of the 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 = 1$ 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
first step of the proof is to take expectations on both sides of this
equation.

\begin{eqnarray}
\Ex(R_1 + R_2 + \ldots + R_Q)
	& = &	\Ex\left( \sum_{i=1}^{\infty} R_i \cdot I_i \right) \\
	& = &	\sum_{i=1}^{\infty} \Ex\left( R_i \cdot I_i \right) \\
	& = &	\sum_{i=1}^{\infty} 
		\sum_x x \cdot \Pr(R_i \cdot I_i = x) \\
	& = &	\sum_{i=1}^{\infty} 
		\sum_x x \cdot \Pr(R_i = x \cap I_i = 1) \\
	& = &	\sum_{i=1}^{\infty} 
		\sum_x x \cdot \Pr(R = x) \cdot \Pr(I_i = 1) \\
	& = &	\sum_{i=1}^{\infty} \Pr(I_i = 1) \cdot
		\sum_x x \cdot \Pr(R = x) \\
	& = &	\sum_{i=1}^{\infty} 
		\Ex(R) \cdot \Pr(I_i = 1) \\
	& = &	\Ex(R) \cdot
			\sum_{i=1}^{\infty} \Pr(Q \geq i) \\
	& = &	\Ex(R) \cdot \Ex(Q)
\end{eqnarray}

Step 2 follows from Fact~\ref{fact:linexp}.  Step 3 uses the
definition of expected value.  The inner summation is over $x$ in the
range of $R_i \cdot I_i$, which is the range of $R$ unioned with $\{ 0
\}$.  Step 4 uses a fact about multiplication.  (This step is valid
for the $x = 0$ term of the summation, since this term is zero both
before and after the step.)  Step 5 follows from the condition in the
theorem that $\Pr(R_i = x \mid I_i = 1) = \Pr(R = x)$.  In step 6, we
pull the constant $\Pr(I_i = 1)$ out of the inner summation.  Step 7
uses the definition of expected value, and step 8 uses the definition
of the indicator variables $I_i$.  Finally, step 9 uses an identity
for the expectation of a random variable with range $\mathbb{N}$.
\end{document}
