We continue with our study of random walks on finite graphs via linear algebra. Let be a graph on possibly with loops and/or multiple edges. As in Lecture 4, let denote the probability that simple random walk on starting from vertex is located at vertex at time In this Lecture, we will use the linear algebra setup from Lecture 4 to analyze the asymptotic behavior of the probability which corresponds to the “long time behavior” of simple random walk on
The linear algebraic setup is as follows. Let be a Hilbert space with orthonormal basis indexed by the vertices of In the language of quantum mechanics, by replacing the vertex set of with the Hilbert space we allow ourselves to consider not just vertices, but “superpositions” of vertices. Recall from Lecture 4 that the transition operator for simple random walk on is defined by its action on the vertex basis as
where is the number of edges of incident to both and , and is the total number of edges incident to In Lecture 4, we showed that
so that understanding the asymptotics of the probability is equivalent to understanding the asymptotics of the scalar product We would like to accomplish this via spectral analysis of
We adopt the same assumptions as in Lecture 4: is a connected graph on and so that in particular every vertex has strictly positive degree. Under this assumption, we showed previously that, although need not be selfadjoint, or even normal, the “symmetrize” transition operator is selfadjoint, with being the operator that acts diagonally in the vertex basis according to
We may thus invoke the spectral theorem to assert that
are the distinct eigenvalues of the selfadjoint operator with the orthogonal projection of onto the -eigenspace. Because the ‘s are orthogonal projections, we have
so that for the th power of the transition operator we have the decomposition
So far everything we have said is valid for an arbitrary operator in whose orbit under the conjugation action of contains a selfadjoint operator. To go further we naturally have to reference some of the particular features of the transition operator
Theorem 1: The largest eigenvalue of is
Proof: Let be the -norm on corresponding to the basis , i.e.
We claim that has norm at most in the corresponding operator norm on , i.e.
Indeed, we have
and the terminal double sum is exactly since
It follows that any eigenvalue of has modulus at most
Now we exhibit an eigenvector of with eigenvalue . Consider the vector
is the sum of the degrees of all vertices of which is equal to twice the number of edges in less the number of loops. We then have
The eigenvector above is called the stationary vector for simple random walk on and it encodes the probability measure on the vertices of which assigns mass to vertex Note that, if is a simple graph with constant vertex degree equal to , which is always the case for Cayley graphs corresponding to a symmetric generating set, then the stationary vector
corresponds to uniform probability measure on
It is important to note that Theorem 1 does not preclude the possibility that the smallest eigenvalue of the transition operator could also have maximum modulus — it could well be that However, this can only be the case if is bipartite (perhaps I should fill in a proof of this later, but if I don’t you can find one in any text on spectral graph theory). Therefore, we have the following.
Corollary 1: If is not bipartite, then
where is any norm on
Proof: Let be an arbitrary norm on (indeed, since is finite-dimensional, all norms are equivalent). Then for any we have that
by the triangle inequality. But since and for the statement follows from the squeeze theorem.
At this point we can finally say something about the probability that simple random walk on starting at arrives at at time for a connected non-bipartite graph on vertices, the limit
exists. Note that the role of bipartiteness here is quite clear from a combinatorial perspective: if is bipartite, then with probability one simple random walk started at is located in the color class of at even times, and in the opposite color class at odd times, so that the above limit obviously does not exist.
Continuing on under the assumption that is not-bipartite, let us define a vector by
which encodes the limit distribution of simple random walk on started at
Theorem 2: For any the limit vector is an eigenvector of with eigenvalue
Proof: We have
Theorem (Markov limit theorem): For a connected non-bipartite graph on we have
Proof: The statement follows if we can show that is a simple eigenvalue of , i.e. that the -eigenspace is a line. Indeed, all the vectors as well as have nonnegative coordinates summing to relative to the vertex basis, so if any of these is a scalar multiple of another then the scalar in question must be