The Library
The 'Burnside process' converges slowly
Tools
Tools
Tools
Goldberg, Leslie Ann and Jerrum, Mark (1998) The 'Burnside process' converges slowly. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-344.pdf - Other - Requires a PDF viewer. Download (1277Kb) | Preview |
Abstract
We consider the problem of sampling "unlabelled structures", i.e., sampling combinatorial structures modulo a group of symmetries. The main tool which has been used for this sampling problem is Burnside's lemma. In situations where a significant proportion of the structures have no non-trivial symmetries, it is already fairly well understood how to apply this tool. More generally, it is possible to obtain nearly uniform samples by simulating a Markov chain that we call the Burnside process; this is a random walk on a bipartite graph which essentially implements Burnside's lemma. For this approach to be feasible, the Markov chain ought to be "rapidly mixing", i.e., converge rapidly to equilibrium. The Burnside process was known to be rapidly mixing for some special groups, and it has even been implemented in some computational group theory algorithms. In this paper, we show that the Burnside process is not rapidly mixing in general. In particular, we construct an infinite family of permutation groups for which we show that the mixing time is exponential in the degree of the group.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Burnside problem | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | June 1998 | ||||
| Dates: |
|
||||
| Number: | Number 344 | ||||
| Number of Pages: | 14 | ||||
| DOI: | CS-RR-344 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Publisher Statement: | Leslien Ann Goldberg and Mark Jerrum, “The "Burnside Process" Converges Slowly”, <i>Proceedings RANDOM '98</i>, Lecture Notes in Computer Science, Springer-Verlag (1998) | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | 21726 (ESPRIT), 20244 (ESPRIT) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
