Random Sampling of Trivial Words in Finitely Presented Groups
| Autor: | Andrew Rechnitzer, Murray Elder, Esaias J. Janse van Rensburg |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Experimental Mathematics. 24:391-409 |
| ISSN: | 1944-950X 1058-6458 |
| DOI: | 10.1080/10586458.2015.1005853 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|