\documentclass[12pt]{6042}
\usepackage{psfig}

\begin{document}

\handout{sum-expectation}{The Expectation of a Sum}{May 5, 1998, 11pm}

We stated in Lecture 22 (4/30/98) that the expectation of the sum two random
variables is the sum of their expectations.  From this it's easy to prove
by induction that the expectation of the sum of any \emph{finite} number
of random variables is the sum of their expectations.  However, there are
a number of applications where it's useful to know that this result
actually generalizes to any \emph{countable} number of random variables.

\section{Countable Sum of Expectations}
\begin{theorem}
Let $\mathbf{V} ::= (V_0,V_1,\dots)$ be a countable sequence of random
variables on the same sample space such that
\[\pr{\sum_{i=0}^{\infty}\abs{V_i} \mbox{ converges}} = 1.\]
Let $V$ be the random variable such that
\[V = \sum_{i=0}^{\infty}V_i\]
on sample points where the sum converges, and $V=0$ otherwise.
Then
\[\expect{V} = \sum_{i=0}^{\infty}\expect{V_i}.\]
\end{theorem}

\begin{proof}
Let $r$ be a variable ranging over the values of $V$.  Then by definition
\begin{eqnarray}\label{EVdef}
\expect{V} & = & \sum_r r\pr{V=r}.
\end{eqnarray}
Notice that this is a countable sum, since there are at most as
many values of $r$ as points in the sample space.

Let $\mathbf{r}$ be a variable ranging over the infinite sequences of
values of $V_0,V_1,\dots$ at all sample points at which $V\neq 0$.  Let
$i$ range over $\nats$, and let $r_i$ be the $i$th element of
$\mathbf{r}$.  So $\sum_i r_i$ is absolutely convergent by hypothesis.

We write $\mathbf{V}=\mathbf{r}$ for the event that $V_i = r_i$ for all
$i$.  So
\begin{eqnarray}\label{prVr}
\pr{V=r} & = & \sum_{\substack{\mathbf{r},\\ \sum_i r_i= r}} \pr{\mathbf{V}=
\mathbf{r}}.
\end{eqnarray}
The sum above is also countable, since there are again at most as
many values of $\mathbf{r}$ as points in the sample space.

Combining~(\ref{EVdef}) and~(\ref{prVr}), we have
\begin{eqnarray}\label{EVsumr}
\expect{V} & = & \sum_{\mathbf{r}} \Bigl[\Bigl(\sum_i r_i \Bigr)
\pr{\mathbf{V}= \mathbf{r}}\Bigr].
\end{eqnarray}

Let $s$ range over the values of all of the random variables $V_i$.  Since
each $V_i$ has only a countable number of values, the range of $s$ is
also countable.

Now, we can rearrange terms in absolutely convergent sums:
\begin{align*}
\sum_\mathbf{r} \Bigl[\Bigl(\sum_i r_i \Bigr)
                \pr{\mathbf{V}= \mathbf{r}}\Bigr]\\
    &= \sum_\mathbf{r} \Bigl[\sum_i r_i \pr{\mathbf{V}=
                \mathbf{r}}\Bigr]\\
    &= \sum_i \sum_\mathbf{r} r_i \pr{\mathbf{V}= \mathbf{r}}\\
    &= \sum_i \sum_s \sum_{\substack{\mathbf{r},\\ r_i = s}}
                        s \pr{\mathbf{V} = \mathbf{r}}\\
    &= \sum_i \sum_s \Bigl[s \sum_{\substack{\mathbf{r},\\ r_i = s}}
                         \pr{\mathbf{V} = \mathbf{r}}\Bigr]\\
    &= \sum_i \sum_s s \pr{V_i = s} \\
    &= \sum_i \expect{V_i}
\end{align*}

\end{proof}

\section{Gambler's Ruin: The Fair Case}
An elegant application of a countable sum of expectations arises from the
``Gambler's Ruin'' problem.

A gambler starts with an initial stake of $n$ dollars.  He repeatedly
flips a coin, betting one dollar on heads each time.  We assume the
results of different flips are independent and that the coin is fair: the
probability of heads is $1/2$.  When heads comes up, the gambler wins one
dollar; when tails comes up, he loses one dollar.  The game ends when
either the gambler {\em loses} by going broke, or {\em wins} by reaching a
goal amount of $T\geq n$ dollars.  We are interested in the probability, $w$,
that the gambler wins.  This is called the Gambler's Ruin problem.

Of course, we are also interested in the probabilities of the other two
possibilities: that the gambler loses, or that the gambler keeps flipping
forever without either winning or losing.  We will show later that the
probability of playing forever is zero.  This means that the probability
that the gambler loses is $1-\pr{\mbox{gambler wins}} = 1 - w$.

We can visualize the Gambler's Ruin problem as a random walk illustrated
in Figure~\ref{fig:walk1}.  At each step, if the gambler wins, the path
goes up by 1---this happens with probability $1/2$; otherwise it goes down
by 1---also with probability $1/2$.  If the path touches either the top
barrier at $T$, or the bottom barrier at 0, the game ends.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/walk1.eps,height=2.5in}}
\caption{This is a graph of the gambler's capital versus time for
one possible sequence of bet outcomes.  At each time step, the graph
goes up with probability $1/2$ and down with probability $1/2$.  The
gambler starts with $n$ and continues betting until the graph reaches
either 0 or $T$.}
\label{fig:walk1}
\end{figure}

