        \problemdata       % Takes 5 *mandatory* arguments
        {ben-coin}             % latex-friendly label for the prob.
        {expectation}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 cp11f-3} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).



\begin{problem}
Ben Bitdiddle is asked to analyze a game in which a fair coin is
tossed until the first time a head turns up.  If this head occurs on
the $n$th toss, and $n$ is odd, then he wins $\$2^n/n$, but if $n$ is
even, he loses $\$2^n/n$.  Ben observes that the expected dollar win
from this game is the value of the series:
\begin{eqnarray*}
& (1/2) \cdot 2 - (1/4) \cdot 2 + (1/8) \cdot 8/3 + \cdots \pm (1/2^n)
\cdot 2^n/n \cdots\\
& = 1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n \cdots
\end{eqnarray*}

This is the \emph{alternating harmonic series}---a series which is
known to converge to a definite real number $r>0$.  Ben concludes that
since $r >0$, it's to his advantage to play this game.  As usual,
Ben's shoot-from-the-hip analysis is off the mark.  Explain. (Hint:
show that by reordering the series you can make it converge to
different values)

\solution{
The definition of expectation of $R$ is a summation, where we sum
$r\cdot\prob{R=r}$ for all values that R can take. However the definition
itself does not specify an ordering on how we do that sum the terms,
therefore it is \emph{not} valid for series where reordering the terms may
change the value (also see
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln11.pdf}
{Course Notes 11}).

In this case $\expect{\textrm{win}} = 1 -1/2 + 1/3 -1/4...$

This series converges, which means that if you add up the terms in the
\emph{given order} you will get some positive value $r$ that is not
infinite.  However it is not absolutely convergent as described below.
If I rearrange the terms then I can make it sum to a different value,
in fact \emph{any} value, even negative, This problem arises because
the positive terms sum to inifinity and the negative terms also sum to
infinity, so one can easily remove a little from infinity here or
there and make this sum acquire any value, depending on how the
expectation is evaluated.

As a result $\expect{\textrm{win}}$ is not well-defined.  The
definition of expectation requires absolute convergence.

%This series is convergent, but not \emph{absolutely}
%convergent. The definition of expectation requires absolute
%convergence, so the expectation in this case is not defined.  The fact
%that the expectation is undefined is no mere formality.  The number
%$r$ is not relevant to the behavior of the game. In fact by reordering
%its terms, the series can be made to converge to any real value or
%diverge to $\pm\infty$.

\paragraph{Parenthesis on convergence vs.~absolute convergence:}
Consider the series
 \[
 S \eqdef \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots
 \]
 By regrouping the terms we can deduce:
 \begin{eqnarray*}
 S & = & [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0,\\
 S & = & 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.
 \end{eqnarray*}

To see the problem here, let $S_n \eqdef \sum_{i=0}^{n}(-1)^i$.  Then
$S_n = 1$ for odd $n$ and $S_n = 0$ for even $n$.  Hence $S_n$ does
not have a well-defined limit as $n$ tends to infinity, implying that
$S$ is not a convergent series.

Even for convergent, but not absolutely convergent, series, rearranging
terms can cause big changes.  For example, the series above
 \[
 1 - 1/2 + 1/3 - 1/4 \dots
 \]
 converges, but is not absolutely convergent.  We can reorder terms in
 the series so that the resulting series converges to 3.  \dots so it
 converges to 4.  \dots so it doesn't converge.

Note that the sum of the negative terms goes to negative infinity, because
 the sum
 \[
 -1/2 - 1/4 - 1/6 -  \dots - 1/2n = -H_n/2 \sim (-\ln n)/ 2
 \]
 and $\ln n$ goes to infinity with $n$.  Similarly, the sum of the positive
 terms goes to positive infinity.

 To reorder the terms to converge to 3, begin by taking the positive terms
 in decreasing order until their sum first exceeds 3.  Next, take the
 negative terms in order of decreasing magnitude until the sum of all the
 terms taken---positive and negative---first goes below 3.  Now take the
 remaining positive terms in decreasing order until the sum again exceeds 3,
 then the negative terms till the sum goes below 3, and so on.  It is always
 possible to move the sum above or below 3 by taking enough of the remaining
 positive or negative terms, because the remaining positive terms sum to
 positive infinity and the remaining negative terms sum to negative
 infinity.  Also, the running sum of the positive and negative terms taken
 in this way goes above and below 3 at most by the magnitude of the last
 term taken.  Since the magnitude of the terms goes to zero, this implies
 that the sum goes above and below 3 by an amount that decreases to zero.
 But this is exactly what it means to say the sum converges to 3.

 Replacing ``3'' by ``4'' above yields an ordering in which the sum
 converges to 4.

 Finally, alternately taking enough positive terms to increase the sum by 1
 and then taking one negative term, yields an ordering in which the sum
 diverges to positive infinity.

 This argument applies to any convergent series that is not
 absolutely convergent to show that it can be reordered to converge to
 \emph{any} desired number, or to diverge.  The moral: when reordering terms
 in a series, be sure to check for absolute convergence.

 }
\end{problem}
