Random Sampling of Trivial Words in Finitely Presented Groups

DOI10.1080/10586458.2015.1005853MaRDI QIDQ3194576zbMATH OpenOpenAlexFDO

Authors Andrew Rechnitzer, E. J. Janse van Rensburg, Murray Elder

Publication date 20 October 2015

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.5722, http://hdl.handle.net/10453/140081

zbMATH Keywords

amenable groupBaumslag-Solitar groupcogrowthmetropolis algorithmR. Thompson's group \(F\)spectral radius

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Geometric group theory (20F65) Asymptotic properties of groups (20F69) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Abstract: 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 �egin{align*}pi(w) &= (|w|+1)^{alpha} �eta^{|w|} cdot Z^{-1} end{align*} where $|w|$ is the length of a word $w$, $alpha$ 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$.

Recommendations

• On the distribution of random words in a compact Lie group
• The probability distribution of word maps on finite groups
• Words, Hausdorff dimension and randomly free groups
• Random generation of finite simple groups
• Random operator approach for word enumeration in braid groups
• On random permutations of finite groups
• Words and mixing times in finite simple groups.
• On representing words in the automorphism group of the random graph
• Words in linear groups, random walks, automata and P-recursiveness
• Probabilistic generation of finite simple groups

Cites work

• A computational approach to the Thompson group F
• A First Look at Rigorous Probability Theory
• Amenability via random walks.
• Cogrowth and amenability of discrete groups
• Cogrowth of groups and simple random walks
• Cogrowth series of free products of finite and free groups
• Cone types and geodesic languages for lamplighter groups and Thompson's group \(F\).
• Fast growth in the Følner function for Thompson's group \(F\).
• FOREST DIAGRAMS FOR ELEMENTS OF THOMPSON'S GROUP F
• scientific article; zbMATH DE number 3493681 (Why is no real title available?)
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• Monte Carlo methods for the self-avoiding walk
• Monte Carlo study of the interacting self-avoiding walk model in three dimensions.
• ON A TORSION-FREE WEAKLY BRANCH GROUP DEFINED BY A THREE STATE AUTOMATON
• On rationality of the cogrowth series
• On the cogrowth of Thompson's group F
• Probability and Computing
• Testing Cayley graph densities.
• The cogrowth series for BS(N, N) is D-finite

Cited in

(5)

• On the distribution of random words in a compact Lie group
• On a theorem of Avez
• Numerical studies of Thompson's group \(F\) and related groups
• Sub-dominant Cogrowth Behavior and the Viability of Deciding Amenability Numerically
• Computational Explorations of the Thompson Group T for the Amenability Problem of F

This page was built for publication: Random Sampling of Trivial Words in Finitely Presented Groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194576)