Random walk on a finite square grid: probability of given position after 15 or 3600 moves

Question

An ant is walking on the squares of a 5x5 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).

1. What is the probability that the ant is on the center square after 15 seconds?
2. 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 :-)

Answer 1

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.

Answer 2

Let P[t, (x,y)] be the probability that the ant will be at (x,y) at time t. We can form a recurrence relation as such:

P[t, (x,y)] = 0.2 * [(5-No of neighbours of (x,y)) * P[t-1, (x,y)]] + 0.2 * P[t-1, (a,b)]
where (a,b) is a valid point neighbouring (x,y)

Start with P[0, (3,3)]=1, P[0, (a,b)]=0 for all other points and build the recursion.

Answer 1 = P[15, (3,3)]
Answer 2 = P[3600, (1,1)] + P[3600, (1,5)] + P[3600, (5,1)] + P[3600, (5,5)]

I wrote a crude python program which gives the result. Unless I'm wrong, the answer to Q1 is 0.0412498 and the answer to Q2 is 0.16

You can find the code at https://gist.github.com/humachine/8402f2183d126a8eb486

Answer 3

Roll up the grid into a torus, so that the ant can move from the top to the bottom edge or from the left to the right edge (anybody remember Asteroids?). This doesn't change the probability of it being in one of the 16 (original) edge squares, because staying put in an edge square is the mirror image of crossing to the opposite edge.

There are no distinguished squares on the torus, so the probability of each square tends to $1/25$. Hence the answer to the second question is "very close to $16/25$".

This is different from Did's $4/25$, but only because we interpret "outermost" differently.

Answer 4

I solve the problem with markov chains: Enumerate the grid cells as follows: $$\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & \ldots & \\ \vdots \\\end{matrix}$$

Then you can set up a $25 \times 25$ transition matrix $A$. Each entry of the transitionmatrix denotes the probability of a transition from a certain cell to a certain cell. The entry $A_{ij}$ has the probability of transition from the cell $j$ to the cell $i$. The cells on the border of the grid have that special rule that if you do an 'invalid move' you just stay there. This means just that the transition probability of that cell to itself is being increased by that amount. This results in following matrix:

$$A = \begin{pmatrix} C & S & & & 0 \\ S & M & S & & \\ & S & M & S & \\ & & S & M & S \\ 0 & & & S & C \end{pmatrix}$$ where $$ C = \begin{pmatrix} .6 & .2 & & & 0 \\ .2 & .4& .2 & & \\ & .2 & .4& .2 & \\ & & .2 & .4 & .2 \\ 0 & & & .2 & .6\end{pmatrix} \quad M = \begin{pmatrix} .4 & .2 & & & 0 \\ .2 & .2& .2 & & \\ & .2 & .2& .2 & \\ & & .2 & .2 & .2 \\ 0 & & & .2 & .4\end{pmatrix}$$

$$ S = \begin{pmatrix} .2 & & & & 0 \\ & .2& & & \\ & & .2& & \\ & & & .2 & \\ 0 & & & & .2\end{pmatrix}$$

If we know what to get the probability distribution after $n$ steps we just have to write down the start distribution $v$ and compute $A^n v$.

The start distribution in this case was: $v = (0,\ldots, 0, 1,0,\ldots,0)^t$ where the $1$ is in the 13nth entry. (Which is the center cell according to our enumeration.)

With this concept you can easily answer your questions.

The Matlab/Octave code can be found here and can be executed in any online octave interpreter by removing the plot commands at line 34/35