Sue and Bob are playing a game in which Sue starts with A chips, Bob starts with B chips, and they play...

probability/chip.game New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Sue and Bob are playing a game in which Sue starts with A chips, Bob
starts with B chips, and they play rounds in which Sue has a
probability p of winning a chip from Bob, and Bob has a probability 1-p
of winning a chip from Sue.  They play until one of them runs out of
chips.  To make it more interesting, Sue will start by picking a
probability p, 0<p<0.5.  Then, to make up for the fact that the rounds
are biased against Sue, Bob will have to pick B first, and then Sue will
get to pick A.  (A and B of course must be positive integers.)  If they
each play intelligently, who wins, and with what probability does he or
she win?

-- Brian Ewald <bewald@indiana.edu>, posted by Jonathan Haas

Show solution

Clearly, one of them wins with probability arbitrarily close to 1.  It
isn't immediately obvious who.

Let us consider a section of the game.  At the start, Bob has B chips,
Sue has A.  Define the section to end when one of them has won C
chips.  For C=1, Bob wins with probability (1-p), Sue with probability
p.  For C=2, Bob wins with probability (1-p)^2/((p^2)+(1-p)^2).  If we
iterate (taking C to be successive powers of 2), the probability of
Bob winning gets arbitrarily close to 1.  However, the largest section
possible is limited by B.

At this point, we can see that the game is equivalent to one in which
Bob picks an arbitrary probability p>0, and B=1.  (OK, there's a
little handwaving there.  This is rec.puzzles, not homework.)  Using
random-walk principles, we find that the probability that the walk
diverges without returning to 0, as a function of p, approaches 1 as p
approaches 0.  (Define the function f(n) as the probability that the
walk never returns to 0, given that it starts from n.
f(n) = pf(n-1) + (1-p)f(n+1); f(0) = 0.)  Thus, no matter how large a
number Sue picks, Bob probably wins.  By picking a large starting
number, Bob can make his chances of winning arbitrarily close to 1.

-- Seth Breidbart <sethb@panix.com>

Let's take a specific example. Sue chooses p=0.49, and Bob chooses B=99.
Then the probability that Sue wins is less than 2%, no matter how large a
value she chooses for A.

In general, for any p with p<0.5, and for any A and B, the probability
that Sue wins is always less than (p/(1-p))^B. Since Bob knows p before
he has to pick B, he can give himself a probability of winning that is as
close as he likes to 1 by choosing a large enough value for B.

It helps to do some mathematics before you answer a mathematical problem.

-- Barry Wolk <wolk@ccm.umanitoba.ca>