Probability question

[The Jester]

Two players play a game in which player one begins with A cents and player two begins with B cents. Each round of the game, a fair coin is flipped and player one takes one cent from player two if the result of the flip is heads, otherwise player two takes one cent from player one. The game continues with the coin repeatedly flipped until one player has no money left. From experimentation, it seems very clear that the expected value for the length of the game should be A x B, however I would like to know how I can go about showing this analytically.

[Samuel]

If player a has x tokens and player b has 1 token, the expected length of the game (where half of the time the game ends) will be one round.

A times B doesn't work for that.

[Kuroneko]

Your intuition is spot on. Suppose that for each turn, the first player has probability p of winning, and one units is exchanged each turn to the winner. For starting amounts A and B, the total pot is C = A+B; thinking of it as a random walk with fixed pot size but varying first player's amount, the running time T = T(A) has boundary conditions T(0) = T(C) = 0. The probability that the game goes on for k turns can be conditioned on the result of the first turn: with probability p, player one wins and increases his amount by one, and with probability 1-p, player one loses and decreases his amount, but either way, the game experiences one more turn. Hence:
[1] T(A) = pT(A+1) + (1-p)T(A-1) + 1
In the particular case p = 1/2, this is an easy recurrence relation having a solution T(A) = (t+1)A - A², t = T(1). The condition T(c) = 0 gives t = C-1, so that
[2] T(A) = AC - A² = AB
The general solution is looks to be rather intense, but behavior for the second player having infinitely large pockets (a good approximation for a casino relative to the average gambler) is not too difficult to determine: the expected number of turns is A/(1-2p) if p<1/2 and infinity if p≥1/2.

[Kuroneko]

Come to think of it, the general case is not too complicated either. The recurrence relation is
[1] T(A) = pT(A+1) + (1-p)T(A-1) + 1.
As the inhomogeneous part (just the +1) is a constant, we should look for a linear particular solution, and one does present itself: T(A) = A/(1-2p). Since the corresponding homogeneous recurrence (everything but the +1) has the characteristic equation x = px² + (1-p), which has roots 1 and r = 1/p-1, the general solution must be of the form
[2] T(A) = A/(1-2p) + a 1^A + b r^A
for some constants a and b. Imposing T(0) = 0 and T(C) = 0 gives
[3] (1-2p)T(A) = A - C[ r^A - 1 ]/[ r^C - 1 ].
This is not defined for p = 1/2, but the limit of T(A) as p→1/2 is still AC - A² = AB, consistent with the previous result.