0
$\begingroup$

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?

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

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$

$\endgroup$
  • $\begingroup$ I don't follow on your statement that visiting either state infinitely many times implies $h(1)=\frac{1}{N}$. Can you clarify this? $\endgroup$ – Leif Ericson Jun 10 '17 at 4:18
  • $\begingroup$ 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$. $\endgroup$ – Ross Millikan Jun 10 '17 at 4:24
  • $\begingroup$ @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). $\endgroup$ – Ian Jun 10 '17 at 4:26
  • $\begingroup$ Ok, but this computes the expectation, not the probability that we absorb in N? $\endgroup$ – Leif Ericson Jun 10 '17 at 6:38
  • $\begingroup$ @LeifEricson You can solve the equation I wrote for $P(X_\tau=N)$. $\endgroup$ – Ian Jun 10 '17 at 14:17
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.