Random sampling of trivial words in finitely presented groups
- Publication Type:
- Journal Article
- Citation:
- Experimental Mathematics, 2015, 24 (4), pp. 391 - 409
- Issue Date:
- 2015-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Copyright © 2014 Taylor & Francis Group, LLC. We describe a Metropolis Monte Carlo algorithm for random sampling of freely reduced words equal to the identity in a finitely presented group. The algorithm samples from a stretched Boltzmann distribution π(w)=(|w|+1)αβ|w|· Z-1 where |w| is the length of a word w, α and β are parameters of the algorithm, and Z is a normalizing constant. It follows that words of the same length are sampled with the same probability. The distribution can be expressed in terms of the cogrowth series of the group, which allows us to relate statistical properties of words sampled by the algorithm to the cogrowth of the group, and hence its amenability. We have implemented the algorithm and applied it to several group presentations including the Baumslag-Solitar groups, some free products studied by Kouksov, a finitely presented amenable group that is not subexponentially amenable (based on the basilica group), the genus 2 surface group, and Richard Thompsons group F.
Please use this identifier to cite or link to this item: