# 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];

answer will be dp[i][j][k];

• This question is impossible to answer unless you define a probability distribution on your random walk. – Yuval Filmus Mar 23 '19 at 10:36
• we can move to any of the 4 neighbours with equal probability. – Manoharsinh Rana Mar 23 '19 at 10:37
• What happens if we have fewer than 4 neighbors? – Yuval Filmus Mar 23 '19 at 10:38
• Don't say "let's say", since afterwards you might change your mind. Decide first on what problem exactly you are trying to solve. There's nothing more frustrating than solving a problem only to find out that there was an error in the statement. – Yuval Filmus Mar 23 '19 at 10:41
• Now spend an hour trying to modify your approach to solve your actual question. – Yuval Filmus Mar 23 '19 at 13:22

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.