# An efficient way to calculate probabilities for Markov chain/Random walks on a graph

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.

• I am a bit confused with the your sentence " i = {2, 4, 5} initial and then the node with i = 4 was randomly selected to be the initial node xx. So only the other two {2, 5}, " Could you expand on this please? Feb 8, 2018 at 13:28
• Actually, this is due to the biological context of the problem. The concept is to expand a network (biological pathway = network of genes) with nodes (genes) outside of that network. Imagine that you have the whole genome that is consisted out of 10 genes. From these 10, the 3 belongs to a specific pathway that you want to expand. The random walker should start from one of them and be absorbed by another one of them. So in order to achieve this, all genes of the pathway should be absorbing states except the one that the walker starts from. Feb 8, 2018 at 15:21
• I see, I'm just trying to make sense of that sentence in the context of the table Feb 8, 2018 at 15:54
• Which table? The first one? Feb 8, 2018 at 17:02
• Yes, the first one. Still do not understand how can why for $i=4$ the only other options are $\{2,5 \}$? Feb 8, 2018 at 19:03