28
$\begingroup$

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?

$\endgroup$
3
  • $\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$ Jun 23, 2013 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$ Jun 23, 2013 at 9:52
  • 1
    $\begingroup$ He goes back down to 18 dollars. $\endgroup$ Jun 23, 2013 at 9:56

3 Answers 3

37
$\begingroup$

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.

$\endgroup$
6
  • 4
    $\begingroup$ Upvoted for the transition matrix. $\endgroup$
    – shieldfoss
    Jun 23, 2013 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, 2013 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$ Jun 23, 2013 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$ Jun 24, 2013 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$ May 26, 2016 at 16:28
26
$\begingroup$

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.

Edit:

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$.

$\endgroup$
3
  • 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$ Jun 23, 2013 at 9:44
  • $\begingroup$ Thanks @MarcvanLeeuwen for pointing that out. $\endgroup$
    – Tim
    Jun 23, 2013 at 11:39
  • $\begingroup$ @Tim Hi, How did you arrive at the solution to the equation of f(n)? $\endgroup$ Sep 20, 2015 at 5:24
3
$\begingroup$

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?).

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .