An ant is walking on the squares of a 5×5 grid – it starts in the center square.
Each second, it will choose (with equal probability)
to do one of the following:
- Move north one square
- Move south one square
- Move east one square
- Move west one square
- Do not move
If it cannot perform the action it has decided on (move west while on the
west edge, for example), it sits in place.
After one second, it has a 20% chance of being in the center, and a 20% chance
of being in each adjacent square. (and a 0% chance of being in any
other square on the board).
- What is the probability that the ant is on the center square after 15 seconds?
- What is the probability that the ant is on one of the outermost squares after 1 hour?
Any suggestions? In the first question, I don't know how to enumerate all the possible routes that finish on the middle square after 15 moves and divide them by the total number of possible routes. In the second one, I'm completely lost.
Thanks for your help 🙂
Best Answer
An exact computation to answer question 1. is simple in principle, difficult to do exactly with no computer, and the result is frankly not very interesting. Question 2. is more interesting since, after 3600 steps on a graph of 25 vertices with diameter 10, the random walk is close to its stationary distribution.
The random walk is equivalent to the simple reversible random walk on the augmented graph where one adds 3 supplementary loops to each corner, 2 to each side vertex not a corner, and 1 to each other vertex. Every vertex in the augmented graph has degree 5 hence the stationary distribution is uniform. The Markov chain is aperiodic hence, at any large time, the probability to be at any of the vertices of this graph with 25 vertices is approximately 1/25.
The probability to be in any set S of vertices is approximately the size of S divided by 25. There are 4 corners hence the probability to be at one corner is approximately 4/25. There are 16 side squares hence the probability to be on one side is approximately 16/25.