DocumentCode :
2643389
Title :
Factoring graphs to bound mixing rates
Author :
Madras, Neal ; Randall, Dana
Author_Institution :
Dept. of Math. & Stat., York Univ., North York, Ont., Canada
fYear :
1996
fDate :
14-16 Oct 1996
Firstpage :
194
Lastpage :
203
Abstract :
This paper develops a new technique for bounding the mixing rate of a Markov chain by decomposing the state space into factors. The first application is an efficient Monte Carlo Markov chain algorithm for generating random three-colorings of 2-dimensional lattice regions. This provides a rigorous tool for studying some properties of the 3-state Potts model and the ice model from statistical mechanics. As a second application, we develop similar techniques to bound the mixing rate of a Metropolis sampling algorithm by a type of “temperature factorization”. Both factorization theorems work by using known mixing properties of related Markov chains to establish the efficiency of a new sampling algorithm
Keywords :
Markov processes; Monte Carlo methods; Potts model; statistical mechanics; 2-dimensional lattice regions; 3-state Potts model; Markov chain; Metropolis sampling algorithm; Monte Carlo Markov chain algorithm; factorization theorems; ice model; mixing rate bounding; random three-colorings; state space decomposition; statistical mechanics; Artificial intelligence; Councils; Educational institutions; Lapping; Lattices; Mathematics; Monte Carlo methods; Physics; State-space methods; Thermodynamics;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
Conference_Location :
Burlington, VT
ISSN :
0272-5428
Print_ISBN :
0-8186-7594-2
Type :
conf
DOI :
10.1109/SFCS.1996.548478
Filename :
548478
Link To Document :
بازگشت