Sampling elements of a finite group: efficiency of the product replacement algorithm with...

Piotr Mizerka (Faculty of Mathematics and Computer Science of Adam Mickiewicz U… https://simons.berkeley.edu/talks/piotr-mizerka-faculty-mathematics-computer-science-adam-mickiewicz-university-poznan-2026-09 Local to Global Principles We study a refinement of the product replacement algorithm that is designed to output individual elements of a finite group $G$ in a random way. We show after how many steps, the distribution of the output is close to uniform on $G$. The proof proceeds via spectral gap estimates and uses computer assisted calculations. This is a joint work with Michał Marcinkowski.