2
$\begingroup$

I have spent a lot of time trying to solve this problem but have had no luck so far! Any help would be highly appreciated!

Suppose I have a 3x3 grid as shown below.

(3,1) (3,2) (3,3)

(2,1) (2,2) (2,3)

(1,1) (1,2) (1,3)

Assume a particle cannot escape the boundaries of the grid. If I initiate a particle in the cell (1,1), it has an equal probability of taking the first step in either direction (1,2) or (2,1). But after it takes the first step, for instance in (2,1) then it cannot take second step back into (1,1) i.e the cell it came from, rather it can then move to either (2,2) or (3,1). If it goes to (2,2), it can either go to (2,3),(1,2) or (3,2). So in a way the movement of the particle is dependent on its current position and also its previous heading direction.

I tried solving it by using a Markov Chain, but if each state is a function of its previous heading and current position, then it becomes a 36 (9 positions x 4 previous headings) state chain and its really hard to analyze the chain.

I am trying to prove that the particle covers the entire grid in a finite amount of time or maybe the probability of reaching every cell is non-zero. Something which shows that the particle will reach every cell.

Thank you and looking forward to any suggestions!

$\endgroup$

1 Answer 1

1
$\begingroup$

This specific problem is not too hard. The theme of the proof is to first show that the path reaches the $(2,2)$ point in finite time almost surely. (That is, although their are paths that circle the perimeter forever, the probability of such a path of infinite length is zero.) Then once you know you will eventually reach the $(2,2)$ point in finite time, the path reaches each of the exterior points in finite time almost surely.

First part: Assume there is a path with finite probability which never visits $(2,2)$. Then at some $t_0$ a path is not at $(2,2)$, and has not come from $(2,2)$. Then the state at $t_0$ is at some exterior point, and has only one choice of direction to leave in other than going to $(2,2)$. Since at each non-corner step there was a $\frac12$ chance of going to $(2,2)$. So the path taken will a.s. leave the non-center path in a finite number of steps.

Second part: The path will a.s. reach a given side point (e.g., $(1,2)$) in a finite number of steps. For we can wait until the path is at the center point, and the path has then either come to will next go to $(1,4)$ with probability $\frac13$. If the path does miss $(1,2)$ then a.s it will arrive at the center point again in a finite number of steps (indeed, since we are satisfied if $(1,2)$ is reached, this finite number of steps is at most $5$ steps), and again there is only a $\frac23$ chance of proceeding without having touched $(1,2)$. So the path will a.s. reash any given side point in a finite number of steps.

Finally, given that the path a.s reaches any side point in a finite number of steps, it will also a.s. reach any corner point in a finite number of steps. For example, consider the corner point $(3,3)$. The path a.s. reaches $(2,3)$ in a finite number of steps, and a path missing $(3,3)$ will have come from either $(2,2)$ or $(1,3)$. In either case there is a $\frac12$ probability of hitting $(3,3)$ on the next move, and if it does not, then we wait until in (a.s.) reaches $(2,3)$ again. As before, this iteration of an indefinite number of choices makes the probability of a path that never reaches $(3,3)$ go to zero.

The above proof, while acceptable, leaves something to be desired, since the property of visiting every point still holds on a larger grid, where the nice feature of having a center point and a group of points equivalent to $C_8$ in a ring around it no longer applies.

$\endgroup$
0

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