We can solve for $w$ by considering the random variable $G$ equal to the
gambler's dollar gain.  The gain is unspecified in the case that the game
goes on forever, but since this happens with probability zero, it doesn't
matter how $G$ behaves in this case; say it equals 0.

Now $G= T-n$ when the gambler wins the game, and $G= -n$ if the gambler
loses (goes broke).  Therefore,
\[\begin{array}{rl}
\expect{G} &= \pr{\mbox{Gambler wins}}(T-n) - \pr{\mbox{Gambler loses}}n\\
        &= w(T-n) - (1 - w)n\\
        &= wT - n,
\end{array}
\]
and so
\begin{eqnarray}\label{wEG}
w & = & \frac{\expect{G}+n}{T}.
\end{eqnarray}
How to find $\expect{G}$?  Here's the trick: let $G_{i}$ be the amount the
gambler gains on the $i$th flip: $G_{i}=1$ if the gambler wins the flip,
$G_{i}=-1$ if the gambler loses the flip, and $G_{i}=0$ if the game has
ended before the $i$th flip.  Since the coin is fair, $\expect{G_i}=0$.
Now
\[G=\sum_i G_i,\]
except for the probability zero event that the game runs forever.
Moreover, $\sum_i \abs{G_i}$ converges with probability one because
$G_{i}=0$ whenever $i$ exceeds the length of the game.  So the conditions
for our Theorem on a countable of sum expectations are satisfied, and
\[
\expect{G} = \sum_{i=1}^{\infty}\expect{G_{i}} = \sum_{i=1}^{\infty}0 = 0.
\]
So we conclude from~(\ref{wEG}),
\[
\pr{\mbox{Gambler wins}} = w = \frac{n}{T}.
\]

\begin{xample}
Suppose we have \$100 and we start flipping a fair coin, betting \$1 with
the aim of winning \$100.  Then the probability of reaching the \$200 goal
is $100/200=1/2$---the same as the probability of going bankrupt.  In
general, if $T=2n$, then the probability of doubling your money or losing
all your money is the same.  This is about what we would expect.
\end{xample}

\begin{xample}\label{win100}
Suppose we have \$500 and we start flipping a fair coin, betting \$1 with
the aim of winning \$100.  So $n=500, T=600$, and $\pr{\mbox{win}} =
500/600 = 5/6$.
\end{xample}

\begin{xample}
Suppose Albert starts with \$100, and Luca starts with \$10.  They flip a
fair coin, and every time a head appears, Albert wins \$1 from Luca, and
vice versa for tails.  They play this game until one person goes bankrupt.
What is the probability of Albert winning?

This problem is identical to the Gambler's Ruin problem with $n=100$ and
$T=100+10=110$.  The probability of Albert winning is $100/110 = 10/11$,
namely, the ratio of his wealth to the combined wealth.  Luca's chances of
winning are $1/11$.

Although Albert will win most of the time, the game still has
expected value {\em zero} for him.  When Albert wins, he wins only \$10.
When he loses, he loses big---\$100.
\end{xample}

Another intuitive idea is confirmed by this analysis: the larger the
gambler's initial stake, the larger the probability that he will win a
fixed amount.

\begin{xample}
If the gambler started with one million dollars instead of 500, but aimed
to win the same 100 dollars as in the Example~\ref{win100}, the
probability of winning would increase to $1M/(1M + 100) > .9999$.
\end{xample}

We'll see in a later lecture that Gambler's Ruin behavior is very
different when the coin is even slightly unfair.

We still have to show that $\pr{\mbox{gambler plays forever}}=0$.

\textbf{Exercise:} Let $N_k$ be the event that the game lasts for at least
$k$ coin tosses.

(a) Argue that
\[\pr{\mbox{gambler plays forever}} \leq N_{k+t}
   \leq N_k \left(1 - \left(1/2\right)^t\right).\]

(b) Conclude that $\pr{\mbox{gambler plays forever}} = 0$.
\end{document}
