A gambler with the devil's luck?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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