Reversible Markov Chains and Random Walks on Graphs

Chapter 2 General Markov Chains (September 10, 1999)

The setting of this Chapter is a finite-state irreducible Markov chain (Xt)(X_{t}), either in discrete time (t=0,1,2,)(t=0,1,2,\ldots) or in continuous time (0t<)(0\leq t<\infty). Highlights of the elementary theory of general (i.e. not-necessarily-reversible) Markov chains are readily available in several dedicated textbooks and in chapters of numerous texts on introductory probability or stochastic processes (see the Notes), so we just give a rapid review in sections 2.1 and 2.1.2. Subsequent sections emphasize several specific topics which are useful for our purposes but not easy to find in any one textbook: using the fundamental matrix in mean hitting times and the central limit theorem, metrics on distributions and submultiplicativity, Matthews’ method for cover times, and martingale methods.