The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups

Babai and Pak proved that the product replacement algorithm (a widely used heuristic algorithm intended to rapidly generate nearly uniformly distributed random elements in a finite group G) has a flaw. Indeed the projection of the uniform distribution on generating n-tuples onto the first component may not give the uniform distribution on elements of G. In this paper we examine the difference between this distribution and the uniform one, in the particular case when G is a finitely generated prosoluble group. Under some additional hypotheses (for example if the derived subgroup is pronilpotent), this bias is bounded away from 1. However even for soluble groups, the problem pointed out by Babai and Pak is unavoidable. We construct a sequence of finite soluble groups of derived length 4 for which the bias is close to 1. © 2016 Elsevier Inc.