INDEX 367 grand coupling, 70, 290, 293 graph, 9 Cayley, 29 colorings, see also colorings complete, 80 connected, 18 degree of vertex, 9 diameter, 87 empty, 98 expander, 185, 213 glued, see also glued graphs grid, 123 ladder, 210 loop, 10 multiple edges, 10 oriented, 117 proper coloring of, 37, see also colorings regular, 11 counting lower bound, 87 simple random walk on, 9 Green’s function, 119, 276 grid graph, 123 Ising model on, 211 group, 27 generating set of, 28 random walk on, 28, 75, 99, 184 symmetric, 75 halting state, 79 Hamming weight, 24 hardcore model, 41 Glauber dynamics for, 43 coupling from the past, 294 grand coupling upper bound, 73 relaxation time, 172 with fugacity, 42, 73 harmonic function, 13, 19, 116, 241 heat bath algorithm, see also Glauber dynamics heat kernel, 265 Hellinger distance, 60, 270, 273 hill climb algorithm, 39 hitting time, 11, 76, 116, 127 cycle identity, 131 upper bound on mixing time, 134 worst case, 128 hypercube, 23 lamplighter chain on, 263 random walk on, 28 2 upper bound, 164 bottleneck ratio, 177 coupling upper bound, 68 cover time, 152 cutoff, 164, 250 distinguishing statistic lower bound, 94 eigenvalues and eigenfunctions of, 162 hitting time, 139 relaxation time, 172 separation cutoff, 254 strong stationary time upper bound, 77, 78, 81 Wilson’s method lower bound, 173 i.i.d., 63 increment distribution, 28 independent, 305 indicator function, 15 induced chain, 180, 284 inessential state, 16 interchange process, 301 inverse distribution, 55, 107 method of simulation, 314 irreducible chain, 8 Ising model, 43, 201 block dynamics, 208, 300 comparison of Glauber and Metropolis, 179 energy, 43 fast mixing at high temperature, 201 Gibbs distribution for, 43 Glauber dynamics for, 43 coupling from the past, 288 infinite temperature, 43 inverse temperature, 43 on complete graph mixing time bounds, 203 on cycle mixing time pre-cutoff, 204, 214 on expander, 213 on grid relaxation time lower bound, 211 on tree, 214 mixing time upper bound, 206 open problems, 299 partial order on configurations, 289 partition function, 43 isoperimetric constant, 98 k-fuzz, 285 Kac lemma, 280 Kirchoff’s node law, 117 p(π) distance, 60, 163 ∞(π) distance, 60 L-reversal chain, see also Durrett chain ladder graph, 210 lamplighter chain, 257, 301 mixing time, 260 on cycle, 262 on hypercube, 263 on torus, 263 relaxation time, 258 separation cutoff, 264 Laws of Large Numbers, 305 lazy version of a Markov chain, 9, 168, 266 leaf, 18, 68 level (of tree), 68

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.