INDEX 369 eigenvalues and eigenfunctions of, 160, 168 in continuous time, 269 spectral gap, 161 Wilson’s method lower bound, 175 projection, 24, 34, 157, 219 onto coordinate, 189 proper colorings, see also colorings pseudorandom number generator, 318 random adjacent transpositions, 217 comparison upper bound, 217 coupling upper bound, 218 single card lower bound, 219 Wilson’s method lower bound, 220 random colorings, 90 random mapping representation, 7, 70 random number generator, see also pseudorandom number generator random sample, 37 Random Target Lemma, 128 random transposition shuffle, 101, 110 coupling upper bound, 102 lower bound, 105 relaxation time, 156 strong stationary time upper bound, 103, 112 random variable, 304 random walk on Z, 30, 229, 277, 286 biased, 230 null recurrent, 279 on Zd, 275 recurrent for d = 2, 278 transient for d = 3, 278 on binary tree bottleneck ratio lower bound, 91 commute time, 132 coupling upper bound, 69 cover time, 147 hitting time, 139 no cutoff, 253 on cycle, 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 on group, 27, 75, 99, 184 on hypercube, 23, 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 on path, 63, see also birth-and-death chain, see also gambler’s ruin, 120, 248 eigenvalues and eigenfunctions, 158, 159 on torus, 65 coupling upper bound, 66, 74 cover time, 147, 152 hitting time, 133 perturbed, 183, 187 self-avoiding, 319 simple, 9, 15, 115, 183 weighted, 115 randomized paths, 183, 225 randomized stopping time, 77 Rayleigh’s Monotonicity Law, 122, 278 Rayleigh-Ritz theorem, 308 recurrent, 276, 285 reflection principle, 30, 34, 34 regular graph, 11 counting lower bound, 87 relaxation time, 155 bottleneck ratio bounds, 177 continuous time, 268 coupling upper bound, 171 mixing time lower bound, 155 mixing time upper bound, 155 variational characterization of, 176 resistance, 115 return probability, 136, 239, 284 reversal, 221, see also Durrett chain reversed chain, see also time reversal reversibility, 15, 116 detailed balance equations, 14 riffle shuffle, 106, 112 counting lower bound, 109 generalized, 110 strong stationary time upper bound, 108 rising sequence, 107 rooted tree, 68 roots of unity, 156 sampling, 313 and counting, 195 exact, 195, 293 self-avoiding walk, 319, 320, 324 semi-random transpositions, 112
Previous Page Next Page