Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks, Jim. The more I thought about your answer, the more sense it makes. Here is a slight rephrasing of it.... –  angela o. Oct 3 '10 at 18:52
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.