Gambler’s Ruin in finite time - solve by Markov chains?

Consider the Gambler's Ruin Problem: an infinite Markov process of steps with binary outcomes of plus or minus, each of equal probability. At each step of the process there may be a play of the game.

At each play of the game starting with step 1, the gambler's initial fortune, B, increases by one unit with probability 1/2 or decreases by one unit with probability 1/2. The game ends at step N or sooner (after fewer plays) if the gambler's profit first reaches a Target of +A or a Ruin (total loss) of -B units anytime during the process (which continues beyond N steps).

There are three profit outcomes after step N: -B, +A, or Neither.

Ruin is defined by profit reaching -B for the first time during N plays without first reaching +A. Success is defined by profit reaching +A for the first time during N plays without first reaching -B.

Problem: What is the probability of a. Ruin or b. Success or c. Neither, in terms of A, B, N?

I cannot solve this except by path-counting. Can a.,b.,c. be solved in a closed form by Markov chains?

This problem is also called a random walk of a particle in finite time with two absorbing barriers.

• He will be ruined – AkatsukiMaliki Jan 2 at 17:10
• @AkatsukiMaliki. Not so. For example with A = B= N=2, P of Neither = 1/2. – artbenis Jan 2 at 18:04

Since each path corresponds to a 0-1 bit string on Length $$N$$, you must implicitly compute the sum of binomial coefficients to determine your final probabilities. I think this is what you are already doing (my interpretation of path counting?). Unfortunately, summing binomial coefficients is infeasible for large values of $$N$$, so this is the best you are going to be able to do. For large $$N$$, Determining exact values for the sum of binomial coefficients is not possible (It would make my research a lot easier if it was :)), we only know of good approximations (again, this is assuming N is very large, otherwise you can just sum up the binomial coefficients you're interested in via some math program). Depending on the relationship between $$N$$ $$B$$ and $$A$$, you may be able to find asymptotically tight bounds for the desired probabilities. I would recommend checking out Stirling's approximation, Entropy bounds for binomial coefficients, and related literature. This may be a useful resource if you are interested in the "large N" regime.