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.

## 2 Comments