In this coin game between A and B, who is favored?

The answer is that neither A nor B is favored.  The expected value of
the game to each is exactly zero.  The simple explanation of this is
that A starts with zero dollars lost or won, and flips the coin some
number of times, each flip having zero expected value for A.

I was not completely satisfied with the above solution.  I still
believe it needs to be somewhat better justified.  The following
articles posted to rec.puzzles give such a justification (I think) as
well as hinting at why it might be needed.

-- David Karr <karr@cs.cornell.edu>

----

Time to round off what's been said.  Please excuse my rough and pompous
manner, it just comes naturally to me.   :-(

There has been a lot of nonsense talked, especially regarding the
problem being imperfectly defined (due to unbounded resources).  This
is never thought to be a difficulty in such problem, and rightly so; it
is irrelevant.  Provided, of course, that the game *does* finish with
probability one, as here; (and if not, there are more problems than
unbounded resources!)  In fact, this is one of the most well-defined
problems in this field one is likely to see.

There were some brave attempts to calculate all the individual
outcomes, which were interesting, but all came to nothing.  I haven't
done this either.

So first off - thanks a bunch to Robert Andrew Ho, for posting this
problem in the first place; it's a little beauty !  Thanks too, for
posting the simple, clearcut resolution: the game is FAIR, because A
has expected gain exactly zero, because each of his plays has expected
gain zero.  I absolutely *KICKED* myself for not seeing this on my own;
it's the sort of answer we all love to see when possible, slick but
simple.

Now; first question - is this proof rigorous?  And if not, what needs
to be done to make it so.  Especially in view of David Karr's ingenious
counterexample, whereby they just exchange dollars with probability
half either way, until B has $100.  This clearly is in B's favor, and
finishes with probability one.

The problem with Dave's example, which highlights the point of
non-rigor in the original argument, is that even though the game is
certain to finish, it has INFINITE expected length, being essentially a
random walk with an absorbing barrier and zero drift, (more below).

In the original problem, we have a random walk (state = size of pot,
timestep = two bets), with an absorbing barrier (zero), and NEGATIVE
drift; it thus has finite expected time to finish, (more below).

So, to make the original argument fully rigorous, we note that the
overall profit to A, is
     W = W1 + W2 + W3 + ... + WN ,
where Wi = profit to A on bet i.

Now use that marvellous simplifying rule for expected values, the
exp-value of a sum equals the sum of the exp-values, (ALWAYS! -
independence not required, though we have it here).

If N were fixed in the above equation, that would be it; as E[Wi] = 0
for all i.

But alas, N also is a random variable, with a proper probability
distribution, (provided the probability of finishing is one).

Fortunately this has little effect on the result, changing it slightly
to

       E[W] = E[Wi] x E[N] , provided of course that all E[Wi] are
       equal.

Now we see the crucial point.  In the original example, E[N] was
finite, and E[Wi] = 0, so E[W] = 0, as stated.  YAY !!!!!!

Whereas in Dave's counterexample, E[N] is infinite, and E[Wi] = 0
still, so E[W] is undefined from this equation, (though it is in fact
equal to -100).

This completes the main issue.

There is a subsidiary question - do you also need to PROVE, that
zero-drift gives infinite expected finishing time, and negative drift
(from positive values toward a boundary at zero) gives finite expected
finishing time.

One could take this for granted, as being a standard result in Markov
chain theory; but if you don't like that, here is an almost rigorous
proof from first principles.

The "drift" of a random walk is the expected distance travelled in one
timestep.

In David's example it is  (-1)(.5) + (1)(.5) = 0 .

In the original, with a two-bet timestep, it is

  (-2)(.25) + (-1)(.25) + (0)(.25) + (1)(.25) = -(.5)  .

In general, if the distance to the barrier is  D, and the drift is -m,
then E[T] = D/m; where T = time to completion.  This is merely time =
distance/speed, in effect, and comes from

D = T x Xi   (loosely speaking; the Xi are i.i.d. variables: the
step-lengths),

whence   D = E[T] x E[Xi] = E[T] * m.

There is a little bit of tidying to do; it is only exact when there is
no "overshoot"; i.e. only single steps toward zero are possible.  If
there are double steps possible, as in the original, the formula is
almost exact; it tends to exact in the limit as D increases.

So in the original problem, if there were an original ante of $N by B,
the game would still be fair, and take about 2N timesteps on average,
i.e. 4N bets.

If the drift is zero, essentially the same argument shows the expected
finishing time is infinite; (you need to throw in some epsilontics to
make it thorough).

-- Bill Taylor <wft@math.canterbury.ac.nz>

----

The variations on Robert Ho's gambling problem.

David Karr asks...

>we could simply assume that both A and B
>start out with some large but bounded multiple of the initial bet, say
>they each have N dollars to start and then B antes up 1 dollar.  Now
>we must add a rule for what happens when A loses a roll but has no
>more money to put in the pot.  Consider the following possibilities:
>
>(a) A does nothing (the pot is unchanged and the game continues)
>
>(b) The game ends immediately, and B collects the entire pot.
>
>(c) The game ends immediately, and the players split the pot evenly
>    (assume a dollar may be changed into two half-dollars if necessary).
>
>For each of these possible rules, who is favored and by how much?

Well clearly they all favor A, even the apparently B-favoring (b) !

This is because, as in my earlier post, all the bets have zero expected
gain to A, except for (at least one) at A's bankruptcy-point, which has
positive value for A, (as he may gain $1 but risk nothing; it is
irrelevant what is done with the pot, at least as far as the individual
bets' expected values go).

Clearly by a simple dominance argument, (b) is the worst for A (even
though it is still in his favor); and as between (a) and (c), some
further thought shows that (c) is better than (a); I'll leave you to
work out the reason, basically a bird in the hand is better than two in
the bush.  (Near-exact values could perhaps be worked out by the
methods used below).

David Blume says...

>I think the following is interesting.  What if they rolled a 6-sided
>die, and a "win" occurs if you role a 1 or a 2. (ie., 1/3 of the
>time.)  Then, what if a "win" was defined by rolling 3 through 6. (2/3
>of the time)
>
>Obviously, one favors player A, and the other favors player B.  But
>*notice* by how much!  The two are not in proportion at all!  Not even
>close!  Wow!

This is a very interesting variation.

In general, let A LOSE each bet with PROBABILITY  p, (collecting for a
win, paying for a loss); and B have the same probability, (collecting
for a win, no change for a loss).

We will need  p<= 2/3, as we will see.     Let B make an initial ante
of $N.

It is easiest to think in these terms.  There are N separate dollar
notes, labelled 1,2,3,...,N, waiting to be won, in order.  While they
are being won, A pays in occasional extra dollars, labelled
(N+1),(N+2),...to be subsequently won; then some more while this second
lot are being won; etc.

Roughly, each player has equal chances, in the limit, of winning each
dollar note.  (This is not quite so for note 1, which is 3/4 to A, or
note 2 which is 3/8 to A, in the case p=1/3; it's not hard to calculate
these recursively, but we only need that they approach 1/2
geometrically fast; for a rough answer).

While each individual dollar note is being fought over, there is an
expected amount of extra money A has to pay in.
Call this "e" when A starts the betting, and "f" when B starts.

Simple probability shows        e = (1-p)(0) + p(1+f)
                                f = (1-p)(0) + p e
giving e =   p/(1-p^2)
and    f = p^2/(1-p^2) ;  and, as (approximately, after a little
while), either is equally likely to start the battle on each note,

we get    E[amount A puts in, per note] = (e+f)/2 = p/(2-2p)  .

So then; while the first N notes are being fought over, (and going
about N/2 to each player), A is putting in an extra  Np/(2-2p).

And while these are being fought over, A puts in an extra
N(p/(2-2p))^2; then an extra  N(p/(2-2p))^3, and so on.

So the total amount A puts in, is, on average, the sum of this
geometric series

N(a + a^2 + a^3 +...) = Na/(1-a),  where a = p/(2-2p);  so over all, on
average

A puts in  Np/(2-3p);  and this is to be compared with the N that B
puts in.
(And as explained, of all the money put in, they take out approx half
each.)

Some concrete cases:

The original problem: p=1/2,  A puts in  N, the game is fair; as we
                      know.

Blume case 2:         p=1/3,  A puts in N/3, they each take out 2N/3.
                      So A gets about N/3 in profit.  That is, A
                      collects, net, 1/3 of the ante; NOT 1/2, as David
                      Blume said his simulations showed.  Could you try
                      again, David?

1/2 < p < 2/3:        A pays in more than B; the game favors B, and the
                      bigger the ante B puts up, THE MORE HE WINS !

Blume case 1:         p=2/3,  disastrous for A - he has an infinite
                      expected amount to pay; though only a finite
                      amount any time the game is actually played.  He
                      doesn't quite need infinite resources; but he's
                      on a giant bummer, (and its still worse the
                      bigger the ante).

p > 2/3.              Catastrophe !  2/3 is the critical case for the
                      above calculations.  Beyond this, the drift is
                      POSITIVE, there is a positive chance the game
                      will never end, and this chance is larger as the
                      ante N gets larger.  So quite likely, B will keep
                      on winning more and more, while A keeps on
                      paying more than he wins, on average; on and on,
                      world without end, amen.

A will not only need infinite resources; but also infinite time and
infinite stupidity !

-- Bill Taylor <wft@math.canterbury.ac.nz>

----

In article <1993May31.153845.17494@nntp.nta.no> stein@hal.nta.no (Stein
Kulseth) writes:
>Just back from a 2-week holiday I find this neat little problem, along
>with a long discussion. Yet I cannot see that anyone has managed to
>find this very simple line of reasoning:
>
>'A' puts one dollar in on  odd rolls, takes one dollar out on even
>rolls.  That means his expected loss/win is zero, thus 'B's expected
>loss/win is zero too, the game is fair.

According to one of the articles, this reasoning was put forward a
couple of centuries ago, give or take.

>In fact, B may follow any strategy he likes, providing he always leaves
>at least one coin in the pot when A is to roll, and does not demand
>money from A other than what A has put in the pot. The game is still
>fair.

I think Bill Taylor made a very important point about the expected
length of the game being finite.  Perhaps even more to the point, the
expected total of all A's wagers is finite.  Consider the following
game:

B puts a dollar in the pot.  A rolls until the pot is empty, wagering 1
dollar on the first roll at even odds, 2 dollars on the second roll at
even odds, and so forth, doubling the wager each time.  If A has
unbounded resources then this game has finite expected length (I think
the expected number of rolls is 2, but I haven't checked carefully) but
the expected total of the wagers is infinite (it's a variation of the
St. Petersburg paradox) and A will win 1 dollar with probability 1, and
I haven't yet been dissuaded from the belief that this means the value
of the game to A is 1 and to B is -1.

The thing about the original puzzle of this thread is that only a
finite amount of money is expected to be involved in the game, hence it
is (at least intuitively) possible to evaluate the expected value by
pairing off events in a convenient fashion.  This reminds me very much
of the absolute convergence of infinite series.

To make this kind of problem correspond to an infinite series, consider
each possible step taken by A (winning or losing some number of dollars
on some roll of the die).  Multiply the amount won (a negative number
for a loss) by the probability at the start of the game that such an
event will actually occur.  Then arrange these products in any order
you like to form an infinite series.  If the series is absolutely
convergent, then the order you chose didn't matter, and I believe the
sum of the series is the expected value of the game.

Note that in the game I described above, the resulting series is *not*
absolutely convergent, in fact if you take the terms for A winning and
losing, respectively, on rolls 1, 2, 3, ..., then you get the series

  1/2 - 1/2 + 1/2 - 1/2 + 1/2 - 1/2 +/- ...

Likewise, I suspect (but have not proved) that if the bet is always $1
but A has infinite resources and B never takes money from the pot as
long as A can still play (i.e. he never does), that the resulting
series likewise is not absolutely convergent.  (It was remarked that
the expected length of the game is infinite as a simple result of
random walk theory; maybe this yields an easy proof of my conjecture.)

I suspect (but again have not proved) that the series of products for
the game where B takes a dollar from the pot with probability 1/2 every
turn *is* absolutely convergent, in which case we simply pair off the
possible win/loss pairs for A such that we get a series

  r1 - r1 + r2 - r2 + r3 - r3 +/- ...

which must sum to 0, as Stein Kulseth asserts, due to absolute
convergence.

-- David Karr <karr@cs.cornell.edu>

[ Editor: for the related St. Petersburg paradox see
decision/stpetersburg. ]