# A gambler with the devil's luck?

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? • 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? Jun 23, 2013 at 9:40 • 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. Jun 23, 2013 at 9:52 • He goes back down to 18 dollars. Jun 23, 2013 at 9:56 ## 3 Answers I drew your transition matrix for you, to better visualize the situation: 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. • Upvoted for the transition matrix. Jun 23, 2013 at 9:54 • +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. – Tim Jun 23, 2013 at 11:48 • 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!) Jun 23, 2013 at 18:47 • 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. Jun 24, 2013 at 0:33 • @Hatshepsut Would you believe me if I said it was MS Paint? :) And thanks for the compliment, much appreciated. May 26, 2016 at 16:28 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$. • 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. Jun 23, 2013 at 9:44 • Thanks @MarcvanLeeuwen for pointing that out. – Tim Jun 23, 2013 at 11:39 • @Tim Hi, How did you arrive at the solution to the equation of f(n)? Sep 20, 2015 at 5:24 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?). • Is this by the same process as Tim ? If not, could you pl. explain the process ? (Btw, d = 19) Jun 23, 2013 at 13:02 • Yes.$   \$
– Did
Jun 23, 2013 at 13:20