On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing

Abstract

Uniform distributions on complicated combinatorial sets can be simulated by the Markov chain method. A condition is given for the simulations to be accurate in polynomial time. Similar analysis of the simulated annealing algorithm remains an open problem. The argument relies on a recent eigenvalue estimate of Alon [4]; the only new mathematical ingredient is a careful analysis of how the accuracy of sample averages of a Markov chain is related to the second-largest eigenvalue.