Embedding Combinatorial Structures as Gibbs Distributions for Faster Approximation of Normalizing Constants

• Activity Number: 324
• Type: Invited
• Date/Time: Tuesday, August 6, 2013 : 10:30 AM to 12:20 PM
• Sponsor: IMS
• Author(s): Mark Lawrence Huber*+
• Companies: Claremont McKenna College
• Keywords: poset ; linear extensions ; approximation algorithms ; MCMC

Abstract

Recent work in variance free methods for turning the ability to sample from a space into approximation algorithms for the volume of a space have concentrated on Gibbs distributions. While this encompasses many problems directly, other problems need to be transformed in order to utilize these new algorithms. This work presents an improved algorithm for counting the number of linear extensions of a partially ordered set (poset), a problem with applications for nonparametric testing. The new method first embeds the combinatorial structure into a Gibbs distribution framework, and then shows how to modify an existing MCMC algorithm to handle the new distribution. Care must be taken at this step: the naive embedding destroys the ability to sample from the distribution. The result is the fastest known algorithm for approximating the number of linear extensions of a partial order.