# Problem

Two players player 1 and player 2 plays a game of fair coin flipping. Player 1 starts with $$A$$ coins and Player 2 with $$B$$ coins. Let $$P_n$$ defines the probability of player 1 winning all coins in a game when player 1 has $$n$$ coins. Find the recurrence relation of $$P_n$$ and then find its closed formula.

This formula can then be used to know the probability of player 1 winning if he has, i.e. twice the coins player 2 has.

# Solution?

I know that $$P_0 = 0$$, because if she has $$0$$ coins, then she can't win, what about $$P_{A+B}?$$

$$P_n = 0.5P_{n+1} + 0.5P_{n-1}$$ Which gives the characteristic equation: $$x^2-2x+1 = (x-1)^2=0 \implies x=1\ (double\ root)$$ This can then be put into the general solution for linear homogenous recurrence relations: $$P_{hn} = C_1+nC_2$$ and here I'm stuck once again. To find these two values I'd need two boundary points

• I changed the whole post to be a lot more clear what I need help for. Sep 18, 2014 at 15:19
• The other boundary condition is $P_{A+B}=1$.
– user940
Sep 18, 2014 at 17:35
• @XMLParsing: This question was duplicated a few hours later, which I provided a solution to before I noticed this earlier question. Sep 18, 2014 at 22:10

So the probability of winning all from a starting point of $k$ is $P_k = 0.5 P_{k+1} + 0.5 P_{k-1}$
It's fairly easy from here to verify that $P_k = k/(n_1+n_2)$.
• Thank you, exactly what I was looking for. One question, does $P_k$ denote the probability of winning all coins, or does it denote the probability of losing all coins? Sep 18, 2014 at 15:05
• Thank you for you help. You claim it's fairly easy to verify the formula. However, I'm puzzled because I can't seem to iterate it, as I only have one boundary $P_0 = 0$ and I can't solve it like a normal recurence relation either. Have any idea on how to solve the recurrence relation? Sep 18, 2014 at 15:33
• The other boundary is $P_{n_1+n_2}=1$ - if you have all the coins already, success is certain. Then the standard way to tackle these recurrence relations is to solve the characteristic polynomial $t = 0.5t^2 + 0.5$ - this has a repeated root of 1 so your general solution is $P_k = A1^k + Bk1^k$ for some $A, B$ Sep 19, 2014 at 9:17