The Library
The "Burnside process" converges slowly
Tools
UNSPECIFIED (1998) The "Burnside process" converges slowly. In: 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 98), BARCELONA, SPAIN, OCT 08-10, 1998. Published in: RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE, 1518 pp. 331-345. ISBN 3-540-65142-X. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
We consider the problem of sampling "unlabelled structures", i.e., sampling combinatorial structures module 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 Ne 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: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-65142-X | ||||
ISSN: | 0302-9743 | ||||
Editor: | Luby, M and Rolim, J and Serna, M | ||||
Official Date: | 1998 | ||||
Dates: |
|
||||
Volume: | 1518 | ||||
Number of Pages: | 15 | ||||
Page Range: | pp. 331-345 | ||||
Publication Status: | Published | ||||
Title of Event: | 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 98) | ||||
Location of Event: | BARCELONA, SPAIN | ||||
Date(s) of Event: | OCT 08-10, 1998 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |