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

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!

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}<n/4)=0$. For the lazy chains we get

$P_{\pi}(X_{0}>3n/4,X_{n}<n/4)\rightarrow 0\mbox{ as }n\rightarrow\infty$ |

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

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML