## 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 *Sigma*^{n} by permutation
of the positions of symbols. This action partitions
*Sigma*^{n} into orbits, i.e., subsets of
*Sigma*^{n} 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 *Sigma*^{n} 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