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.

From Wikipedia:

the conductance of a graph G=(V,E) measures how "well-knit" the graph is: it controls how fast a random walk on G converges to a uniform distribution.

I was wondering why a random walk on a graph G converges to a uniform distribution? Any references on this?

Thanks!

share|improve this question

2 Answers 2

up vote 11 down vote accepted

It doesn't, in general. That article needs correction.

A random walk starting at any vertex will (assuming G is connected and [as Nate pointed out] gives an aperiodic walk) converge to the stationary distribution, which is given by the values of the left eigenvector associated with the first eigenvalue of the transition matrix. This depends on both the connections in the graph and the probabilities, at any vertex, with which you will move to each of its neighbors.

The stationary distribution will be uniform if, for example, the graph is regular (all vertices have the same degree) and at each step you choose one of the neighboring nodes with equal probability, since then the left eigenvector is proportional to $\mathbf{1} = (1,1,\dotsc,1)$.

share|improve this answer
3  
As in Alex's answer, you also need aperiodicity for this to work. –  Nate Eldredge Dec 1 '12 at 20:34

A random walk on a graph $G$ with vertices $\{1,2,\ldots,n\}$ has transition matrix $P(i,j)=\frac{n_{ij}}{d_i}$ where $n_{ij}$ is 1 for $i,j$ being neighbors and 0 otherwise and $d_i$ is the degree of $i$. This transition matrix is reversible with respect to the measure $\pi(i)=\frac{d_i}{\sum_i d_i}=\frac{d_i}{2m}$, where $m$ is the number of edges:

$\pi(i)P(i,j)=\pi(j)P(j,i)$.

This easily implies $\pi$ is a stationary measure of the Markov chain: $\pi P= \pi$, in that $\sum_i \pi(i)P(i,j)=\sum_i\pi(j)P(j,i)=\pi(j)$. Assuming the Markov chain is both irreducible and aperiodic, this implies we have convergence to the stationary distribution. Note that it is not quite "uniform" in that not all points are equally likely, rather each point is as likely as it's degree.

share|improve this answer
1  
Thanks! (1) I wonder why $\sum_i d_i = 2n$? It seems require there are $n$ edges in $G$, where $n$ is the number of vertices in $G$. (2) Why is a random walk on a graph $G$ is irreducible and aperiodic? Being irreducible seems equivalent to require $G$ to be connected, and being aperiodic seems also require some extra conditions? –  Tim Dec 1 '12 at 13:24
2  
@Tim Your concern (1) is probably a notation problem--Alex probably indented $\sum d_i = 2m$ where $m$ is the number of edges, or some such. It is not correct as written. In addition, the random walk is, as you noted, only irreducible if the graph is connected (and with some conditions on the transition probabilities, too), and not all random walks on graphs are aperiodic (an easy counterexample is bipartite graphs, on which random walks always have period two). –  Jonathan Christensen Dec 1 '12 at 16:12
    
@JonathanChristensen: whoops thanks for the correction –  Alex R. Dec 1 '12 at 19:15
    
@Alex: Thanks for the correction. Why is a random walk on a graph G irreducible and aperiodic? Being irreducible seems equivalent to require G to be connected, and being aperiodic seems also require some extra conditions? –  Tim Dec 1 '12 at 19:39
1  
@Tim: I believe the walk is aperiodic if and only if every component contains an odd cycle (or a loop, which you can consider as a 1-cycle). –  Nate Eldredge Dec 1 '12 at 20:38

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.