1
Introduction (July 20, 1999)
Reversible Markov Chains and Random Walks on Graphs
Unfinished monograph, 2002 (this is recompiled version, 2014)
David Aldous and James Allen Fill
Contents:
1
Introduction (July 20, 1999)
1.1
Word problems
1.1.1
Random knight moves
1.1.2
The white screen problem
1.1.3
Universal traversal sequences
1.1.4
How long does it take to shuffle a deck of cards?
1.1.5
Sampling from high-dimensional distributions: Markov chain Monte Carlo
1.1.6
Approximate counting of self-avoiding walks
1.1.7
Simulating a uniform random spanning tree
1.1.8
Voter model on a finite graph
1.1.9
Are you related to your ancestors?
1.2
So what’s in the book?
1.2.1
Conceptual themes
1.2.2
Prerequisites
1.2.3
Contents and alternate reading
2
General Markov Chains (September 10, 1999)
2.1
Notation and reminders of fundamental results
2.1.1
Stationary distribution and asymptotics
2.1.2
Continuous-time chains
2.2
Identities for mean hitting times and occupation times
2.2.1
Occupation measures and stopping times
2.2.2
Mean hitting time and related formulas
2.2.3
Continuous-time versions
2.3
Variances of sums
2.4
Two metrics on distributions
2.4.1
Variation distance
2.4.2
L
2
L^{2}
distance
2.4.3
Exponential tails of hitting times
2.5
Distributional identities
2.5.1
Stationarity consequences
2.5.2
A generating function identity
2.5.3
Distributions and continuization
2.6
Matthews’ method for cover times
2.7
New chains from old
2.7.1
The chain watched only on
A
A
2.7.2
The chain restricted to
A
A
2.7.3
The collapsed chain
2.8
Miscellaneous methods
2.8.1
Martingale methods
2.8.2
A comparison argument
2.8.3
Wald equations
2.9
Notes on Chapter 2.
2.10
Move to other chapters
2.10.1
Attaining distributions at stopping times
2.10.2
Differentiating stationary distributions
3
Reversible Markov Chains (September 10, 2002)
3.1
Introduction
3.1.1
Time-reversals and cat-and-mouse games
3.1.2
Entrywise ordered transition matrices
3.2
Reversible chains and weighted graphs
3.2.1
The fluid model
3.3
Electrical networks
3.3.1
Flows
3.3.2
The analogy
3.3.3
Mean commute times
3.3.4
Foster’s theorem
3.4
The spectral representation
3.4.1
Mean hitting times and reversible chains
3.5
Complete monotonicity
3.5.1
Lower bounds on mean hitting times
3.5.2
Smoothness of convergence
3.5.3
Inequalities for hitting time distributions on subsets
3.5.4
Approximate exponentiality of hitting times
3.6
Extremal characterizations of eigenvalues
3.6.1
The Dirichlet formalism
3.6.2
Summary of extremal characterizations
3.6.3
The extremal characterization of relaxation time
3.6.4
Simple applications
3.6.5
Quasistationarity
3.7
Extremal characterizations and mean hitting times
3.7.1
Thompson’s principle and leveling networks
3.7.2
Hitting times and Thompson’s principle
3.8
Notes on Chapter 3
4
Hitting and Convergence Time, and Flow Rate, Parameters for Reversible Markov Chains (October 11, 1994)
4.1
The maximal mean commute time
τ
*
\tau^{*}
4.2
The average hitting time
τ
0
\tau_{0}
4.3
The variation threshold
τ
1
\tau_{1}
.
4.3.1
Definitions
4.3.2
Proof of Theorem 6
4.3.3
τ
1
\tau_{1}
in discrete time, and algorithmic issues
4.3.4
τ
1
\tau_{1}
and mean hitting times
4.3.5
τ
1
\tau_{1}
and flows
4.4
The relaxation time
τ
2
\tau_{2}
4.4.1
Correlations and variances for the stationary chain
4.4.2
Algorithmic issues
4.4.3
τ
2
\tau_{2}
and distinguished paths
4.5
The flow parameter
τ
c
\tau_{c}
4.5.1
Definition and easy inequalities
4.5.2
Cheeger-type inequalities
4.5.3
τ
c
\tau_{c}
and hitting times
4.6
Induced and product chains
4.6.1
Induced chains
4.6.2
Product chains
4.6.3
Efron-Stein inequalities
4.6.4
Why these parameters?
4.7
Notes on Chapter 4
5
Examples: Special Graphs and Trees (April 23 1996)
5.1
One-dimensional chains
5.1.1
Simple symmetric random walk on the integers
5.1.2
Weighted linear graphs
5.1.3
Useful examples of one-dimensional chains
5.2
Special graphs
5.2.1
Biased walk on a balanced tree
5.3
Trees
5.3.1
Parameters for trees
5.3.2
Extremal trees
5.4
Notes on Chapter 5
6
Cover Times (October 31, 1994)
6.1
The spanning tree argument
6.2
Simple examples of cover times
6.3
More upper bounds
6.3.1
Simple upper bounds for mean hitting times
6.3.2
Known and conjectured upper bounds
6.4
Short-time bounds
6.4.1
Covering by multiple walks
6.4.2
Bounding point probabilities
6.4.3
A cat and mouse game
6.5
Hitting time bounds and connectivity
6.5.1
Edge-connectivity
6.5.2
Equivalence of mean cover time parameters
6.6
Lower bounds
6.6.1
Matthews’ method
6.6.2
Balanced trees
6.6.3
A resistance lower bound
6.6.4
General lower bounds
6.7
Distributional aspects
6.8
Algorithmic aspects
6.8.1
Universal traversal sequences
6.8.2
Graph connectivity algorithms
6.8.3
A computational question
6.9
Notes on Chapter 6
7
Symmetric Graphs and Chains (January 31, 1994)
7.1
Symmetric reversible chains
7.1.1
Definitions
7.1.2
This section goes into Chapter 3
7.1.3
Elementary properties
7.1.4
Hitting times
7.1.5
Cover times
7.1.6
Product chains
7.1.7
The cutoff phenomenon and the upper bound lemma
7.1.8
Vertex-transitive graphs and Cayley graphs
7.1.9
Comparison arguments for eigenvalues
7.2
Arc-transitivity
7.2.1
Card-shuffling examples
7.2.2
Cover times for the
d
d
-dimensional torus
Z
N
d
Z^{d}_{N}
.
7.2.3
Bounds for the parameters
7.2.4
Group-theory set-up
7.3
Distance-regular graphs
7.3.1
Exact formulas
7.3.2
Examples
7.3.3
Monotonicity properties
7.3.4
Extremal distance-regular graphs
7.3.5
Gelfand pairs and isotropic flights
7.4
Notes on Chapter 7
8
Advanced
L
2
L^{2}
Techniques for Bounding Mixing Times (May 19 1999)
8.1
The comparison method for eigenvalues
8.2
Improved bounds on
L
2
L^{2}
distance
8.2.1
L
q
L^{q}
norms and operator norms
8.2.2
A more general bound on
L
2
L^{2}
distance
8.2.3
Exact computation of
N
(
s
)
N(s)
8.3
Nash inequalities
8.3.1
Nash inequalities and mixing times
8.3.2
The comparison method for bounding
N
(
⋅
)
N(\cdot)
8.4
Logarithmic Sobolev inequalities
8.4.1
The log-Sobolev time
τ
l
\tau_{l}
8.4.2
τ
l
\tau_{l}
, mixing times, and hypercontractivity
8.4.3
Exact computation of
τ
l
\tau_{l}
8.4.4
τ
l
\tau_{l}
and product chains
8.4.5
The comparison method for bounding
τ
l
\tau_{l}
8.5
Combining the techniques
8.6
Notes on Chapter 8
9
A Second Look at General Markov Chains (April 21, 1995)
9.1
Minimal constructions and mixing times
9.1.1
Strong stationary times
9.1.2
Stopping times attaining a specified distribution
9.1.3
Examples
9.2
Markov chains and spanning trees
9.2.1
General Chains and Directed Weighted Graphs
9.2.2
Electrical network theory
9.3
Self-verifying algorithms for sampling from a stationary distribution
9.3.1
Exact sampling via the Markov chain tree theorem
9.3.2
Approximate sampling via coalescing paths
9.3.3
Exact sampling via backwards coupling
9.4
Making reversible chains from irreversible chains
9.4.1
Mixing times
9.4.2
Hitting times
9.5
An example concerning eigenvalues and mixing times
9.6
Miscellany
9.6.1
Mixing times for irreversible chains
9.6.2
Balanced directed graphs
9.6.3
An absorption time problem
9.7
Notes on Chapter 9
10
Some Graph Theory and Randomized Algorithms (September 1 1999)
10.1
Expanders
10.1.1
Definitions
10.1.2
Random walk on expanders
10.1.3
Counter-example constructions
10.2
Eigenvalues and graph theory
10.2.1
Diameter of a graph
10.2.2
Paths avoiding congestion
10.3
Randomized algorithms
10.3.1
Background
10.3.2
Overview of randomized algorithms using random walks or Markov chains
10.4
Miscellaneous graph algorithms
10.4.1
Amplification of randomness
10.4.2
Using random walk to define an objective function
10.4.3
Embedding trees into the
d
d
-cube
10.4.4
Comparing on-line and off-line algorithms
10.5
Approximate counting via Markov chains
10.5.1
Volume of a convex set
10.5.2
Matchings in a graph
10.5.3
Simulating self-avoiding walks
10.6
Notes on Chapter 9
10.7
Material belonging in other chapters
10.7.1
Large deviation bounds
10.7.2
The probabilistic method in combinatorics
10.7.3
copied to Chapter 4 section 6.5
11
Markov Chain Monte Carlo (January 8 2001)
11.1
Overview of Applied MCMC
11.1.1
Summary
11.1.2
Further aspects of applied MCMC
11.2
The two basic schemes
11.2.1
Metropolis schemes
11.2.2
Line-sampling schemes
11.3
Variants of basic MCMC
11.3.1
Metropolized line sampling
11.3.2
Multiple-try Metropolis
11.3.3
Multilevel sampling
11.3.4
Multiparticle MCMC
11.4
A little theory
11.4.1
Comparison methods
11.4.2
Metropolis with independent proposals
11.5
The diffusion heuristic for optimal scaling of high dimensional Metropolis
11.5.1
Optimal scaling for high-dimensional product distribution sampling
11.5.2
The diffusion heuristic.
11.5.3
Sketch proof of Theorem
11.6
Other theory
11.6.1
Sampling from log-concave densities
11.6.2
Combining MCMC with slow exact sampling
11.7
Notes on Chapter MCMC
11.8
Belongs in other chapters
11.8.1
Pointwise ordered transition matrices
12
Coupling Theory and Examples (October 11, 1999)
12.1
Using coupling to bound variation distance
12.1.1
The coupling inequality
12.1.2
Comments on coupling methodology
12.1.3
Random walk on a dense regular graph
12.1.4
Continuous-time random walk on the
d
d
-cube
12.1.5
The graph-coloring chain
12.1.6
Permutations and words
12.1.7
Card-shuffling by random transpositions
12.1.8
Reflection coupling on the
n
n
-cycle
12.1.9
Card-shuffling by random adjacent transpositions
12.1.10
Independent sets
12.1.11
Two base chains for genetic algorithms
12.1.12
Path coupling
12.1.13
Extensions of a partial order
12.2
Notes on Chapter 4-3
13
Continuous State, Infinite State and Random Environment (June 23, 2001)
13.1
Continuous state space
13.1.1
One-dimensional Brownian motion and variants
13.1.2
d
d
-dimensional Brownian motion
13.1.3
Brownian motion in a convex set
13.1.4
Discrete-time chains: an example on the simplex
13.1.5
Compact groups
13.1.6
Brownian motion on a fractal set
13.2
Infinite graphs
13.2.1
Set-up
13.2.2
Recurrence and Transience
13.2.3
The finite analog of transience
13.2.4
Random walk on
Z
d
Z^{d}
13.2.5
The torus
Z
m
d
Z^{d}_{m}
13.2.6
The infinite degree-
r
r
tree
13.2.7
Generating function arguments
13.2.8
Comparison arguments
13.2.9
The hierarchical tree
13.2.10
Towards a classification theory for sequences of finite chains
13.3
Random Walks in Random Environments
13.3.1
Mixing times for some random regular graphs
13.3.2
Randomizing infinite trees
13.3.3
Bias and speed
13.3.4
Finite random trees
13.3.5
Randomly-weighted random graphs
13.3.6
Random environments in
d
d
dimensions
13.4
Notes on Chapter 13
14
Interacting Particles on Finite Graphs (March 10, 1994)
14.1
Coupling
14.1.1
The coupling inequality
14.1.2
Examples using the coupling inequality
14.1.3
Comparisons via couplings
14.2
Meeting times
14.3
Coalescing random walks and the voter model
14.3.1
A bound using the voter model
14.3.2
A bound using the coalescing random walk model
14.3.3
Conjectures and examples
14.3.4
Voter model with new opinions
14.3.5
Large component sizes in the voter model with new opinions
14.3.6
Number of components in the voter model with new opinions
14.4
The antivoter model
14.4.1
Variances in the antivoter model
14.4.2
Examples and Open Problems
14.5
The interchange process
14.5.1
Card-shuffling interpretation
14.6
Other interacting particle models
14.6.1
Product-form stationary distributions
14.6.2
Gaussian families of occupation measures
14.7
Other coupling examples
14.7.1
Markov coupling may be inadequate
14.8
Notes on Chapter 14
Bibliography