368 INDEX linear congruential sequence, 319 Lipschitz constant, 171, 198 loop, 10 lower bound methods bottleneck ratio, 88, 89 counting bound, 87 diameter bound, 87 distinguishing statistic, 92 Wilson’s method, 172 lozenge tiling, 290 lumped chain, see also projection Markov chain aperiodic, 8 birth-and-death, 26 communicating classes of, 16 comparison of, see also comparison of Markov chains continuous time, 265 Convergence Theorem, 52, 73 coupling, 64 definition of, 3 ergodic theorem, 58 irreducible, 8 lamplighter, see also lamplighter chain lazy version of, 9 mixing time of, 55 Monte Carlo method, 37, 287 null recurrent, 280 periodic, 8, 167 positive recurrent, 280 product, see also product chain projection of, 24, 34 random mapping representation of, 7, 70 recurrent, 277 reversible, 15, 116 stationary distribution of, 10 time averages, 165 time reversal of, 15, 34 time-inhomogeneous, 20, 112, 191 transient, 277 transitive, 29, 34 unknown, 296 Markov property, 3 Markov’s inequality, 305 Markovian coupling, 65, 74 martingale, 229 Matthews method lower bound on cover time, 146 upper bound on cover time, 144 maximum principle, 19, 116 MCMC, see also Markov chain Monte Carlo method metric space, 189, 308 Metropolis algorithm, 37 arbitrary base chain, 39 for colorings, 70, 171 for Ising model, 179 symmetric base chain, 37 mixing time, 55 2 upper bound, 163 Cesaro, 83, 140 continuous time, 266 coupling upper bound, 65 hitting time upper bound, 134 path coupling upper bound, 192 relaxation time lower bound, 155 relaxation time upper bound, 155 Monotone Convergence Theorem, 307 Monte Carlo method, 37, 287 move-to-front chain, 81 Nash-Williams inequality, 122, 278 network, 115 infinite, 277 node, 115 node law, 117 null recurrent, 280 odd permutation, 100 Ohm’s law, 118 optimal coupling, 50, 190 Optional Stopping Theorem, 232 order statistic, 323 oriented edge, 117 Parallel Law, 119 parity (of permutation), 100 partition function, 43 path, 191 metric, 191 random walk on, 63, see also birth-and-death chain, see also gambler’s ruin, 120, 248 eigenvalues and eigenfunctions, 158, 159 path coupling, 189 upper bound on mixing time, 192, 201 patterns in coin tossing cover time, 148 hitting time, 139, 234 perfect sampling, see also sampling, exact periodic chain, 8 eigenvalues of, 167 pivot chain for self-avoiding walk, 320 P´ olya’s urn, 25, 124, 124, 133 positive recurrent, 279 pre-cutoff, 248, 255 mixing time of Ising model on cycle, 204, 214 previsible sequence, 231 probability distribution, 304 measure, 303 space, 303 product chain

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.