Some of you might remember me from previous posts on Markov chains on top of biological data [1,2]. Finally, I managed to understand the basic concept of the procedure after reading it again and again for a week.
So let me guide you through an explanation trip on what is going on that paper and then I would like to help me, telling me if there is any other easier way to calculate the followings.
For those that didn't read my previous posts, we begin with a transition matrix ${^{x}}P= \left(\begin{array}{cc} {^{x}}Q & {^{x}}R \\ 0 & I \\ \end{array} \right)$.
In that transition matrix, a subset of nodes have been set as absorbing states and denoted as $S$ but ONLY one (randomly selected) node of them is turned into transient state and at the same time is the initial node $x$ for the random walker.
The first step is to run many times the random walker and get a list of its pathways and keeping only the ones that do not overcome the predefined length $L_{max}$.
Next, one have to calculate the folowing expression (The expected number of times the edge (i, j), is visited while starting the walk in x given that the walk length is L ) for each transition pair (i, j).
$$E[e(x,i,j)|L]=\sum_{k=0}^{L-1}\frac{P[X_{k}=i,X_{k+1}=j,L|X_{0}=x]}{P[L|X_{0}=x]}$$
To calculate this first you calculate the nominator and the denominator by using (more details at the paper):
A) For nominator
$${} \begin{aligned} &P\left[X_{k}=i,X_{k+1}=j,L|X_{0}=x\right]= \\ &\left\{\begin{array}{lll} f(i,j,k,x,r,L) & j \ is \ a \ transient \ state \\ \left[({^{x}}Q){^{L-1}}\right]{_{xi}}[({^{x}}R) ]{_{ij}} & j \ is \ an \ absorbing \ state \end{array}\right. \end{aligned}$$
B) For denominator
$$P[L|X{_{0}}=x]=\mathop{\sum}\limits_{r\in S \backslash \{x\}}[({^{x}}Q){^{L-1}}({^{x}}R) ]{_{xr}}$$
DEMO
Now let me show you how did I approach it. Here I will demonstrate only the part of the denominator calculation because it takes less place.
1)
Here is pictured the initial transition matrix. And as you can see the selected nodes that belong to the $S$ are the nodes with i = {2, 4, 5} initial and then the node with i = 4 was randomly selected to be the initial node $x$. So only the other two {2, 5}, are turned into absorbing states.
Also, we define the $L_{max} = 5$
2)
Running many times the random walker (here I run it three times for simplicity) we take the following paths ONLY for $x = 4$ (as initial node):
[ Walk 1 ]
Step-1 : i=4 -> j=4
Step-2 : i=4 -> j=1
Step-3 : i=1 -> j=5 ( i=5 is absorbing state and we keep Walk 1 because L < Lmax )
[ Walk 2 ]
Step-1 : i=4 -> j=4
Step-2 : i=4 -> j=1
Step-3 : i=1 -> j=6
Step-4 : i=6 -> j=3
Step-5 : i=3 -> j=5 (i=5 is absorbing state and we keep Walk 2 because L = Lmax )
[ Walk 3 ]
Step-1 : i=4 -> j=4
Step-2 : i=4 -> j=6
Step-3 : i=6 -> j=3
Step-4 : i=3 -> j=3
Step-5 : i=3 -> j=2 (i=2 is absorbing state and we keep Walk 3 because L = Lmax )
3)
Calculating the probability of a walk of length $L=5$ starting in $x=4$ and got absorbed at any absorbing state ($r\in S \backslash \{x\}$) is given by:
$$P[L|X{_{0}}=x]=\mathop{\sum}\limits_{r\in S \backslash \{x\}}[({^{x}}Q){^{L-1}}({^{x}}R) ]{_{xr}}$$
In that case as we said we have only two absorbing states {2 & 5} and also $(^xQ)^{L-1} = (^xQ)^4$ is going to look like:
While the $(^xR)$ is taken from the initial matrix and it is :
By multiplying both of the above matrices we have the following one :
And so the probability of a walk of length $L=5$ starting in $x=4$ and stopping at either of the both absorbing states is the sum of:
A : For absorbing state 2 = 0.031
B : For absorbing state 5 = 0.047
$$P[L|X{_{0}}=x]=\mathop{\sum}\limits_{r\in S \backslash \{x\}}[({^{x}}Q){^{L-1}}({^{x}}R) ]{_{xr}} = 0.031 + 0.047 = 0.078$$
The same must be done for every $L <= L_{max}$ and respectively for the nominator of the first fraction I posted, one should calculate it for every pair of transition states (i,j).
So what interest me and I want to ask you at that point, is if there is any way algorithmicaly, more efficient to calculate those quantities and not one by one for every length and every transition pair.
Thanks.