Uniform sampling modulo a group of symmetries using Markov chain simulation

Mark Jerrum

Abstract: Let Sigma be a finite alphabet, and G a permutation group of degree n. The group G induces a natural action on Sigman by permutation of the positions of symbols. This action partitions Sigman into orbits, i.e., subsets of Sigman which are equivalent modulo the symmetry group G. The problem addressed is that of uniform sampling from the set of all orbits. This problem is closely allied to that of estimating the cycle index polynomial of G, and can be regarded as part of the wider question ``to what extent can Polya theory be automated?'' The approach taken here is to simulate a Markov chain on Sigman that converges to a uniform distribution on the orbits. The Markov chain may be rapidly mixing for all G, but positive results to date are limited to some very simple special cases. The general question is likely to be difficult to resolve, because it includes the mixing rate of the Swendsen-Wang process as a special case.

LFCS report ECS-LFCS-93-272, July 1993.

Previous | Index | Next