# Gambler's Ruin and Markov Chains

Suppose that on each play of a certain game, a person will either win one dollar with the probability of $\frac{2}{3}$ or lose one dollar with probability $\frac{1}{3}$. Suppose also that the person's goal is to win two dollars (over his initial fortune) by playing this game. How large an initial fortune must the person have in order for the probability to be at least $0.99$ that he will achieve his goal before he loses his initial fortune?

I am stuck on what do after I find out when the game is fair $p = 0.5$ and when the game is not fair when $p$ does not equal $0.5$.

• You are asked to answer the following. Given that you start in state $N$, what is the probability that you hit state $N + 2$ before state $0$? You move from state $i$ to state $i - 1$ with probability $1/3$ and you move from state $i$ to state $i + 1$ with probability $2/3$. Find $N$ for which this probability is at least $0.99$. Hope this clears up some things. – Ritz Mar 11 '16 at 8:24

Say you have $k$ dollars and will stop if you reach either $0$ or $n$. Then the probability of winning (i.e. reaching $n$) satisfies the recurrence

$$x_k=\frac23x_{k+1}+\frac13x_{k-1}\;,$$

or

$$2x_{k+1}-3x_k+x_{k-1}=0\;.$$

The ansatz $x_k=\lambda^k$ yields the characteristic equation $2\lambda^2-3\lambda+1=0$ with solutions $\lambda=1$ and $\lambda=\frac12$. Thus the winning probability has the form $x_k=c_1+c_22^{-k}$. Substituting $x_0=0$ and $x_n=1$ yields $c_1+c_2=0$ and $c_1+c_22^{-n}=1$ and thus $c_1=-c_2=1/(1-2^{-n})$ and

$$x_k=\frac{1-2^{-k}}{1-2^{-n}}\;.$$

You want $x_{n-2}\ge0.99$ and thus

$$\frac{1-2^{-(n-2)}}{1-2^{-n}}\ge0.99\;,$$

or $(1-0.99)\ge(4-0.99)2^{-n}$ and thus $n\gt8.23$. With $n=9$, the initial fortune must be $9-2=7$.