Absorbing Markov chains... how do they work?

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

Absorbing Markov chains... how do they work?

Post by quilan » Tue May 10, 2011 1:40 am

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

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

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

Post by quilan » Tue May 10, 2011 2:43 am

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

Post Reply