The simplified version of a (newspaper column) problem
goes like this:
A starts with 2 dollars and B with 1 dollar. They play
a game by tossing a fair coin. If it comes up heads,
A gives B one dollar. If it comes up tails, B gives A
one dollar.The game ends when either one runs out
of coins. What are the chances that A will win?
It is not difficult to draw out the tree in this case.
To win the game
1. A should "win" the first toss
2. Lose the first, and win the next two
Essentially, to win his path is
(LW)^n W, with n = 0, 1, 2, .....
where 'L' stands for losing and 'W' stands for
winning a toss.
The geometric sum gives the probablity as 2/3.
What I am after is the more complicated case of the
starting situation with A having 3 dollars and B with 2,
which is the problem in the newspaper.
Here the game does not terminate as easily as in the
previous case as there are many paths the "loop back"
to the starting configuration, unilke the "only way" in the
previous case. As the numbers increase for the
starting configuration, a player can recover even after
going into a prolonged losing streak -- something not
possible in the example.
What I am wondering is whether there is some sort of
recursive relation that can be written down to get the
probability of one of the players winning the game.
One wild guess is that in the starting state was (m, n),
the probability that A will win is
but I doubt life is that simple!