Random Sampling of Trivial Words in Finitely Presented Groups

Abstract

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 $$\begin{array}{cc}\hfill \pi \left(w\right)& ={\left(\right|w|+1)}^{\alpha }{\beta }^{\left|w\right|}·Z^{-1}\hfill \end{array}$$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 Thompson’s group F.

2000 AMS Subject Classification::

• 20F69
• 20F65
• 05A15
• 60J20

Keywords:

• cogrowth
• spectral radius
• amenable group
• Metropolis algorithm
• Baumslag–Solitar group
• R. Thompson’s group F

Notes

¹Available at http://www.gnu.org/software/gsl/ at the time of writing.