Date/Time
Date(s) - 07/11/2023
3:30 pm - 5:00 pm

Location: University Hall (UH) 112

Speaker: J. E. Paguyo (McMaster University)

Title: Sampling unlabeled structures via the Burnside process 

Abstract:
Let $X$ be a finite set and $G$ a finite group acting on $X$. This splits $X$ into disjoint orbits. The Burnside process is a Markov chain on $X$ with a uniform stationary distribution when projected onto the orbits. This gives an algorithm for sampling combinatorial structures modulo a group of symmetries, such as unlabeled trees and integer partitions. It is a special case of hit-and-run, a class of unifying algorithms which include the Gibbs sampler and the Swendsen-Wang algorithm. These are widely used algorithms, most of which have resisted mixing time analysis. In this talk, we give the history of the Burnside process and survey previous results. In particular, we consider a variant of a chain studied by Jerrum, Aldous-Fill, and Diaconis-Zhong, which gives a sampler for set partitions and discusses mixing time results. This talk will be in probabilistic English but aimed towards a non-specialist audience.

Refreshments at 3pm in HH 216