## Absorbing Markov chains... how do they work?

Mechanics, discrete, statistics, ...
quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

### Absorbing Markov chains... how do they work?

So I've used Markov chains plenty before, but only in the case of one absorbing state. I was playing around with a super simple example of a random walk, and I got really confused by the results.

The simple random walk is: [x] <- [a] <-> -> [y] with equal probabilities in each direction.

In canonical form, the transition matrix looks like:
$\begin{array}{c} a \\ b \\ x \\ y \end{array} \left[ \begin{array}{cccc} 0 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right] = \left[ \begin{array}{cc} Q & R \\ 0 & I \end{array} \right]$

I never covered these in any of my classes, so all info has been from online texts. Assuming I start at node [a], I get both via simulation and online equations, that: P[x] = 2/3, P[y] = 1/3. That is, given infinite simulations, 2/3'rds of them will end in [x], 1/3 will end in [y].

So here's the problem. How long it takes before the walk is absorbed into each x & y node. I haven't found any information online regarding the expected hit time for each end-point. Given a very simple simulation (code below), it's noticed (starting from [a]) that the average number of nodes traveled until hitting [x] is 5/3, and the average to hit [y] is 8/3.

Previously, I'd simply have done a recurrence relation as follows [x] <- [a] <-> -> [y]:
E[x to x] = 0
E[a to x] = (E[x to x]+1)/2 + (E+1)/2
E = (E[a to x]+1)/2 + 0

Yields: E[x to x] = 0, E[a to x] = 5/3, E = 4/3.
The value for E[a to x] is correct, but E is not. I'm been pouring over literature & fiddling with numbers and equations for days now trying to figure it out to no avail. What am I missing here?

Python sim, very simple.

Code: Select all

def sim4():
lst=time();

trial=0;
total_length=[0]*2;
times=[0]*2;
while True:
trial+=1;
room=0; travel=0;
while True:
if(room==0): room=choice([1,2]);
elif(room==1): room=choice([0,3]);
else: break;
travel+=1;
termroom=room-2;
total_length[termroom]+=travel;
times[termroom]+=1;

if(time()-lst>10):
lst=time();
EX,EY = [float(total_length[i])/times[i] for i in [0,1]];
PX,PY = [float(times[i])/sum(times) for i in [0,1]];
print "E[x]=%r\tE[y]=%r\tP[x]=%s\tP[y]=%s\t\t%s\t%s"%(EX,EY,PX,PY,total_length,times);

from random import choice;
sim4();

ex ~100%'er... until the gf came along.

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

### Re: Absorbing Markov chains... how do they work?

AHAH! I think I figured it out! if $N = (I-Q)^{-1}$, the correct values are $\frac { N^2R } { NR }$, where it's element-wise division of the upper & lower matrices.

Derivation:
Given a transition matrix $M = \left[ \begin{array}{cc} Q & R \\ 0 & I \end{array} \right]$

Expected value is: $E[X] = \displaystyle\sum\limits_{n=1}^\infty nP[X=n]$. In this scenario, we need to find the probability at each turn that a terminus is reached. It turns out, that's pretty simple. If $M' = \left[ \begin{array}{cc} Q & R \\ 0 & 0 \end{array} \right]$ and $M'^n = \left[ \begin{array}{cc} Q^n & RQ^{n-1} \\ 0 & 0 \end{array} \right]$, then $P[x=n] = RQ^{n-1}$.

So, $E[X] = \displaystyle\sum\limits_{n=1}^\infty nP[X=n] = R + 2RQ^1 + 3RQ^2 + 4RQ^3 + ... = (I-Q)^{-2}R$.

Or if $N = (I-Q)^{-1}$, then $E[X] = N^2R$. This gives the expected value overall, but if we wanted to limit it to the condition given in the original post, we'd see $P[X] = NR$, so $E[X]/P[X] = \frac { N^2R } { NR }$. I know I'm not using the correct terms most likely, but hurray for figuring it out.

Example:
Given the chain [x] <- [a] <-> -> [y], x and y are absorbing states. The transition matrix is:
$\begin{array}{c} a \\ b \\ x \\ y \end{array} \left[ \begin{array}{cccc} 0 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right] = \left[ \begin{array}{cc} Q & R \\ 0 & I \end{array} \right]$, so $Q = \left[ \begin{array}{cc} 0 & 1/2 \\ 1/2 & 0 \end{array} \right]$ and $R = \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]$

$N = (I-Q)^{-1} = \left[ \begin{array}{cc} 4/3 & 2/3 \\ 2/3 & 4/3 \end{array} \right]$. We'll say $P = NR = \left[ \begin{array}{cc} 4/3 & 2/3 \\ 2/3 & 4/3 \end{array} \right] \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right] = \left[ \begin{array}{cc} 2/3 & 1/3 \\ 1/3 & 2/3 \end{array} \right]$ and thus the equation above becomes:

$E/P = \frac { N^2R } { NR } = \frac { NP } { P }$, where division is done element-wise. Thus (for columns $x$ and $y$... I suck at latex):
$E/P = \frac { \left[ \begin{array}{cc} 10/9 & 8/9 \\ 8/9 & 10/9 \end{array} \right] } { \left[ \begin{array}{cc} 2/3 & 1/3 \\ 1/3 & 2/3 \end{array} \right] } = \begin{array}{c} a \\ b \end{array} \left[ \begin{array}{cc} 5/3 & 8/3 \\ 8/3 & 5/3 \end{array} \right]$
ex ~100%'er... until the gf came along.