Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

The 'Burnside process' converges slowly

Tools
- Tools
+ Tools

Goldberg, Leslie Ann and Jerrum, Mark (2002) The 'Burnside process' converges slowly. Combinatorics, Probability & Computing, Volume 11 (Number 1). pp. 21-34. doi:10.1017/S096354830100493X ISSN 0963-5483.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Official URL: http://dx.doi.org/10.1017/S096354830100493X

Request Changes to record.

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 nontrivial 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: Journal Article
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title: Combinatorics, Probability & Computing
Publisher: Cambridge University Press
ISSN: 0963-5483
Official Date: January 2002
Dates:
DateEvent
January 2002Published
Volume: Volume 11
Number: Number 1
Number of Pages: 14
Page Range: pp. 21-34
DOI: 10.1017/S096354830100493X
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access

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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us