# simple random walks on undirected graphs

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.

-
@jericson - its not true that if you let the random walker move around for a sufficiently long time and then stop him, he is equally likely to be at any of the vertices. – angela o. Oct 3 '10 at 18:55
Thank you, I was not confident in my reasoning anyways which is why I left it as a comment. It was more for my understanding :) I will remove the above comment since it is inaccurate and does not add to the discussion. – jericson Oct 3 '10 at 19:19

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.
Its natural in this object to consider the edge chain whose states are the directed edges $(i,j)$. When the particle transitions from $i$ to $j$ to $k$, we will say that the edge chain transitioned from the edge $(i,j)$ to $(j,k)$. In retrospect, its obvious this is the right object to look at, but somehow it escaped me as of writing the above post.... – angela o. Oct 3 '10 at 18:53
....anyway, its easy to see the edge chain has the uniform distribution as stationary. Indeed, start the edge chain in the uniform distribution at time $0$, i.e. pick each edge with the same probability $1/|E|$. Whats the probability that edge $(i,j)$ is the next one traversed? Letting $d_i$ denote the degree of node $i$, its $(d_i/E) (1/d_i)=1/E$, so that the uniform distribution is indeed stationary. – angela o. Oct 3 '10 at 18:55