366 INDEX of Markov chains, 64 of random variables, 49, 189 optimal, 50, 190 coupon collector, 22, 68, 81, 94, 145 cover time, 143 current flow, 117 cutoff, 247 open problems, 300 window, 248 cutset edge, 122 cycle biased random walk on, 15 Ising model on mixing time pre-cutoff, 204, 214 random walk on, 6, 9, 18, 28, 34, 78 bottleneck ratio, 177 coupling upper bound, 65 cover time, 143, 152 eigenvalues and eigenfunctions, 156 hitting time upper bound, 137 last vertex visited, 84 lower bound, 96 no cutoff, 253 relaxation time, 157 strong stationary time upper bound, 82, 84 cycle law, 118 cycle notation, 100 cyclic-to-random shuffle, 112 degree of vertex, 9 density function, 304 depth (of tree), 68 descendant (in tree), 91 detailed balance equations, 14 diameter, 87, 189 diameter lower bound, 87 dimer system, 319 Dirichlet form, 175 distinguishing statistic, 92 distribution function, 304 divergence of flow, 117 Dominated Convergence Theorem, 307 domino tiling, 319 Doob h-transform, 241 Doob decomposition, 245 Durrett chain comparison upper bound, 224 distinguishing statistic lower bound, 222 East model, 301 lower bound, 97 edge cutset, 122 edge measure, 88 effective conductance, 118 effective resistance, 118 gluing nodes, 120, 122 of grid graph, 123 of tree, 120 Parallel Law, 119 Series Law, 119 triangle inequality, 125, 131 Ehrenfest urn, 24, 34, 251 eigenvalues of transition matrix, 153, 167 empty graph, 98 energy of flow, 121 of Ising configuration, 43 ergodic theorem, 58 escape probability, 119 essential state, 16 even permutation, 100 event, 303 evolving-set process, 235 expander graph, 185 Ising model on, 213 expectation, 304 Fibonacci numbers, 199 FIFO queue, 286 “fifteen” puzzle, 109 first return time, 11, 127 flow, 117 fpras, 196 fugacity, 42 fully polynomial randomized approximation scheme, 196 gambler’s ruin, 21, 34, 124, 233 Gaussian elimination chain, 301 generating function, 136 generating set, 28 Gibbs distribution, 43 Gibbs sampler, 40 Glauber dynamics definition, 41 for colorings, 40, 301 path coupling upper bound, 193 for hardcore model, 43, 73 coupling from the past, 294 relaxation time, 172 for Ising model, 43, 179, 201 coupling from the past, 289 for product measure, 161 glued graphs, 138 complete, 80 lower bound, 84 strong stationary time upper bound, 81 hypercube hitting time upper bound, 139 strong stationary time, 141 torus bottleneck ratio lower bound, 90 hitting time upper bound, 127, 139 gluing (in networks), 120, 122

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.