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

__Claremont Graduate University__ | __Claremont McKenna__ | __Harvey Mudd__ | __Pitzer__ | __Pomona__ | __Scripps__

Proudly Serving Math Community at the Claremont Colleges Since 2007

Copyright © 2018 Claremont Center for the Mathematical Sciences