# Math 202C: Lecture 5

We continue with our study of random walks on finite graphs via linear algebra. Let $\mathrm{G}$ be a graph on $\{1,\dots,n\},$ possibly with loops and/or multiple edges. As in Lecture 4, let $P^r(i,j)$ denote the probability that simple random walk on $\mathrm{G}$ starting from vertex $i$ is located at vertex $j$ at time $r.$ In this Lecture, we will use the linear algebra setup from Lecture 4 to analyze the $r \to \infty$ asymptotic behavior of the probability $P^r(i,j),$ which corresponds to the “long time behavior” of simple random walk on $\mathrm{G}.$

The linear algebraic setup is as follows. Let $\mathcal{H}$ be a Hilbert space with orthonormal basis $\{\mathbf{e}_1,\dots,\mathbf{e}_n\}$ indexed by the vertices of $\mathrm{G}.$ In the language of quantum mechanics, by replacing the vertex set of $\mathrm{G}$ with the Hilbert space $\mathcal{H}$ we allow ourselves to consider not just vertices, but “superpositions” of vertices. Recall from Lecture 4 that the transition operator $T \in \mathrm{End}\mathcal{H}$ for simple random walk on $\mathrm{G}$ is defined by its action on the vertex basis as

$T\mathbf{e}_i = \sum\limits_{j=1}^n \frac{m_{ij}}{d_i} \mathbf{e}_j,$

where $m_{ij}$ is the number of edges of $\mathrm{G}$ incident to both $i$ and $j$, and $d_i=\sum_{j=1}^n m_{ij}$ is the total number of edges incident to $i.$ In Lecture 4, we showed that

$P^r(i,j) = \langle T^r\mathbf{e}_i,\mathbf{e}_j \rangle,$

so that understanding the $r \to \infty$ asymptotics of the probability $P^r(i,j)$ is equivalent to understanding the $r \to \infty$ asymptotics of the scalar product $\langle T^r\mathbf{e}_i,\mathbf{e}_j \rangle.$ We would like to accomplish this via spectral analysis of $T.$

We adopt the same assumptions as in Lecture 4: $\mathrm{G}$ is a connected graph on $\{1,\dots,n\}$ and $n \geq 2,$ so that in particular every vertex has strictly positive degree. Under this assumption, we showed previously that, although $T$ need not be selfadjoint, or even normal, the “symmetrize” transition operator $D^{-1}TD$ is selfadjoint, with $D \in \mathrm{GL}(\mathcal{H})$ being the operator that acts diagonally in the vertex basis according to

$D\mathbf{e}_j = \sqrt{d_j}\mathbf{e}_j.$

We may thus invoke the spectral theorem to assert that

$D^{-1}TD = \lambda_1P_1 + \dots + \lambda_mP_m,$

where

$\lambda_1 >\dots > \lambda_m,$

are the distinct eigenvalues of the selfadjoint operator $D^{-1}TD,$ with $P_i \in \mathrm{End}\mathcal{H}$ the orthogonal projection of $\mathcal{H}$ onto the $\lambda_i$-eigenspace. Because the $P_i$‘s are orthogonal projections, we have

$D^{-1}T^rD = \lambda_1^rP_1 + \dots + \lambda_m^rP_m,$

so that for the $r$th power of the transition operator we have the decomposition

$T^r = \lambda_1^r DP_1D^{-1} + \dots + \lambda_m^r DP_mD^{-1}.$

So far everything we have said is valid for an arbitrary operator in $\mathrm{End}\mathcal{H}$ whose orbit under the conjugation action of $\mathrm{GL}(\mathcal{H})$ contains a selfadjoint operator. To go further we naturally have to reference some of the particular features of the transition operator $T.$

Theorem 1: The largest eigenvalue of $T$ is $\lambda_1=1.$

Proof: Let $\|\cdot\|_1$ be the $1$-norm on $\mathcal{H}$ corresponding to the basis $\mathbf{e}_1,\dots,\mathbf{e}_n$, i.e.

$\|\mathbf{v}\|_1 = \sum\limits_{j=1}^n |\langle \mathbf{v},\mathbf{e}_j \rangle|.$

We claim that $T$ has norm at most $1$ in the corresponding operator norm on $\mathrm{End}\mathcal{H}$, i.e.

$\|T\mathbf{v}\|_1 \leq \|\mathbf{v}\|_1 \quad \forall \mathbf{v} \in \mathcal{H}.$

Indeed, we have

$\|T\mathbf{v}\|_1 = \sum\limits_{j=1}^n |\langle S\mathbf{v},\mathbf{e}_j\rangle| = \sum\limits_{j=1}^n \left| \left\langle \sum\limits_{i=1}^n \langle \mathbf{e}_i,\mathbf{v}\rangle T\mathbf{e}_i,\mathbf{e}_j \right\rangle \right| \leq \sum\limits_{i=1}^n|\langle \mathbf{v},\mathbf{e}_i\rangle|\sum\limits_{j=1}^n |\langle T\mathbf{e}_i,\mathbf{e}_j\rangle|,$

