Tom has 2 quarters and Jerry 3; they flip fairly, loser paying winner a quarter, until one is broke.

The probability of winning is 0.4 and the expected number of flips is
6.

In the general case with m and n quarters the probability of winning
is m/(m+n) and the expected number of flips is m*n.

Proof:

Let p(m,n) be the probability of player 1 to win if he has m quarters
and player 2 has n quarters.  Then p(m,n) = 0.5 * p(m-1,n+1) + 0.5 *
p(m+1,n-1).  It is easy to see that p(m,n) = m/(m+n) always satisfies
this equation.

Let E(m,n) be the expected number of flips if player 1 has m quarters
and player 2 has n quarters.  Then E(m,n)-1 = 0.5 * E(m-1,n+1) + 0.5 *
E(m+1,n-1).  As (m-1)*(n+1)+(m+1)*(n-1) = 2*(m*n-1), one can see that
here E(m,n) = m*n always satisfies the above equation.

-- Ilan Mayer <ilan@isgtec.com>

Let (i,j) mean that Tom has i quarters and Jerry has j quarters.
There are 6 possible states which I'll label with 0,1,2,3,4,5

(5,0) ---- (4,1) ---- (3,2) ---- (2,3) ---- (1,4) ---- (0,5)
  0          1          2          3          4          5

State 0 means that Tom wins while State 5 means that Jerry wins.  If
you are in one of the intermediate states, then you move to either
neighboring state with probability 1/2.  The game starts at state 3.

(1) What is the probability that the game ends in state 0?

Let P(n) be the probability that the game ends in state 0 given that
we are in state n.  Obviously, P(0) = 1 and P(5) = 0.  If we are in
state N (not equal to 0 or 5), we move to state N-1 with probability
1/2 and to state N+1 with probability 1/2.  Thus 2*P(N) = P(N-1) +
P(N+1).  Substituting 1,2,3,4 for N we get 4 equations in 4 unknowns
whose solutions are P(1)=.8 P(2)=.6 P(3)=.4 P(4)=.2 Since we start in
state 3, Tom wins with probability .4

(2) What is the expected number of flips before the game ends?

Let E(n) be the expected number of flips before the game ends given
that you are in state n.  Obviously, E(0) = E(5) = 0.  Again if we are
in state N (not equal to 0 or 5), we move to state N-1 with probability
1/2 and to state N+1 with probability 1/2.  Since each move takes 1
flip, 2*E(N) = E(N-1) + E(N+1) + 2.  Substituting 1,2,3,4 for N gives
us 4 equations in 4 unknowns whose solution is E(1)=E(4)=4,
E(2)=E(3)=6.  We start in state 3 so the expected number of flips is
6.

Generalization: Tom start with t quarters and Jerry starts with j
quarters.  There are now t+j+1 states (t+j,0) (t+j-1,1) (t+j-2,2) ...
(0,t+j)

(1) The equation 2*P(N) = P(N-1) + P(N+1) along with P(0)=1 and
P(t+j)=0 imply that the probabilities increase linearly from state 0
through state t+j.  Thus, P(N) = N/(t+j).  Thus, Tom wins with
probability t/(t+j) and Jerry wins with probability j/(t+j)

[ Editor: with P(0)=1 and P(t+j)=0 the probabilities decrease:
  P(N) = 1 - N/(t+j), as in P(1)=.8 ... P(4)=.2 above.  The game starts
  in state j, so P(j) = t/(t+j), as stated. ]

(2) 2*E(N) = E(N-1) + E(N+1) + 2 and E(0)=E(t+j) imply that E(N) =
N*(t+j) - N^2 for N <= (t+j+1)/2.  (proof left as an exercise for the
reader)  The expected values are symmetric about the middle.  Thus, the
expected number of flips is d*(t+j-d) (where d = min{t,j}) = t*j.

-- Glenn C. Rhoads <rhoads@paul.rutgers.edu>