Probability of random walk in a specific point - 2D Random Walk -

Question

I've written a simulation in matlab of a 2-D random walk that, at any point, has an equal probability of going to any of the adjacent points. The simulation was run for 10,000 steps on a grid with dimensions 5x5, with the 'walker' starting at point (0,0). The number of times a specific point was reached is divided by he number of steps to determine the probability that the random walk is in that state. I noticed that this probability, for any point, is approximately the same. The probability for any point only changes depending on the size of the grid. Why?

Answer 1

Let $L_d = \{1, ..., d\}^2$ be the domain of the random walk. I assume that when OP says

a 2-D random walk that, at any point, has an equal probability of going to any of the adjacent points

they mean that at the boundaries, any "accessible" point is selected with equal probability. Thus, at the point $x = (1, 3)$ and $d = 5$, the points $(1, 2), (1, 4), (2, 3)$ exhaust all the next possible states, each with probability 1/3.

This Markov chain is irreducible and aperiodic on a finite state space, hence ergodic with unique stationary distribution $\pi$. In general, the transition kernel of a finite-state Markov chain can be encoded via a matrix $P$ called the transition matrix. The stationary distribution is then the row vector which satisfies $\pi^T P = \pi^T$ (here the superscript $T$ denotes a transpose). In this case, $P$ would be a $d^2\times d^2$ matrix. You can read more about stationary distributions of Markov chains anywhere you like with Google.

Owing to the asymmetry of the proposal distribution of the Markov chain at the boundary, the stationary distribution will not be uniform. You can see this by running more samples. I ran with $10^6$. Below is a heat map of the probabilities.

Finally, you ask "why" would this be so. If you started from a random location on the grid and ran 1000 steps of the random walk, do you think you could identify with high confidence where you started? No. Each state that's not on the boundary eventually experiences similar "inflow" and "outflow", regardless of where the chain started, so the eventual frequency of visits should be equal for all such states.