# 9.5 An example concerning eigenvalues and mixing times

Here is an example, adapted from Aldous [17]. Let $(\lambda_{u}:1\leq u\leq n)$ be the eigenvalues of ${\bf P}$ with $\lambda_{1}=1$, and let

 $\beta=\max\{|\lambda_{u}|:2\leq u\leq n\}.$

A weak quantification of “mixing” is provided by

 $\alpha(t)\equiv\max_{A,B}|P_{\pi}(X_{0}\in A,X_{t}\in B)-\pi(A)\pi(B)|.$

By definition, $\alpha(t)$ is less than the maximal correlation $\rho(t)$ discussed in Chapter 4 yyy, and so by yyy

 $\alpha(t)\leq\beta^{t}\mbox{ for a reversible chain}.$ (9.22)

The convergence theorem (Chapter 2 yyy) says that $\alpha(t)\rightarrow 0$ as $t\rightarrow\infty$ provided $\beta<1$. So one might expect some analog of (9.22) to hold in general. But this is dramatically false: Example 9.26 shows

###### Lemma 9.25

There exists a family of $n$-state chains, with uniform stationary distributions, such that $\sup_{n}\beta_{n}<1$ while $\inf_{n}\alpha_{n}(n)>0$.

Loosely, this implies there is no reasonable hypothesis on the spectrum of a $n$-state chain which implies an $o(n)$ mixing time. There is a time-asymptotic result

 $\alpha(t)\leq\rho(t)\leq C\beta^{t}\ \forall t,$

for some $C$ 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!

###### Example 9.26

Let $(Y_{t})$ be independent r.v.’s taking values in $\{0,1,\ldots,n-1\}$ with distribution specified by

 $P(Y\leq j)=\frac{j+1}{j+2},\ 0\leq j\leq n-2.$

Define a Markov chain $(X_{t})$ on $\{0,1,\ldots,n-1\}$ by

 $X_{t}=\max(X_{t-1}-1,Y_{t}).$

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 $\sigma$, the distribution of $X_{n-1}$ is uniform, and hence $X_{t}$ is uniform for all $t\geq n-1$. To prove this, we simply observe that for $0\leq j\leq n-1$,

 $\displaystyle P_{\sigma}(X_{n-1}\leq j)$ $\displaystyle=$ $\displaystyle P(Y_{n-1}\leq j,Y_{n-2}\leq j+1,\ldots,Y_{0}\leq j+n-1)$ $\displaystyle=$ $\displaystyle\frac{j+1}{j+2}\times\frac{j+2}{j+3}\times\ldots\times\frac{n-1}{% n}\times\ 1\times\ldots 1$ $\displaystyle=$ $\displaystyle\frac{j+1}{n}.$

If $X_{0}$ is either $0$ or $1$ then $X_{1}$ is distributed as $Y_{1}$, implying that the vector $v$ with $v_{i}=1_{(i=0)}-1_{(i=1)}$ is an eigenvector of ${\bf P}$ with eigenvalue $0$. By soft “duality” arguments it can be shown [17] that this is the largest eigenvalue, in the sense that

 ${\cal R}(\lambda_{u})\leq 0\mbox{ for all }2\leq u\leq n.$ (9.23)

I believe it is true that

 $\beta_{n}=\max\{|\lambda_{u}|:2\leq u\leq n\}$

is bounded away from $1$, but we can avoid proving this by considering the “lazy” chain $\hat{X}_{t}$ with transition matrix $\hat{{\bf P}}=({\bf I}+{\bf P})/2$, for which by (9.23)

 $\hat{\beta}_{n}\leq\sup\{|(1+\lambda)/2|:|\lambda|\leq 1,{\cal R}(\lambda)\leq 0% \}=\sqrt{1/2}.$

So the family of lazy chains has the eigenvalue property asserted in Lemma 9.25. But by construction, $X_{t}\geq X_{0}-t$, and so $P(X_{0}>3n/4,X_{n/2}. For the lazy chains we get

 $P_{\pi}(X_{0}>3n/4,X_{n}

establishing the (non)-mixing property asserted in the lemma.