In Lecture 5, we worked out the Markov limit theorem which says that simple random walk on a connected, non-bipartite graph will converge to the stationary distribution on its vertices in the large time limit. This is an important general result, but it gives no understanding of how quickly this convergence occurs. Let us try to do this for the complete graph on

Intuitively, because is so highly connected, we expect convergence of simple random walk on this graph to the stationary measure to be very rapid. Indeed, at time a particle located at vertex at time which performs simple random has equal probability of being at any vertex except where it cannot be:

This seems close to the stationary distribution for simple random walk on which according to the Markov limit theorem is uniform distribution

on except for the aberration However, this aberration continues indefinitely: there cannot be any finite time such that

because the particle has zero probability of being located at vertex conditional on the event that it was located at vertex at time and this event has positive probability. So, what really do we mean by “ gets close to fast?”

**Definition 1:** If are probability measures on their total variation distance is

This is quite an intuitive notion: the total variation distance simply sums up the discrepancy between and over all points, giving a quantitative meaning to the total discrepancy between these measures. In particular, the maximum total variation occurs when places all its mass at a single point, and places all its mass at a single different point; we then have

We now have a clearly defined objective: estimate the total variation distance between the distribution of simple random walk on at time , and its stationary (uniform) distribution. Following the same pedagogical template as in our first few lectures, let us emphasize that this can be done in a completely elementary way, since we were able to obtain explicit formulas for counting walks on just by being clever. Back in Lecture 1, we showed that the number of step loops on based at any vertex is

Now, since is -regular, the total number of -step walks departing from is and consequently the probability that simple random walk on returns to its starting point at time is

from which we see directly that

exactly as the Markov limit theorem predicts. But actually, since we have simple explicit formulas, we can see more, namely we have the error estimate

which is actually an identity (the best kind of estimate). As for the number of -step walks from to this is given by the complementary formula

whence

So again we immediately obtain the limit

along with the discrepancy formula

All told, our maneuvering above comes down to the exact formula

for the total variation distance between the distribution of simple random walk on at time and the uniform distribution, which is its limit. Thus we know not just that converges to but exactly how fast, as an explicit function both of spatial parameter and the time parameter

Now let us reproduce the above formulas algebraically. We form the Hilbert space with orthonormal basis labeled by the vertices of . From this point of view, a probability measure on is replaced with the vector defined by

Note that even though is probability measure on is *not* a unit vector with respect to the Hilbert space norm (or ) norm,

Rather, it is a unit vector with respect to the -norm, which is defined by

and it is this norm that corresponds to the total variation distance: for probability measures on with corresponding probability vectors we have

So, we would like to compute where

is the probability vector corresponding to the distribution of simple random walk on at time and

is the probability vector corresponding to the uniform distribution.

The adjacency operator is defined by its action in the vertex basis,

and since is -regular the transition operator for simple random walk on is just By inspection, we have

so that is an eigenvector of with eigenvalue Let be the line in spanned by Since is selfadjoint, is an invariant subspace of and in fact, as you saw in last week’s problem set, acts in as multiplication by Thus, the adjacency operator decomposes as

where are the orthogonal projections of onto the complementary subspaces and respectively. We thus have

and hence

We now have the formula

so it remains only to compute in order to get the total variation distance we seek. Now this is just

where is the orthogonal projection of onto and is the orthogonal projection of onto By basic linear algebra,

and hence for the complementary projection we have

This allows to explicitly compute the -norm of though I have to admit I stopped short of doing the required simplifications to check that we get the same formulas as by the barehands method, up to a factor of

**Problem 6.1:** Analyze simple random walk on the graph obtained by adding a loop at each vertex of This is exactly the same thing as “lazy” simple random walk on where the particle can either jump to an adjacent vertex or stay put.

The main message of this lecture is the following. We would like to analyze random walk on the Cayley graph of the symmetric group as generated by the conjugacy class of transpositions. Of course, being a Cayley graph, this is a regular graph and hence the Markov limit theorem tells us that the distribution of the walk tends to uniform in the long-time limit. But in real world terms, this is just the statement that “after infinitely many shuffles, a deck of cards is randomized,” and now it is clear that this is not a useful statement: what we really want to be able to calculate is the total variation distance between the distribution of the walk at time and uniform. This will allow us to quantitatively state how many shuffles are required to get within a stipulated distance of the uniform measure. This endeavor will require everything you learned in Math 202B, and will (hopefully) help to elucidate that material. In the next lecture, we will start down this road by analyzing the same question for some fairly simple abelian subgroups of

## 1 Comment