UNSPECIFIED. (2002) The 'Burnside process' converges slowly. COMBINATORICS PROBABILITY & COMPUTING, 11 (1). pp. 21-34. ISSN 0963-5483

Full text not available from this repository.

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
Journal or Publication Title:	COMBINATORICS PROBABILITY & COMPUTING
Publisher:	CAMBRIDGE UNIV PRESS
ISSN:	0963-5483
Date:	January 2002
Volume:	11
Number:	1
Number of Pages:	14
Page Range:	pp. 21-34
Identification Number:	10.1017/S096354830100493X
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/11237

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item