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
where
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
where
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
— Q.E.D.
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.
— Q.E.D.
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
— Q.E.D.
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
The proof that the top eigenspace is indeed one-dimensional uses a bit of a deus ex machina, namely the Perron-Frobenius theorem. Look up this theorem, and complete the proof!
— Q.E.D.