In section 4.6 of his book on probability models, Ross analyzes the gambler ruin problem (a gambler who starts with some units of money, stops when he either reaches N or goes broke). In particular, he provides an expression for the expected number of time units the gambler will spend in each of the possible states. This got me thinking about a rich gambler. So rich, that his fortune is bottomless. This guy can afford to take an infinite amount of debt from his account. So, -1, -2, -3, … are all possibilities for him. He simply keeps tossing his coin till his accumulated fortune reaches N. Now, the important difference is that his state space becomes infinitely large. In Ross's example since the state space was finite, we got:


(here, $S$ is the matrix of expected time units spent in state $j$ given one starts in state $i$ and $P_T$ is the transition probability matrix).

For the bottomless gambler, this simply becomes an infinite system of equations with no recursively cancelling terms.

$$s_{i,j} = \delta_{i,j} + (1-p)s_{i-1,j}+ps_{i+1,j}$$

The problem obviously has an answer. How do I go about solving it?

  • 1
    $\begingroup$ Note that this is the inverse of gambler's ruin. The gambler now has an unlimited bankroll and the casino only has $N$. This means the gambler will win with probability $1$ as long as the individual probability of winning is at least $\frac 12$. The probability he visits $0$ and all positive states is $1$. This plus the limit of $0$ at $-\infty$ gives the boundary conditions you need. $\endgroup$ – Ross Millikan Nov 12 '18 at 3:39
  • $\begingroup$ Shouldn't the gambler win with probability 1 even if $p<1/2$? Because by definition, he keeps trying till he wins. Also, I think you assumed he starts with a fortune of 0. That was not my original intention, but it should be equivalent since we can just shift everything. I'll think about it more, but am currently having a hard time imagining how I would make use of that infinite boundary condition. $\endgroup$ – Rohit Pandey Nov 12 '18 at 4:00
  • $\begingroup$ No, if $p \lt \frac 12$ there is a finite probability he never hits $N$. It seemed from the question that he starts at $0$, but because his fortune is infinite he never goes broke and can keep playing from any negative state. I took the states to be his net at each time. $\endgroup$ – Ross Millikan Nov 12 '18 at 4:19
  • $\begingroup$ @RossMillikan - do you have any reference for how we would calculate the probability he would win as a function of $p$ when $p<\frac{1}{2}$? Also, the only way I can think of for using the infinite boundary condition is to take a very large negative number and assume he never crosses it. Is that what you had in mind? $\endgroup$ – Rohit Pandey Nov 12 '18 at 4:51
  • $\begingroup$ No, I don't have a solution. I would start with the $N=1$ case. The probability he wins is $p$ that he wins from $0$ plus $(1-p)$ times the probability he wins from $-1$. Write $f(n)$ as the probability that he wins from $n$ and make a recurrence. You can then just shift it for higher $N$. $\endgroup$ – Ross Millikan Nov 12 '18 at 5:28

Your Answer

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

Browse other questions tagged or ask your own question.