Here is an example, adapted from Aldous [17]. Let be the eigenvalues of with , and let
A weak quantification of “mixing” is provided by
By definition, is less than the maximal correlation discussed in Chapter 4 yyy, and so by yyy
(9.22) |
The convergence theorem (Chapter 2 yyy) says that as provided . So one might expect some analog of (9.22) to hold in general. But this is dramatically false: Example 9.26 shows
There exists a family of -state chains, with uniform stationary distributions, such that while .
Loosely, this implies there is no reasonable hypothesis on the spectrum of a -state chain which implies an mixing time. There is a time-asymptotic result
for some depending on the chain. But implicit claims in the literature that bounding the spectrum of a general chain has some consequence for finite-time behavior should be treated with extreme skepticism!
Let be independent r.v.’s taking values in with distribution specified by
Define a Markov chain on by
This chain has the property (cf. the “patterns in coin-tossing” chain) of attaining the stationary distribution in finite time. Precisely: for any initial distribution , the distribution of is uniform, and hence is uniform for all . To prove this, we simply observe that for ,
If is either or then is distributed as , implying that the vector with is an eigenvector of with eigenvalue . By soft “duality” arguments it can be shown [17] that this is the largest eigenvalue, in the sense that
(9.23) |
I believe it is true that
is bounded away from , but we can avoid proving this by considering the “lazy” chain with transition matrix , for which by (9.23)
So the family of lazy chains has the eigenvalue property asserted in Lemma 9.25. But by construction, , and so . For the lazy chains we get
establishing the (non)-mixing property asserted in the lemma.