# Gambler's Ruin with adsorbing state

Say we have a gamblers ruin Markov Chain where there's equal probability of winning and losing in each round. That is, if we have x dollars, the transition probabilities are:

$p(x,x+1)=1/2=p(x,x-1)$

Now we add a condition that says if we earn N dollars, we stop playing the game. This logically turns x=N into an absorbing state of the chain in addition to x=0. The question is to compute $P_x(N(0)<\infty)$ where $N(0)$ is the number of visits to state $0$. This is, probability that starting at state x, $N(0) < \infty$

The way I interpreted this is that if we ever visit 0, then were stuck there and will visit infinitely many times. So I rewrote the event as $P_x(N(0)<\infty)$ as equivalently the event that the chain absorbs at $N$. More explicitly, this would be if $V_N$={$\min n > 0 : X_n=N$} and $V_0$={$\min m > 0 : X_m=0$} then we want to compute the $P_x(V_N<V_0)$.

So I think I'm close. I let $h(x)$ be the probability we absorb in $N$ starting from state $x$. Naturally $h(0)=0$ and $h(N)=1$. A theorem in the book says that $h(x)$ is precisely the probability we want to compute. From the properties of the chain, for arbitrary $x \neq 0,N$ we have that:

$h(x)=\frac{1}{2} h(x-1)+\frac{1}{2}h(x+1)$

I'm just not sure how to compute from here. I think we can telescope sum somehow, but all I end up doing is going in circles. Or is this even the right approach to the question?

• Are you a chemist making a difference betwen adsorption (your title) and absorption :) – Jean Marie Jun 10 '17 at 7:04

The simple answer is that you will eventually hit either $0$ or $N$. As the game is fair, the expectation at any point is the same as your bankroll at the start. You will visit one of them infinitely many times. This says $h(1)=\frac 1N$ so the expectation if you start with $1$ is $0 \cdot \frac {N-1}N+ N \cdot \frac 1N=1$. It also gives $h(k)=\frac kN$ for $0\le k \le N$

• I don't follow on your statement that visiting either state infinitely many times implies $h(1)=\frac{1}{N}$. Can you clarify this? – Leif Ericson Jun 10 '17 at 4:18
• Once you get to $0$ or $N$ you stay there. The expectation at long time is then $0$ times the probability the state you stop in is $0$ plus $N$ times the probability that the state you stop in is $N$. These have to add to $1$. – Ross Millikan Jun 10 '17 at 4:24
• @LeifEricson Ross Millikan is saying that if $\tau$ is the time to hit the boundary then $E[X_\tau]=0 P(X_\tau=0) + N P(X_\tau=N)=E[X_0]$. This does not immediately follow from $E[X_n]$ being constant; he is implicitly using a theorem called the optional stopping theorem, which depends both on this process being a martingale (stronger than merely having constant expectation) and on properties of $\tau$ in this particular problem. An example where optional stopping does not apply is in the so-called martingale betting strategy (repeatedly play double-or-nothing until you win). – Ian Jun 10 '17 at 4:26
• Ok, but this computes the expectation, not the probability that we absorb in N? – Leif Ericson Jun 10 '17 at 6:38
• @LeifEricson You can solve the equation I wrote for $P(X_\tau=N)$. – Ian Jun 10 '17 at 14:17

If you have done linear algebra, you can do it with matrices, for example in Matlab/Octave:

P = diag(1/2*[1,1,1,1,0],1)+diag(1/2*[0,1,1,1,1],-1)+diag([1,0,0,0,0,1]);


This will give:

$${\bf P} = \frac 12 \left[\begin{array}{cccccc} 2&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&1&0&1&0&0\\ 0&0&1&0&1&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&2 \end{array}\right]$$

where a column vector $\bf v$ contains probability and multiplied right: ${\bf P}^n {\bf v}$ contains the distribution after $n$ gambles. The end scalars probability of the vector are for ruin and $5$ coins respectively.

Now you can use your knowledge of eigenvectors and eigenvalues if you want a closed form solution, or just let a computer do some matrix powers for you if a numerical solution is good enough.

The equation $h(x)=\frac{1}{2} h(x-1) + \frac{1}{2} h(x+1)$ is a linear recurrence relation with constant coefficients. It has characteristic polynomial $\frac{1}{2} x^2 - x + \frac{1}{2}$ which has a double root of $1$. Consequently its solutions are linear polynomials. Applying the boundary conditions gives the desired result.