Chapter 9 A Second Look at General Markov Chains (April 21, 1995)

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})$.