此書是對Markov 鏈理論的現(xiàn)代處理方法的導(dǎo)引，該方法的主要目標(biāo)是確定一個Markov 鏈?zhǔn)諗康阶鳛閼B(tài)空間體積和幾何的函數(shù)的平穩(wěn)分布的收斂速率。作者發(fā)展了估計收斂時間的關(guān)鍵工具，包括耦合、強(qiáng)平穩(wěn)時間以及譜方法；一有可能，便強(qiáng)調(diào)概率論式的方法。該書包括了許多例題并對統(tǒng)計力學(xué)的中心模型給出了簡短介紹；還講述了網(wǎng)絡(luò)上的隨機(jī)游動, 包括擊中和掩蓋時間, 以及對洗牌的各種方法的分析。至于預(yù)備知識，作者假定了對概率論的適度了解以及大學(xué)水平的線性代數(shù)。本書打算將這個活躍的研究領(lǐng)域的激情帶給大范圍的受眾。
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
書單推薦
