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