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!