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

  • 1
    $\begingroup$ This question is impossible to answer unless you define a probability distribution on your random walk. $\endgroup$ – Yuval Filmus Mar 23 '19 at 10:36
  • $\begingroup$ we can move to any of the 4 neighbours with equal probability. $\endgroup$ – Manoharsinh Rana Mar 23 '19 at 10:37
  • 1
    $\begingroup$ What happens if we have fewer than 4 neighbors? $\endgroup$ – Yuval Filmus Mar 23 '19 at 10:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 23 '19 at 10:41
  • 1
    $\begingroup$ Now spend an hour trying to modify your approach to solve your actual question. $\endgroup$ – 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.

  • $\begingroup$ geeksforgeeks.org/a-matrix-probability-question I did this (additionally used dynamic programming) I have P[a][b][t] matrix.How can I find the probability for atmost k steps. Certainly, I can not sum the probability for P[ i ][ j ] [ t ] ,t≤k. $\endgroup$ – Manoharsinh Rana Mar 23 '19 at 18:50
  • $\begingroup$ Are you asking a new question? If so, you should ask it as a new question. $\endgroup$ – Yuval Filmus Mar 23 '19 at 19:26
  • $\begingroup$ it is the same question.But I did not understand the solution. $\endgroup$ – Manoharsinh Rana Mar 23 '19 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.