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)$ certainly 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!

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!

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)$ certainly decreases with time $t$. But is this decrease just 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/can $P(t)$ vary the same way? Thanks for any suggestion!

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)$ certainly 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!