370 INDEX separation distance, 79, 80, 84, 301 total variation upper bound, 260 upper bound on total variation, 80 Series Law, 119 shift chain, see also patterns in coin tossing shuffle cyclic-to-random, 112 move-to-front, 81 open problems, 300 random adjacent transposition, 217 comparison upper bound, 217 coupling upper bound, 218 single card lower bound, 219 Wilson’s method lower bound, 220 random transposition, 101, 110 coupling upper bound, 102 lower bound, 105 relaxation time, 156 strong stationary time upper bound, 103, 112 riffle, 106, 112 counting lower bound, 109 generalized, 110 strong stationary time upper bound, 108 semi-random transpositions, 112 top-to-random, 75 cutoff, 247 lower bound, 96 strong stationary time upper bound, 78, 81, 84 simple random walk, 9, 115, 183 stationary distribution of, 10 simplex, 318 simulation of random variables, 311, 313 sink, 117 source, 117 spectral gap, 154, see also relaxation time absolute, 154 bottleneck ratio bounds, 177 variational characterization of, 176 spectral theorem for symmetric matrices, 308 spin system, 43 star, 90 stationary distribution, 10 existence of, 12, 19 uniqueness of, 14, 17 stationary time, 77, 83 strong, 78, 243 Stirling’s formula, 309 stochastic flow, see also grand coupling stopping time, 76, 84, 231 randomized, 77 strength of flow, 117 Strong Law of Large Numbers, 305 strong stationary time, 78, 243 submartingale, 230 submultiplicativity of ¯(t), d 54, 55 of s(t), 84 supermartingale, 230, 245 support, 304 symmetric group, 75, 99 symmetric matrix, 308 systematic updates, 300 target time, 128, 129 tensor product, 160 Thomson’s Principle, 121, 278 tiling domino, 319 lozenge, 290 time averages, 165 time reversal, 15, 34, 55, 57, 60, 82, 107 time-inhomogeneous Markov chain, 20, 112, 191 top-to-random shuffle, 75 cutoff, 247 lower bound, 96 strong stationary time upper bound, 78, 81, 84 torus definition of, 65 glued bottleneck ratio lower bound, 90 hitting time upper bound, 139 lamplighter chain on, 263 random walk on coupling upper bound, 66, 74 cover time, 147, 152 hitting time, 133 perturbed, 183, 187 total variation distance, 47 coupling characterization of, 50 Hellinger distance upper bound, 270 monotonicity of, 59 separation distance upper bound, 80 standardized (d(t), ¯(t)), d 53 upper bound on separation distance, 260 transient, 276 transition matrix definition of, 3 eigenvalues of, 153, 167 multiply on left, 6 multiply on right, 6 spectral representation of, 153 transition probabilities, t-step, 6 transition times, 265 transitive chain, 29, 34, 60, 300 network, 131 transportation metric, 189, 198 transpose (of a matrix), 308

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.