Consider a simple random walk on a undirected, connected graph. This is the random walk which, at every time step, moves to a random neighbor, with all neighbors being equally likely. Lets assume every node has a self-loop to avoid issues associated with periodicity. Then, the following (surprising to me) fact is true: under the stationary distribution, every edge is traversed with the same probability.
I'm trying to get some intuition for why this holds, and I am wondering whether someone
can provide an explanation for this phenomenon.
Naturally, I know the standard proof which
observes that $\pi_i = d_{i}/\sum_k d_k$ satisfies the equations for the stationary distribution, and so $\pi_i p_{ij} = 1/\sum_k d_k$ whenever the edge $(i,j)$ is present in the graph. This proof, however, feels more like a lucky calculation to me than an explanation.
Note that the fact in boldface is false for directed graphs. Its also false for the corresponding two-step chain, i.e. the Markov chain with probability transition matrix $P^2$, where $P$ is the transition matrix of the simple random walk.
Best Answer
First, think of each edge as a unit-length path connecting two vertices.
Now, imagine that instead of a random walk on the vertices, we consider a continuous random walk that moves along edges at unit speed. Every time we arrive at a vertex, we randomly decide which edge coming out of the vertex to traverse next. Note that the sequence of vertices and edges that we traverse will be the same as in the discrete-time random walk.
Now imagine that we fill the graph with a very large number of particles, each of which is performing a continuous walk. We start the particles at random times in the interval $[0,1]$, so that each vertex continuously has particles going through it, and then wait until we are in the steady state.
At least for me, it seems obvious at this point that the graph will be uniformly filled with particles, with each edge having the same density. Every vertex will have particles coming in from all of its edges at the same rate, and these particles will randomly distribute themselves among the outgoing edges. This situation is clearly stable, so it must be the steady state.