Title :
Mixing [Markov chain]
Author_Institution :
Coll. of Comput., Georgia Inst. of Technol., Atlanta, GA, USA
Abstract :
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.
Keywords :
Markov processes; random processes; sampling methods; Markov chain mixing; mixing time; running time; stationary distribution; Algorithm design and analysis; Computational modeling; Convergence; Monte Carlo methods; Nearest neighbor searches; Pervasive computing; Physics computing; Sampling methods; State-space methods; Stochastic processes;
Conference_Titel :
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
Print_ISBN :
0-7695-2040-5
DOI :
10.1109/SFCS.2003.1238175
