0
$\begingroup$

Edit 3. Fixed question to be more clear and include current solution

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

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

1 Answer 1

Reset to default
3
$\begingroup$

Say you have k coins. Then after the first flip, you are equally likely to have k-1 or k+1.

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)$.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – B. Lee
    Sep 18, 2014 at 15:05
  • 1
    $\begingroup$ Edited to clarify! $\endgroup$
    – Julia Hayward
    Sep 18, 2014 at 15:27
  • $\begingroup$ 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? $\endgroup$
    – B. Lee
    Sep 18, 2014 at 15:33
  • 1
    $\begingroup$ 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$ $\endgroup$
    – Julia Hayward
    Sep 19, 2014 at 9:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .