FOR THE READER xiii Chapter 13 covers advanced spectral techniques, including comparison of Dirich- let forms and Wilson’s method for lower bounding mixing. Chapters 14 and 15 cover some of the most important families of “large” chains studied in computer science and statistical mechanics and some of the most impor- tant methods used in their analysis. Chapter 14 introduces the path coupling method, which is useful in both sampling and approximate counting. Chapter 15 looks at the Ising model on several different graphs, both above and below the critical temperature. Chapter 16 revisits shuffling, looking at two examples—one with an application to genomics—whose analysis requires the spectral techniques of Chapter 13. Chapter 17 begins with a brief introduction to martingales and then presents some applications of the evolving sets process. Chapter 18 considers the cutoff phenomenon. For many families of chains where we can prove sharp upper and lower bounds on mixing time, the distance from stationarity drops from near 1 to near 0 over an interval asymptotically smaller than the mixing time. Understanding why cutoff is so common for families of interest is a central question. Chapter 19, on lamplighter chains, brings together methods presented through- out the book. There are many bounds relating parameters of lamplighter chains to parameters of the original chain: for example, the mixing time of a lamplighter chain is of the same order as the cover time of the base chain. Chapters 20 and 21 introduce two well-studied variants on finite discrete time Markov chains: continuous time chains and chains with countable state spaces. In both cases we draw connections with aspects of the mixing behavior of finite discrete-time Markov chains. Chapter 22, written by Propp and Wilson, describes the remarkable construc- tion of coupling from the past, which can provide exact samples from the stationary distribution. Chapter 23 closes the book with a list of open problems connected to material covered in the book. For the Reader Starred sections contain material that either digresses from the main subject matter of the book or is more sophisticated than what precedes them and may be omitted. Exercises are found at the ends of chapters. Some (especially those whose results are applied in the text) have solutions at the back of the book. We of course encourage you to try them yourself first! The Notes at the ends of chapters include references to original papers, sugges- tions for further reading, and occasionally “complements.” These generally contain related material not required elsewhere in the book—sharper versions of lemmas or results that require somewhat greater prerequisites. The Notation Index at the end of the book lists many recurring symbols. Much of the book is organized by method, rather than by example. The reader may notice that, in the course of illustrating techniques, we return again and again to certain families of chains—random walks on tori and hypercubes, simple card shuffles, proper colorings of graphs. In our defense we offer an anecdote.
Previous Page Next Page