2013/12/19 by Murray Elder, M. Elder, Elder, M. +6
Computer Science · Mathematics · Physics and Astronomy · #05A15 #20F65 #20F69 #60J20 #Complex Network Analysis Techniques #FOS: Mathematics #Group Theory (math.GR) #Probability (math.PR) #Theoretical and Computational Physics #Topological and Geometric Data Analysis #math.GR #math.PR #msc:05A15 #msc:20F65 #msc:20F69 #msc:60J20
paper · pdf · doi:10.48550/arxiv.1312.5722
28 pages, 9 figures. This article supersedes arXiv:1210.3425
openalex publication_date 2013/12/19 · arxiv created 2013/12/20 · arxiv updated 2013/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe a novel algorithm for random sampling of freely reduced words equal to the identity in a finitely presented group. The algorithm is based on Metropolis Monte Carlo sampling. 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 normalising 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 then 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), and Richard Thompson's group F.