The product replacement algorithm is polynomial

The product replacement algorithm is a heuristic designed to generate random group elements. The idea is to run a random walk on generating κ-tuples of the group, and then output a random component. The algorithm was designed by C.R. Leedham-Green, and further investigated by F. Cellar et al. (1995). It was found to have an outstanding performance, much better than the previously known algorithms (P. Diaconis and L. Saloff-Coste, 1996). The algorithm is now included in two major group algebra packages: GAP (M. Scheonert et al., 1995) and MAGMA (W. Bosma et al., 1997). In spite of the many serious attempts and partial results, the analysis of the algorithm remains difficult at best. For small values of κ, even graph connectivity becomes a serious obstacle. The most general results are due to Diaconis and Saloff-Coste, who used a state of the art analytic technique to obtain polynomial bounds in special cases, and (sub)-exponential bounds in the general case. The main result of the paper is a polynomial upper bound for the cost of the algorithm, provided κ is large enough