logo资料库

Markov Chains and Mixing Times.pdf

发布时间：2022-06-06 发布人：admin 分类：说明书 资料大小：6.45M 资料格式：pdf 举报 版权申诉
第1页 / 共387页
第2页 / 共387页
第3页 / 共387页
第4页 / 共387页
第5页 / 共387页
第6页 / 共387页
第7页 / 共387页
第8页 / 共387页
资料共387页，剩余部分请下载后查看
    Preface
    Overview
    For the Reader
    For the Instructor
    For the Expert
    Acknowledgements
    Part I: 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 Pólya 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 2 Bound
    12.6. Time Averages
    Exercises
    Notes
    Part II: 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 Functions 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
    Markov Chains and Mixing Times David A. Levin Yuval Peres Elizabeth L. Wilmer University of Oregon E-mail address: dlevin@uoregon.edu URL: http://www.uoregon.edu/~dlevin Microsoft Research, University of Washington and UC Berkeley E-mail address: peres@microsoft.com URL: http://research.microsoft.com/~peres/ Oberlin College E-mail address: elizabeth.wilmer@oberlin.edu URL: http://www.oberlin.edu/math/faculty/wilmer.html
    Contents Preface Overview For the Reader For the Instructor For the Expert Acknowledgements Part I: Basic Methods and Examples Chapter 1. Introduction to Finite Markov Chains Irreducibility and Aperiodicity 1.1. Finite Markov Chains 1.2. Random Mapping Representation 1.3. 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 P´olya 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 Introduction 3.1. 3.2. Metropolis Chains 3.3. Glauber Dynamics Exercises Notes Chapter 4. Introduction to Markov Chain Mixing 4.1. Total Variation Distance v xi xii xiii xiv xvi xvii 1 3 3 6 8 9 10 14 16 18 20 21 21 22 23 25 26 27 30 34 35 37 37 37 40 44 44 47 47
    vi CONTENTS 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 49 52 53 55 55 58 59 60 63 63 64 65 70 73 74 75 75 76 77 78 80 83 84 85 87 87 88 92 96 98 98 99 99 101 106 109 111 115 115 116 117 118 123 124 125
    CONTENTS 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 ℓ2 Bound 12.6. Time Averages Exercises Notes Part II: 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 vii 127 127 128 130 133 134 138 139 141 143 143 143 147 151 152 153 153 154 156 160 163 165 167 168 169 171 171 172 175 179 182 185 187 187 189 189 191 193 195 198 199 201 201 203
    viii CONTENTS 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 Functions 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 Introduction 19.1. 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 204 206 208 211 213 214 217 217 221 226 227 229 229 231 233 235 239 241 243 245 245 247 247 248 252 254 255 255 257 257 258 260 262 263 265 265 266 268 269 273 273 275 275 277
    CONTENTS 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 Introduction 22.1. 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 Inverse Distribution Function Method B.1. What Is Simulation? B.2. Von Neumann Unbiasing* B.3. Simulating Discrete Distributions and Sampling B.4. 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 ix 279 283 284 285 286 287 287 288 293 294 296 297 297 299 299 300 301 303 303 308 308 309 311 311 312 313 314 314 317 318 318 319 322 325 327 353 363 365
    分享到：
    赞 收藏

    相关推荐

    资料库

    信息化

    共收录1827份资料，累计6个分类，关注成员有19位，主要包括：管理软件,企业管理,电子商务,其它,IT管理,项目管理

    热门标签

    管理软件 企业管理 电子商务 其它 IT管理 项目管理

    最新资料