此书是对Markov 链理论的现代处理方法的导引，该方法的主要目标是确定一个Markov 链收敛到作为态空间体积和几何的函数的平稳分布的收敛速率。作者发展了估计收敛时间的关键工具，包括耦合、强平稳时间以及谱方法；一有可能，便强调概率论式的方法。该书包括了许多例题并对统计力学的中心模型给出了简短介绍；还讲述了网络上的随机游动, 包括击中和掩盖时间, 以及对洗牌的各种方法的分析。至于预备知识，作者假定了对概率论的适度了解以及大学水平的线性代数。本书打算将这个活跃的研究领域的激情带给大范围的受众。
Preface
Overview
For the Reader
For the Instructor
For the Expert
Acknowledgements
Part Ⅰ： Basic Methods and Examples
Chapter 1． Introduction to Finite Markov Chains
1．1． Finite Markov Chains
1．2． Random Mapping Representation
1．3． Irreducibility and Aperiodicity
1．4． Random Walks on Graphs
1．5． Stationary Distributions
1．6． Reversibility and Time Reversals
1．7． Classifying the States of a Markov Chain
Exercises
Notes
Chapter 2． Classical （and Useful） Markov Chains
2．1． Gambler's Ruin
2．2． Coupon Collecting
2．3． The Hypercube and the Ehrenfest Urn Model
2．4． The Polya Urn Model
2．5． Birth-and-Death Chains
2．6． Random Walks on Groups
2．7． Random Walks on Z and Reflection Principles
Exercises
Notes
Chapter 3． Markov Chain Monte Carlo： Metropolis and Glauber Chains
3．1． Introduction
3．2． Metropolis Chains
3．3． Glauber Dynamics
Exercises
Notes
Chapter 4． Introduction to Markov Chain Mixing
4．1． Total Variation Distance
4．2． Coupling and Total Variation Distance
4．3． The Convergence Theorem
4．4． Standardizing Distance from Stationarity
4．5． Mixing Time
4．6． Mixing and Time Reversal
4．7． Ergodic Theorem*
Exercises
Notes
Chapter 5． Coupling
5．1． Definition
5．2． Bounding Total．Variation Distance
5．3． Examples
5．4． Grand Couplings
Exercises
Notes
Chapter 6． Strong Stationary Times
6．1． Top-to-Random Shuffle
6．2． Definitions
6．3． Achieving Equilibrium
6．4． Strong Stationary Times and Bounding Distance
6．5． Examples
6．6． Stationary Times and Cesaro Mixing Time
Exercises
Notes
Chapter 7． Lower Bounds on Mixing Times
7．1． Counting and Diameter Bounds
7．2． Bottleneck Ratio
7．3． Distinguishing Statistics
7．4． Examples
Exercises
Notes
Chapter 8． The Symmetric Group and Shuffling Cards
8．1． The Symmetric Group
8．2． Random Transpositions
8．3． Riffle Shuffles
Exercises
Notes
Chapter 9． Random Walks on Networks
9．1． Networks and Reversible Markov Chains
9．2． Harmonic Functions
9．3． Voltages and Current Flows
9．4． Effective Resistance
9．5． Escape Probabilities on a Square
Exercises
Notes
Chapter 10． Hitting Times
10．1． Definition
10．2． Random Target Times
10．3． Commute Time
10．4． Hitting Times for the Torus
10．5． Bounding Mixing Times via Hitting Times
10．6． Mixing for the Walk on Two Glued Graphs
Exercises
Notes
Chapter 11． Cover Times
11．1． Cover Times
11．2． The Matthews Method
11．3． Applications of the Matthews Method
Exercises
Notes
Chapter 12． Eigenvalues
12．1． The Spectral Representation of a Reversible Transition Matrix
12．2． The Relaxation Time
12．3． Eigenvalues and Eigenfunctions of Some Simple Random Walks
12．4． Product Chains
12．5． An l2 Bound
12．6． Time Averages
Exercises
Notes
Part Ⅱ： The Plot Thickens
Chapter 13． Eigenfunctions and Comparison of Chains
13．1． Bounds on Spectral Gap via Contractions
13．2． Wilson's Method for Lower Bounds
13．3． The Dirichlet Form and the Bottleneck Ratio
13．4． Simple Comparison of Markov Chains
13．5． The Path Method
13．6． Expander Graphs
Exercises
Notes
Chapter 14． The Transportation Metric and Path Coupling
14．1． The Transportation Metric
14．2． Path Coupling
14．3． Fast Mixing for Colorings
14．4． Approximate Counting
Exercises
Notes
Chapter 15． The Ising Model
15．1． Fast Mixing at High Temperature
15．2． The Complete Graph
15．3． The Cycle
15．4． The Tree
15．5． Block Dynamics
15．6． Lower Bound for Ising on Square
Exercises
Notes
Chapter 16． From Shuffling Cards to Shuffling Genes
16．1． Random Adjacent Transpositions
16．2． Shuffling Genes
Exercise
Notes
Chapter 17． Martingales and Evolving Sets
17．1． Definition and Examples
17．2． Optional Stopping Theorem
17．3． Applications
17．4． Evolving Sets
17．5． A General Bound on Return Probabilities
17．6． Harmonic Fhnctions and the Doob h-Transform
17．7． Strong Stationary Times from Evolving Sets
Exercises
Notes
Chapter 18． The Cutoff Phenomenon
18．1． Definition
18．2． Examples of Cutoff
18．3． A Necessary Condition for Cutoff
18．4． Separation Cutoff
Exercise
Notes
Chapter 19． Lamplighter Walks
19．1． Introduction
19．2． Relaxation Time Bounds
19．3． Mixing Time Bounds
19．4． Examples
Notes
Chapter 20． Continuous-Time Chains
20．1． Definitions
20．2． Continuous-Time Mixing
20．3． Spectral Gap
20．4． Product Chains
Exercises
Notes
Chapter 21． Countable State Space Chains
21．1． Recurrence and Transience
21．2． Infinite Networks
21．3． Positive Recurrence and Convergence
21．4． Null Recurrence and Convergence
21．5． Bounds on Return Probabilities
Exercises
Notes
Chapter 22． Coupling from the Past
22．1． Introduction
22．2． Monotone CFTP
22．3． Perfect Sampling via Coupling from the Past
22．4． The Hardcore Model
22．5． Random State of an Unknown Markov Chain
Exercise
Notes
Chapter 23． Open Problems
23．1． The Ising Model
23．2． Cutoff
23．3． Other Problems
Appendix A． Background Material
A．1． Probability Spaces and Random Variables
A．2． Metric Spaces
A．3． Linear Algebra
A．4． Miscellaneous
Appendix B． Introduction to Simulation
B．1． What Is Simulation?
B．2． Von Neumann Unbiasing
B．3． Simulating Discrete Distributions and Sampling
B．4． Inverse Distribution Function Method
B．5． Acceptance-Rejection Sampling
B．6． Simulating Normal Random Variables
B．7． Sampling from the Simplex
B．8． About Random Numbers
B．9． Sampling from Large Sets
Exercises
Notes
Appendix C． Solutions to Selected Exercises
Bibliography
Notation Index
Index
新书资讯
