7
$\begingroup$

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!

2 Answers 2

11

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)$.

  • 3
    As in Alex's answer, you also need aperiodicity for this to work.2012-12-01
7

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.

  • 0
    @Alex: Right. Thanks!2012-12-12