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