Recurrence problem with a game of probability

Question

Fair coin flipping (50% on both sides)

$P_1$ and $P_2$ plays a few games of fair coin flipping. Assume player $A$ starts with $x$ coins and player $B$ with $y$ coins.

Let $P_n$ denote the probability of player $A$ winning all coins. Find $P_0$ and $P_{x+y}$, then write a difference equation for $P_n$. Solve the difference equation

Find the odds of player $A$ winning over player $B$ if $A$ starts with, e.g. half the coins $B$ starts with.

How far I've come

I've been able to produce a recurrence relation $P_n = \frac{1}{2}P_{n+1} + \frac{1}{2}P_{n-1}$.

And I assume $P_0 = 0, P_{x+y}=1$, since when player $A$ has 0 coins, he also has $0\%$ chance of winning, and when player $A$ has $x+y$ coins, he's already won, therefore it would be $100\%$ Correct me if I'm wrong.

All help appreciated, thanks a lot.

Answer 1

The characteristic polynomial of this recurrence relation is $r=\frac{1}{2}(r^2+1)$ with double root $r=1$. So the probabilities have the form $P_n=A+Bn$, and the boundary conditions imply $P_0=A=0$, $P_{x+y}=B(x+y)=1\implies P_n=\dfrac{n}{x+y}$. Thus the probability is a linear function of $n$, which on reflection is consistent with $P_n=\frac{1}{2}(P_{n-1}+P_{n+1})$.

Answer 2

Solution

$$P_n = \frac{1}{2}P_{n+1} + \frac{1}{2}P_{n-1} \implies \frac{1}{2}P_{n+1} - P_n + \frac{1}{2}P_{n-1} = 0$$ Which gives the characteristic equation:

$\alpha^2-2\alpha+1=0 \implies(\alpha-1)^2=0 \implies\alpha=1$ (Double root)

General solution:

$P_{hn} = C_1\alpha_1^n + n\cdot C_2\alpha_2^n = C_1+n\cdot C_2$

$P_0 = C_1+0\cdot C_2 = C_1 = 0$

$P_{x+y} = C_1+C_2(x+y) = C_2(x+y) = 1 \implies C_2 = \frac{1}{x+y}$

$\implies P_n = n\cdot \frac{1}{x+y} = \frac{n}{x+y}$