# Hitting probability of random walk within given number of steps

Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates.

What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially?

We can travel to 4 neighbors.

that is ( i , j+1 ), ( i , j-1 ), ( i-1, j ), ( i+1 , j ) if they are inside the matrix.

If there are only 3 neighbors which are inside the matrix then the probability with which we will go to that neighbor is 1/3(for each of the three).

How to solve this problem? I am able to find the solution for exactly k steps.

for exactly k steps problem, I make a matrix, dp[m][n][k+1]; initial all values are zero

except dp[x][y][0]=1;

dp[a][b][q]= weighted average of probablity of neighbours.

for example dp[0][0][4] = 0.5 * dp[1][0][3] + 0.5 * dp[0][1][3];

• Yes, now everything is well-defined. Perhaps you could also explain how to calculate the probability of arriving there in exactly $k$ steps, and why the same approach doesn't work for your actual question. Mar 23, 2019 at 12:26
For every point $$(a,b)$$ and number of steps $$t \leq k$$, compute inductively (i.e., using dynamic programming) the probability of reaching $$(a,b) \neq (x,y)$$ in $$t$$ steps without hitting $$(x,y)$$. Given this information, you can easily compute the probability of hitting $$(x,y)$$ in at most $$k$$ steps.