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
Let be an -orthornormal system of eigenvectors for . Now fix an initial distribution and write,
Then we have,
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.