In the spirit of Chapter 2, this is an unsystematic treatment of scattered topics which are related to topics discussed for reversible chains, but where reversibility plays no essential role. Section 9.1 treats constructions of stopping times with various optimality properties. Section 9.2 discusses random spanning trees associated with Markov chains, the probabilistic elaboration of “the matrix-tree theorem”. Section 9.3 discusses self-verifying algorithms for sampling from a stationary distribution. Section 9.4 discusses “reversiblizations” of irreversible chains. Section 9.5 gives an example to show that the nonasymptotic interpretation of relaxation time, so useful in the reversible setting, may fail completely in the general case. At first sight these topics may seem entirely unrelated, but we shall see a few subtle connections.

Throughout the chapter, our setting is a finite irreducible discrete-time Markov chain $(X_{n})$ with transition matrix ${\bf P}=(p_{ij})$.

- 9.1 Minimal constructions and mixing times
- 9.2 Markov chains and spanning trees
- 9.3 Self-verifying algorithms for sampling from a stationary distribution
- 9.4 Making reversible chains from irreversible chains
- 9.5 An example concerning eigenvalues and mixing times
- 9.6 Miscellany
- 9.7 Notes on Chapter 9

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