A new way to view popping algorithms

10/03/2017 - 12:15pm
10/03/2017 - 1:10pm
Speaker: 
Mark Huber (CMC)
Abstract: 

One method of sampling from high dimensional distributions is called "popping", and was first introduced by David Wilson in 1996. In this talk I'll show how these popping algorithms arise naturally as a special case of a type of acceptance rejection algorithm. In particular, I'll describe how the algorithm for generating uniformly from the rooted directed spanning trees of a graph, and for generating uniformly from sink free orientations of a graph, both come about from such an analysis. I'll then talk about how these algorithms can be used to generate perfectly from problems where popping does not apply such as the isolated (aka independent) sets of a graph.

Where: 
Millikan 2099, Pomona College