Index Italics indicate that the reference is to an exercise. absolute spectral gap, 154 absorbing state, 16 acceptance-rejection sampling, 314 adapted sequence, 229 alternating group, 100, 109 aperiodic chain, 8 approximate counting, 196 averaging over paths, 183, 225 ballot theorem, 33 binary tree, 68 Ising model on, 206 random walk on bottleneck ratio lower bound, 91 commute time, 132 coupling upper bound, 69 cover time, 147 hitting time, 139 no cutoff, 253 birth-and-death chain, 26, 245, 282 stationary distribution, 26 block dynamics for Ising model, 208, 300 bottleneck ratio, 88, 89 bounds on relaxation time, 177 lower bound on mixing time, 88 boundary, 88 Bounded Convergence Theorem, 307 Catalan number, 32 Cayley graph, 29 Central Limit Theorem, 306 Cesaro mixing time, 83, 140 CFTP, see also coupling from the past Chebyshev’s inequality, 305 Cheeger constant, 98 children (in tree), 68 coin tossing patterns, see also patterns in coin tossing colorings, 37 approximate counting of, 196 Glauber dynamics for, 40, 301 exponential lower bound on star, 90 lower bound on empty graph, 98 path coupling upper bound, 193 Metropolis dynamics for grand coupling upper bound, 70 relaxation time, 171 communicating classes, 16 commute time, 69, 130 Identity, 130 comparison of Markov chains, 179 canonical paths, 182 on groups, 184 randomized paths, 183 theorem, 182, 209, 217, 224 complete graph, 80 Ising model on, 203 lamplighter chain on, 262 conductance, 115 bottleneck ratio, 98 configuration, 40 congestion ratio, 182, 183 connected graph, 18 connective constant, 211 continuous-time chain, 265 Convergence Theorem, 266 product chains, 269 relation to lazy chain, 266 relaxation time, 268 Convergence Theorem, 52 continuous time, 266 coupling proof, 73 null recurrent chain, 283 positive recurrent chain, 281 convolution, 136, 140 counting lower bound, 87 coupling bound on d(t), 65 characterization of total variation distance, 50 from the past, 287 grand, 70, 290, 293 Markovian, 65, 74 of distributions, 49, 50, 189 365

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.