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
Previous Page Next Page