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.
In this lecture, we generalized our setting to weighted graphs where is a positive weight function on edges. We also looked at the basic spectral theory of the normalized Laplacian, defined by
which operates on functions via
In particular, we associated with the normalized Rayleigh quotient,
and we showed that we can express the second-smallest eigenvalue as
We defined the expansion of a subset by
where is the characteristic function for .
Finally, we defined the expansion of a graph by
We then stated and (almost) proved the following discrete Cheeger inequality.
Theorem 1. For any weighted graph , we have
- Prove that for the normalized Laplacian, just as for the combinatorial Laplacian, the number of connected components in a graph G is precisely the multiplicity of the smallest eigenvalue.
- We saw the the right-hand inequality in Theorem 1 is asymptotically tight. Prove that the left-hand side is asymptotically tight for the complete graph on n nodes.
Today we started studying the spectrum of the combinatorial Laplacian on a graph . This is the operator given by
We saw that has a spectrum of the form , and that the number of connected components in is precisely the multiplicity of .
I encourage you to look at the first four lectures of Spielman’s course for a refresher.
The best way to learn a subject is to get your hands dirty. Here are some optional exercises to help build your intuition.
Recall that for a function , we define its Rayleigh quotient by
If is the path graph on n vertices, then as we argued today, we have .
- Prove that by showing that (a) there exists a map with and and (b) for any such map with , we have . We did this in class, but it will help to reconstruct the proof on your own.
- Try to prove that by exhibiting an explicit subspace of test functions
that achieves this bound. It may help to use the Courant-Fischer min-max principle
which says that
where the minimum is over all k-dimensional subspaces .
[Hint: Have your subspace be the span of k functions with disjoint supports, where the support of a function is .]