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.

### Excersies

Prove that for any graph G.