Use recurrence relation to find the probability

Question

Ram and Shyam have agreed to bet one dollar on each flip of a fair coin and to continue playing until one of the them wins all of other’s money. Use a recurrence relation to find the probability that Ram will win all of Shyam’s money if Ram starts with $a$ dollars and Shyam starts with $b$ dollars.

My attempt: Probability of Ram winning at $b$-th try = $\frac{1}{2} \times \frac{1}{2} \times \dots = (\frac{1}{2})^b$

Probability of Ram winning at $(b + 1)$-th try = $(\frac{1}{2})^{b+1}$

. . .

Summing up all probabilities till infinite tries, I get probability to be $\frac{\frac{1}{2}^b}{1-\frac{1}{2}}$ = $\frac{1}{2}^{b-1}$

Now I am pretty sure, my approach is incorrect. Can someone tell me how to solve this?

Answer 1

Hint: the following equation is the solution: $$p(a,b)=0.5\times\left(p(a-1,b+1)+p(a+1,b-1)\right)$$ $$p(1,1)=0.5$$ $$p(x,0) = 1, x\geq 1$$ $$p(0,y) = 0, y\geq 1$$

You can expand the equation:

$$p(a,b) = 0.5\times(p(a,b) + 0.5(p(a-2,b+2) + p(a+2,b-2)) = 0.5\times p(a,b) + \frac{1}{2^2}(p(a-2,b+2) + p(a+2,b-2)) \Rightarrow$$ $$(1-\frac{1}{2})p(a,b) = \frac{1}{2^2}(p(a-2,b+2) + p(a+2,b-2))$$

Expand another time:

$$(1-\frac{1}{2})p(a,b) = \frac{1}{2^2}(0.5(p(a-1,b+1) + p(a+1,b-1)) + 0.5(p(a-3,b+3) + p(a+3,b-3))) = \frac{1}{2^2}(p(a,b) + 0.5(p(a-3,b+3) + p(a+3,b-3)))\Rightarrow$$

$$(1-\frac{1}{2}-\frac{1}{2^2})p(a,b) = \frac{1}{2^3}(p(a-3,b+3) + p(a+3,b-3))$$

Answer 2

A further hint: Borrowing @OmG's notation, I make the unsurprising claim that $p(a,\,b)=\frac{a}{a+b}$, which satisfies the recursion relation and boundary conditions and $p(a,\,b)=1-p(b,\,a)$. See if you can prove the solution is unique.