0
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ This question is impossible to answer unless you define a probability distribution on your random walk. $\endgroup$
    – Yuval Filmus
    Mar 23, 2019 at 10:36
  • 1
    $\begingroup$ What happens if we have fewer than 4 neighbors? $\endgroup$
    – Yuval Filmus
    Mar 23, 2019 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, 2019 at 10:41
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Mar 23, 2019 at 12:26
  • 1
    $\begingroup$ Now spend an hour trying to modify your approach to solve your actual question. $\endgroup$
    – Yuval Filmus
    Mar 23, 2019 at 13:22

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Are you asking a new question? If so, you should ask it as a new question. $\endgroup$
    – Yuval Filmus
    Mar 23, 2019 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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