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.

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

Would leave as comment, but too long:

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.

EDIT: As a side note, this does not become feasible even when the probability of win/loss is not 1/2. In this regime, you can still get useful bounds using KL-Divergence based estimates of binomial coefficients. This generalizes the entropy bounds mentioned earlier (See this math stack post if you are interested).

  • $\begingroup$ Thanks for your reply. A quick point on your reference to very large N values: then there are well-known closed form solutions to a., b., and c. they are a. B/( A+ B) , b. A/(A + B) , c. zero. $\endgroup$ – artbenis Jan 3 at 19:13
  • $\begingroup$ There are also approximate solutions for them e.g. for c. (A+B - 3)/N. $\endgroup$ – artbenis Jan 3 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.