I'm working on the extra credit for my Discrete Structures homework, but so far I have been unable to get a handle on the problem, even with help from 3rd parties, so I've decided to turn to you guys. The title explains the essentials, but I've included the full wording below, along with some notes.
Extra Credit Problem: Consider a game of gambling, where Bob started with 20 dollars in his pocket. Each time Bob wins, he will earn 1 dollar and each time he loses he will lose 1 dollar. A fair coin is flipped to decide win or loss, head = win & tails = loss. Bob will stop playing if his balance reaches 100 dollars or 0 dollars. What is the probability that Bob is ruined? (He loses all his money, as opposed to returning home with $100 in his pocket.)
The question is as such:
Let $P_k$ be the probability that Bob is ruined when he has k dollars in his pocket.
a. Write a recurrence relation for $P_k$
b. Solve the recurrence relation to find the answer.
Note that $P_0 = 100\%$ (with no money Bob is ruined) and $P_{100} = 0\%$ (Because Bob returns with 100 dollars in his pocket and the game is over for Bob, so he is not ruined.)
Basically, I'm at a loss for how to create this recurrence relation. I started by investigating what information I might be able to derive from the given values of P, but honestly I'm not sure if this is really helpful. Solving the relations does not seem to be as difficult, but creating them has proved extremely challenging for me, if anyone has advice on a good way to think about this or some sort of methodology that helps you personally it would be well received.
Any help you could provide is much appreciated, I'd really like to get this extra credit or at least be able to understand how it works, because the professor generally doesn't go over the HW unless explicitly asked about a problem and even then it's very quickly, so that we have time in lecture to cover the new/current material. Also, the next time we have lecture will be the same day the HW is due, which limits the time I'll be able to spend with any hints given.
Best Answer
If he has $k$ dollars, there is a $50\%$ chance he loses a dollar and a $50\%$ chance he gains a dollar. Then the probabilities for those amounts determine how likely he will be ruined. The relation is $$P_k=\frac12P_{k-1}+\frac12P_{k+1}$$ Which when combined with the initial conditions is $$P_{k+1}=2P_k-P_{k-1}; \,P_0=1, P_{100}=0$$ From here you can solve the recurrence relation to get $$P_k=1-\frac k {100}$$