# Chance of being able to quit while ahead in a betting game (Markov chain with gambler's ruin)

Suppose a player starts with $N$ chips, and is playing a game with odds $O$, betting 1 chip in each iteration. When the player reaches 0 chips the betting must end.

What is the probability that at some point the player has $N+M$ chips (i.e. $M$ more than they started with)?

The most interesting question here to me is -- are there games with disfavorable odds where the player is still more likely than not to have more than $N$ chips at some point (e.g. games where the most likely outcome is a downward sawtooth that exceeds $N$ at some points before reaching 0)?

I'm not really familiar with the language of odds, but if I misunderstood what you meant, it should be easy to adapt the answer to your needs.

Let $p$ be the probability that you win a chip and $1-p$ the probability that you lose a chip. The question is about the probabilities of $0$ or $N+M$ being reached first, starting from $N$. Let $a_k$ be the probability of $N+M$ being reached first, starting from $k$; so we're looking for $a_N$. The probabilities $a_k$ satisfy the recurrence

$$a_k=pa_{k+1}+(1-p)a_{k-1}\;.$$

The characteristic equation is

$$p\lambda^2-\lambda+(1-p)=0\;,$$

with characteristic values $\lambda=1$ and $\lambda=(1-p)/p$. If I understand the term correctly, $(1-p)/p$ is precisely the odds $O$ against your bet, so we have

$$a_k=c_1+c_2O^k\;.$$

The boundary values $a_0=0$ and $a_{N+M}=1$ yield $c_1+c_2=0$ and $c_1+c_2O^{N+M}=1$, with solution $c_1=-c_2=1/(1-O^{N+M})$, so

$$a_k=\frac{1-O^k}{1-O^{N+M}}$$

and

$$a_N=\frac{1-O^N}{1-O^{N+M}}\;.$$

For even odds ($p=1/2$, $O=1$), this is to be understood as a limit, which can be evaluated using L'Hôpital's rule to obtain $a_N=N/(N+M)$.

For it to be more likely than not that $N+M$ is reached, we want $a_N\gt1/2$, and thus

\begin{align} \frac{1-O^N}{1-O^{N+M}}&\gt\frac12\;,\\ O^N\left(2-O^M\right)&\lessgtr1\;, \end{align}

for $O\lessgtr1$.

• @zyx: Sure there's a double root. One root is always $1$, and the other is also $1$ for $p=1/2$. That's why $a_k$ is linear in $k$ for $p=1/2$. Mar 9, 2013 at 0:43
• Is it correct to say then that if $p < .5$ then $A_n$ must be as well? Mar 15, 2013 at 5:30
• @babonk: You mean $a_N$? No, that would be strange. With $M=1$, your chances of reaching $N+1$ are much better than $1/2$ if $p\lesssim1/2$. Mar 15, 2013 at 9:10
• Got it. This is a fun problem to graph out with different M's, N's, and p's for whoever is interested. Turns out that you can't do this at p < 1/3 no matter what Mar 16, 2013 at 1:06