Mixing

In this paper, we introduce the notion of a Markov chain and explore how it can be used to sample from a large set of configurations. Our primary focus is determining how quickly a Markov chain "mixes, " or converges to its stationary distribution, as this is the key factor in the running time. We provide an overview of several techniques used to establish good bounds on the mixing time. The applications are mostly chosen from statistical physics, although the methods are much more general.

Authors

• Dana Randall

Keywords

• Sampling methods
• Monte Carlo methods
• Nearest neighbor searches
• Algorithm design and analysis
• State-space methods
• Pervasive computing
• Physics computing
• Computational modeling
• Stochastic processes
• Convergence
• Markov Chain
• Stationary Distribution
• Mixing Time
• Statistical Physics
• State Space
• Independent Set
• Transition Probabilities
• Random Walk
• Algorithm Design
• Change In Distance
• Ising Model
• Partition Function
• Hamming Distance
• Intimate Connection
• Metropolis-Hastings
• Detailed Balance
• Rapid Mixing
• Pairwise Model
• Chain Mixing
• Arbitrary Configuration
• Slow Mixing
• Fast Mixing
• Behavior Of Chains