Enhancing the Markov Chain Monte Carlo Method

The Markov Chain Monte Carlo method is arguably the most powerful algorithmic tool available for approximate counting problems. Most known algorithms for such problems follow the paradigm of defining a Markov chain and showing that it mixes rapidly. However, there are natural counting problems where the obvious Markov chains do not mix rapidly. Annealing and Simulated Tempering are two heuristic approaches that can be applied in such situations. Both aim at finding ways to circumvent bottlenecks that cause Markov chains to mix slowly. In this talk, we will explore the power and limitations of these approaches.

We present a simulated annealing based algorithm for the problem of generating random binary contingency tables. This problem can be restated as generating random bipartite graphs with a given degree sequence. This is based on joint work with Ivona Bezakova and Eric Vigoda. On the flip side, we show that in some scenarios, simulated tempering fails to speed up the mixing of the Markov chain and in fact no temperature based interpolants for the tempering algorithm can succeed. This is based on joint work with Dana Randall.

Speaker Details

Nayantara Bhatnagar is a Ph.D candidate in the Algorithms, Combinatorics and Optimization program at Georgia Tech. Her advisors are Dana Randall and Eric Vigoda. Her main research interests are Randomized algorithms and the Markov Chain Monte Carlo method. She is also interested in the application of these methods to algorithmic problems arising in Statistical Physics and Biology.

Date:
Speakers:
Nayantara Bhatnagar
Affiliation:
Georgia Tech
    • Portrait of Jeff Running

      Jeff Running