Mixing times of a Burnside process Markov chain on set partitions

Let X be a finite set and let G be a finite group acting on X . The group action splits X into disjoint orbits. The Burnside process is a Markov chain on X which has a uniform stationary distribution when the chain is lumped to orbits. We consider the case where X = [ k ] n with k ≥ n and G = S k is the symmetric group on [ k ] , such that G acts on X by permuting the value of each coordinate. The resulting Burnside process gives a novel algorithm for sampling a set partition of [ n ] uniformly at random. We obtain bounds on the mixing time and show that the chain is rapidly mixing. For the case k < n , the algorithm corresponds to sampling a set partition of [ n ] with at most k blocks, and we obtain a mixing time bound which is independent of n . Along the way, we obtain explicit formulas for the transition probabilities and bounds on the second largest eigenvalue for both the original process and the lumped chain.