Remarks on Lecture 3


Today we saw the connection between mixing times of random walks and the second eigenvalue of the normalized Laplacian. Recall that is an -vertex, weighted graph.

First, we introduced the lazy walk matrix,

which is related to the normalized Laplacian via,

In particular, if we arrange the eigenvalues of as , then

where is the th smallest eigenvalue of . Furthermore, the eigenfunctions of are given by , where is an eigenfunction of .

The eigenfunctions of are orthogonal with respect to the inner product

We will refer to this Hilbert space as . Recall that .

If we define the stationary distribution by

then .

Let be an -orthornormal system of eigenvectors for . Now fix an initial distribution and write,

Then we have,

In particular,

Let be the minimum stationary measure. A particularly strongly notion of mixing time is given by the following definition.

where the supremum is taken over all initial distributions . By time , the distribution is pointwise very close to the stationary distribution .

Let and . Using our preceding calculation, we have

Observe that , so if we now choose appropriately, then

yielding our main result:

One can also proof that (see the exercises). In general, we will be concerned with weaker notions of mixing. We’ll discuss those when they arise.


Prove that for any graph G.