and the terminal double sum is exactly $\|\mathbf{v}\|_1,$ since

$\sum\limits_{j=1}^n \langle T\mathbf{e}_i,\mathbf{e}_j \rangle = \sum\limits_{j=1}^n \frac{m_{ij}}{d_i} = \frac{d_i}{d_i}=1.$

It follows that any eigenvalue of $T$ has modulus at most $1.$

Now we exhibit an eigenvector of $T$ with eigenvalue $1$. Consider the vector

$\mathbf{s} = \sum\limits_{i=1}^n \frac{d_i}{D}\mathbf{e}_i,$

where

$D=\sum\limits_{i=1}^n d_i$

is the sum of the degrees of all vertices of $\mathrm{G},$ which is equal to twice the number of edges in $\mathrm{G}$ less the number of loops. We then have

$T\mathbf{s} = \sum\limits_{i=1}^n \frac{d_i}{D}T\mathbf{e}_i = \sum\limits_{i=1}^n \frac{d_i}{D}\sum\limits_{j=1}^n \frac{m_{ij}}{d_i} \mathbf{e}_j = \sum\limits_{j=1}^n \frac{d_j}{D}\mathbf{e}_j = \mathbf{s}.$

— Q.E.D.

The eigenvector $\mathbf{s}$ above is called the stationary vector for simple random walk on $\mathrm{G},$ and it encodes the probability measure on the vertices of $\mathrm{G}$ which assigns mass $\frac{d_i}{D}$ to vertex $i.$ Note that, if $\mathrm{G}$ is a simple graph with constant vertex degree equal to $d$, which is always the case for Cayley graphs corresponding to a symmetric generating set, then the stationary vector

$\mathbf{s} = \sum\limits_{i=1}^n \frac{d}{dn}\mathbf{e}_i = \sum\limits_{i=1}^n \frac{1}{n}\mathbf{e}_i$

corresponds to uniform probability measure on $\{1,\dots,n\}.$

It is important to note that Theorem 1 does not preclude the possibility that the smallest eigenvalue of the transition operator $T$ could also have maximum modulus — it could well be that $\lambda_m=-1.$ However, this can only be the case if $\mathrm{G}$ 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 $\mathrm{G}$ is not bipartite, then

$\lim\limits_{r \to \infty} \|T^r-DP_1D^{-1}\| = 0,$

where $\|\cdot\|$ is any norm on $\mathrm{End}\mathcal{H}.$

Proof: Let $\|\cdot\|$ be an arbitrary norm on $\mathrm{End}\mathcal{H}$ (indeed, since $\mathrm{End}\mathcal{H}\}$ is finite-dimensional, all norms are equivalent). Then for any $r$ we have that

$\|T^r-\lambda_1DP_1D^{-1}\| \leq \sum\limits_{i=2}^m |\lambda_i|^r \|DP_iD^{-1}\|,$

by the triangle inequality. But since $\lambda_1=1$ and $|\lambda_i|<1$ for $i > 1,$ the statement follows from the squeeze theorem.

— Q.E.D.

At this point we can finally say something about the probability $P^r(i,j) = \langle T^r\mathbf{e}_i,\mathbf{e}_j \rangle$ that simple random walk on $\mathrm{G}$ starting at $i$ arrives at $j$ at time $r:$ for $\mathrm{G}$ a connected non-bipartite graph on $n \geq 2$ vertices, the limit

$t(i,j) = \lim\limits_{r \to \infty} P^r(i,j)$

exists. Note that the role of bipartiteness here is quite clear from a combinatorial perspective: if $\mathrm{G}$ is bipartite, then with probability one simple random walk started at $i$ is located in the color class of $i$ 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 $\mathrm{G}$ is not-bipartite, let us define a vector $\mathbf{t}_i \in \mathcal{H}$ by

$\mathbf{t}_i = \sum\limits_{j=1}^n t(i,j) \mathbf{e}_j,$

which encodes the limit distribution of simple random walk on $\mathrm{G}$ started at $i.$

Theorem 2: For any $1 \leq i \leq n,$ the limit vector $\mathbf{t}_i$ is an eigenvector of $T$ with eigenvalue $1.$

Proof: We have

$T\mathbf{t}_i = T\lim\limits_{r \to \infty} T^r \mathbf{e}_i = \lim\limits_{r \to \infty} T^{r+1} \mathbf{e}_i = \mathbf{t}_i.$

— Q.E.D.

Theorem (Markov limit theorem): For $\mathrm{G}$ a connected non-bipartite graph on $\{1,\dots,n\},$ $n \geq 2,$ we have

$\mathbf{t}_1=\mathbf{t}_2=\dots = \mathbf{t}_n = \mathbf{s}.$

Proof: The statement follows if we can show that $\lambda_1=1$ is a simple eigenvalue of $T$, i.e. that the $\lambda_1$-eigenspace is a line. Indeed, all the vectors $\mathbf{t}_i$ as well as $\mathbf{s}$ have nonnegative coordinates summing to $1$ relative to the vertex basis, so if any of these is a scalar multiple of another then the scalar in question must be $1.$

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.