2
$\begingroup$

I am simulating two objects on a grid, and checking how long they can run until the two objects meet. The two objects move randomly, and choose any block (up, down, left, right) randomly. If the side the objects randomly selects does not have a block, then the objects goes the other way. I'm generating the probability of the two objects not meeting after some time $t$.

This is a Markov process, and the states are $[1..n*n]$, where $n*n$ is the grid coordinate $(n,n)$. For grid of size two and three, here are the tables:

$\mathbf{Mat} = \begin{bmatrix}0&0.5&0.5&0\\0.5&0&0&0.5\\0.5&0&0&0.5\\0&0.5&0.5&0\end{bmatrix}$

$\mathbf{Mat} = \begin{bmatrix} 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\ 1/4 & 0 & 1/4 & 0 & 1/2 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 \\ 1/4 & 0 & 0 & 0 & 1/2 & 0 & 1/4 & 0 & 0 \\ 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 \\ 0 & 0 & 1/4 & 0 & 1/2 & 0 & 0 & 0 & 1/4 \\ 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 0 & 1/2 & 0 & 1/4 & 0 & 1/4 \\ 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 \end{bmatrix}$

So if an object is initially at $(0,0)$, then it's probability at $t$ of being at any position in the grid can be gotten from $$\mathbf{u} = [1,0,0 \:..\:0].(\mathbf{Mat})^{t}$$

Similarly for the second object, it would be $$\mathbf{v} =[0,0 \:..\:0, 1].(\mathbf{Mat})^{t}$$

So the probability of the two objects not meeting by some time $t$ would be $$P(t)= (1 - \mathbf{u}.\mathbf{v}) * P(t-1)$$

$P(t)$ decreases with time $t$. But is this decrease random for each grid size? Like for grid size 2, $P(t)$ decreases as $[1,0.5,0.25...]$, which exponentially decreases. But for higher sizes, does $P(t)$ vary the same way? Thanks for any suggestion!

Improve this question
$\endgroup$
3
  • $\begingroup$ I bet it will decrease exponentially, roughly as $(1-2/n^2)^k$, where $k$ is the number of steps. This is because after a long period of time, the position of each of the objects becomes almost uniform on black/white squares of the chessboard for even/odd $k$, and roughly independent from whether the objects already met or not. $\endgroup$
    – Mateusz Kwaśnicki
    Commented Sep 17, 2017 at 22:29
  • $\begingroup$ @MateuszKwaśnicki For a 3 row grid, $(1-2/(3)^2)^k$ would give a < 1 value for k < 2. Similarly for all $n\ge3$ $\endgroup$
    – Indo Ubt
    Commented Sep 18, 2017 at 6:45
  • $\begingroup$ @IndoUbt: This is why I wrote "roughly". I do not even claim comparability of $P(k)$ and $(1-2/n^2)^k$ for large $k$. The decay is in fact exponential, of the form $C \lambda^k$, where $\lambda$ is the largest eigenvalue of a killed Markov chain that describes both objects simultaneously (and it is killed when the objects meet). However, I am not sure if this answers the original question. $\endgroup$
    – Mateusz Kwaśnicki
    Commented Sep 18, 2017 at 8:18

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .