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

271 Views Asked by At

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

1

There are 1 best solutions below

4
On BEST ANSWER

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