# The probability of seeing a vertex $v_j$ in less than $K$ steps from another vertex $v_i$

I want to calculate the probability of seeing vertex $$v_j$$ in a random walk in less than $$K$$ steps from vertex $$v_i$$ for every pair of vertices. Is there any approach for this problem in polynomial time? Actually I want to calculate the $$p(v_j|v_i)$$ in a window of width $$K$$, but my problem is that there might be more than one path from $$v_i$$ to $$v_j$$.

• What do you know about the graph? If the graph is finite or regular or something, this sounds a lot easier than in full generality. – quarague Feb 14 at 10:29
• Yeah, we know that graph is finite but not regular, may be with power law degree distribution. – user137927 Feb 14 at 10:41
• If the graph is finite, you can solve this with a version of the adjacency matrix. Compute the matrix $A$ that gives you the probability for every vertex after a random walk with $1$ step. To figure out what happens after $K$ steps you only need the $K$th power fo this matrix $A^K$. Note that you only need to compute this matrix once and then can use it for all vertices. – quarague Feb 14 at 12:01
• I thought there might be a better solution with less time complexity that matrix multiplication. Thanks a lot for your help. – user137927 Feb 14 at 12:16
• Matrix powers can be computed a lot more efficiently than by just multiplying a matrix by itself over and over again by diagonalizing it first. Whether this actually helps depends on the size of your graph and the range of $K$. If the graph is small and $K$ is big or you want a lot of different values of $K$, this is much faster. If the graph is huge and you only need relatively low values of $K$ just multiplying the matrices might be faster. – quarague Feb 14 at 12:55