A gambler with $1$ dollar intends to make repeated bets of $1$ dollar until he wins $20$ dollars or is ruined. Probabilities of win/loss are $p$ and $(1-p)$, and each bet brings a gain/loss of $1$ dollar.

Unfortunately, the devil is active, and ensures that every time he reaches $19, he loses! Obviously, the poor guy will get ruined sooner or later!

The question is, what is the expected number of bets he makes until he is ruined?

  • $\begingroup$ What does "every time he reaches \$19, he loses" mean: does it just mean that if he makes a bet when on \$19, he is guaranteed to lose that bet (and therefore move to \$18, and continue playing), or that he somehow magically gets ruined (all his money disappears, say) when he reaches \$19? $\endgroup$ – ShreevatsaR Jun 23 '13 at 9:40
  • 2
    $\begingroup$ He goes back down to 18 dollars, I think. If he can get to 19 dollars multiple times (since he loses "every time"), then he doesn't go down to 0 at 19. $\endgroup$ – markovchain Jun 23 '13 at 9:52
  • 1
    $\begingroup$ He goes back down to 18 dollars. $\endgroup$ – true blue anil Jun 23 '13 at 9:56

Let $f(n)$ be the expected number of bets given that the gambler has £$n$. (My gambler is British to save messing around with dollar signs).

for every integer $0<n<19$ we have $$f(n) = 1 + pf(n+1) + (1-p) f(n-1)$$

Solutions to this equation look like $$f(n) = \alpha + \beta\left(\frac{1-p}p\right)^n + \frac n{1-2p}\tag 1$$ and by recursion this formula must hold for $0\leq 1\leq19$. We must have $f(0)=0$ and because of the unholy involvement we have $f(19) = 1+f(18)$, that is $$\begin{align} \alpha + \beta &= 0 \\ \alpha + \beta \left(\frac{1-p}p\right)^{19} + \frac {19}{1-2p} &= \alpha + \beta \left(\frac{1-p}p\right)^{18} + \frac {18}{1-2p} + 1 \end{align}$$

Rearranging $$\begin{align} \frac{1}{1-2p}&= \beta\left(\frac{1-p}p\right)^{18}\frac{2p-1}p \\ \beta &=-\left(\frac{1-p}p\right)^{-18}\frac{2p^2}{(1-2p)^2} \end{align}$$

So substituting into $(1)$ we get the same answer as given by Did.


As pointed out below this answer is invalid when $p=\frac 12$ because the particular solution $\frac{n}{1-2p}$ is infinite. In this case notice that $f(n) = -n^2$ satisfies $f(n) = 1+\frac{f(n+1) + f(n-1)}2$ hence all solutions will be in the form $$f(n) = \alpha + \beta n -n^2.$$ Which is solved as before with $\alpha = 0, \beta=37$.

  • 1
    $\begingroup$ It might be noted that this method works except in the "easy" case $p=\frac12$ (essentially because the formula for summing a geometric series fails when the ratio is$~1$, I think). I guess is easier to do that case separately than by a limiting argument from the solution given here. $\endgroup$ – Marc van Leeuwen Jun 23 '13 at 9:44
  • $\begingroup$ Thanks @MarcvanLeeuwen for pointing that out. $\endgroup$ – Tim Jun 23 '13 at 11:39
  • $\begingroup$ @Tim Hi, How did you arrive at the solution to the equation of f(n)? $\endgroup$ – xkcvk2511 Sep 20 '15 at 5:24

I drew your transition matrix for you, to better visualize the situation:

Transition Matrix

Notice, of course, that there's no way to get to 20 dollars. It might as well be removed, but I wanted to put it there anyway.

I'll just explain what Tim did and how he did it, using the transition matrix.

First of all, let's define $\mu_i$ such that it is the expected number of "steps" to reach 0 dollars. Each "step" is simply a transition from 1 state (a circle) into another state (another circle).

So at $\mu_0$, we have $\mu_0 = 0$ because we're already there. The gambler is already ruined.

With just 1 dollar, we need to take 1 step either to state 0 or state 2. So whatever happens, our expected number of steps is always at least 1.

We therefore have $\mu_1 = p\mu_2 + (1-p)\mu_0 + 1$ because there is a $1-p$ chance to get to state 0, and a $p$ chance to get to state 2.

Generally, $\mu_n = p\mu_{n+1} + (1-p)\mu_{n-1} + 1$ which is exactly what Tim did. You can verify this on your diagram.

So with your $i$ ranging from 0 to 19 (we don't need to consider 20 since there is no way to get to it), you have 20 equations to define all your $\mu_i$ as well as 20 unknowns.

From here, it's only a matter of solving systems of equations. Tim showed a good shortcut though, so you probably want to do that instead.

  • 4
    $\begingroup$ Upvoted for the transition matrix. $\endgroup$ – medivh Jun 23 '13 at 9:54
  • 1
    $\begingroup$ +1 for the picture and the helpful explanation. I should point out though that I never considered the transition matrix. I just looked for a martingale in the form $f(n)-t$, which works even for non finite state spaces. $\endgroup$ – Tim Jun 23 '13 at 11:48
  • 1
    $\begingroup$ Is this the concept of "Markov Chains?" I've always wanted to understand them, but have never found a good explanation (but, I understand this!) $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 23 '13 at 18:47
  • $\begingroup$ Yup, it is a Markov chain. And it's the inspiration for my name. A Markov chain is just any system with an identifiable state, but whose state in the next period depends entirely upon its present state and none of its past states. $\endgroup$ – markovchain Jun 24 '13 at 0:33
  • 1
    $\begingroup$ @Hatshepsut Would you believe me if I said it was MS Paint? :) And thanks for the compliment, much appreciated. $\endgroup$ – markovchain May 26 '16 at 16:28

If the devil intervenes when you reach level $d$ (here $d=19$), the mean time before ruin occurs is $$ E_1(T)=\frac1{1-2p}\,\left(1-2p\left(\frac{p}{1-p}\right)^{d-1}\right). $$ If $p=\frac12$, one should consider the limit of this when $p\to\frac12$, which yields $$ E_1(T)=2d-1. $$ Sanity checks: If $d=1$ then $E_1(T)=1$ for every $p$ (why?). If $p\lt\frac12$, $E_1(T)$ stays bounded when $d\to\infty$ (why?). If $p\gt\frac12$, $E_1(T)$ grows exponentially fast when $d\to\infty$ (why?).

  • $\begingroup$ Is this by the same process as Tim ? If not, could you pl. explain the process ? (Btw, d = 19) $\endgroup$ – true blue anil Jun 23 '13 at 13:02
  • 1
    $\begingroup$ Yes. $ $ $ $ $ $ $\endgroup$ – Did Jun 23 '13 at 13:20

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.