Leo asks:
Absolutely Regular: A neat problem: Communicated to me by co-blogger Steve Miller, which he's too busy to post. Two players, A and B, start out with $a and $b dollars, respectively -- where a and b are natural numbers. They flip a fair coin, and every time it comes up heads, A gives 1 dollar to B; for every tails, B gives 1 dollar to A. The game ends when one of the players has zero dollars (and the other one has a+b). What's the probability that player A wins?
I was able to guess the answer right away (Steve told this to me on the phone), but this is probably more luck than anything else, as these intuitions can often be misleading. In any case, an answer is worthless without a proof, which Steve tells me is not entirely trivial. Furthermore, we don't know what happens if the coin, instead of being fair, has bias p. Anyone out there know?
At the start, player A has $a dollars. Subsequent coin flips do not change the expected value of A's wealth, so A's expected wealth is $a at every point in the future. When the game ends, A has either 0 or $a+b dollars. For her expected wealth to be $a, the probability that she wins--has $a+b dollars--must be equal to a/(a+b).
In order to solve the problem with an unfair coin with p ≠ 1/2, construct the value function. Suppose that player A wanted to sell you her position in the game when she has $x dollars. What would be a fair price for you to pay?
Clearly, if A has $a+b dollars, she has won and the game is over and her position is worth $a+b, so V(a+b) = a+b. And if A has $0 dollars, she has lost and the game is over and her position is is worth $0, so V(0) = 0.
If A has $x dollars this round, then after the next coin flip A will have $x+1 dollars with probability p and $x-1 dollars with probability 1-p. If the value function is to be fair, then:
V(x) = p(V(x+1)) + (1-p)(V(x-1))
or:
[V(x) - V(x-1)] = [(1-p)/p][V(x-1) - V(x-2)]
The two boundary conditions and this difference equation pin down the value function V():
And at the start, with x = a, the probability of player A's winning is:
