Show simple item record

dc.contributor.authorBhatnagar, Nayantaraen_US
dc.date.accessioned2007-08-16T18:00:25Z
dc.date.available2007-08-16T18:00:25Z
dc.date.issued2007-07-09en_US
dc.identifier.urihttp://hdl.handle.net/1853/16323
dc.description.abstractThe Markov Chain Monte Carlo (MCMC) method has been widely used in practice since the 1950's in areas such as biology, statistics, and physics. However, it is only in the last few decades that powerful techniques for obtaining rigorous performance guarantees with respect to the running time have been developed. Today, with only a few notable exceptions, most known algorithms for approximately uniform sampling and approximate counting rely on the MCMC method. This thesis focuses on algorithms that use MCMC combined with an algorithm from optimization called simulated annealing, for sampling and counting problems. Annealing is a heuristic for finding the global optimum of a function over a large search space. It has recently emerged as a powerful technique used in conjunction with the MCMC method for sampling problems, for example in the estimation of the permanent and in algorithms for computing the volume of a convex body. We examine other applications of annealing to sampling problems as well as scenarios when it fails to converge in polynomial time. We consider the problem of randomly generating 0-1 contingency tables. This is a well-studied problem in statistics, as well as the theory of random graphs, since it is also equivalent to generating a random bipartite graph with a prescribed degree sequence. Previously, the only algorithm known for all degree sequences was by reduction to approximating the permanent of a 0-1 matrix. We give a direct and more efficient combinatorial algorithm which relies on simulated annealing. Simulated tempering is a variant of annealing used for sampling in which a temperature parameter is randomly raised or lowered during the simulation. The idea is that by extending the state space of the Markov chain to a polynomial number of progressively smoother distributions, parameterized by temperature, the chain could cross bottlenecks in the original space which cause slow mixing. We show that simulated tempering mixes torpidly for the 3-state ferromagnetic Potts model on the complete graph. Moreover, we disprove the conventional belief that tempering can slow fixed temperature algorithms by at most a polynomial in the number of temperatures and show that it can converge at a rate that is slower by at least an exponential factor.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectAnnealingen_US
dc.subjectMarkov Chain Monte Carloen_US
dc.subjectMarkov chainsen_US
dc.subjectDiscrete probabilityen_US
dc.subjectAlgorithmsen_US
dc.subjectTheoretical computer scienceen_US
dc.subjectSimulated temperingen_US
dc.titleAnnealing and Tempering for Sampling and Countingen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentAlgorithms, Combinatorics, and Optimizationen_US
dc.contributor.departmentComputing
dc.description.advisorCommittee Chair: Dr. Dana Randall; Committee Chair: Dr. Eric Vigoda; Committee Member: Dr. Prasad Tetali; Committee Member: Dr. Robin Thomas; Committee Member: Dr. Santosh Vempalaen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record