The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups (Q324208): Difference between revisions

The classical product replacement algorithm proposed by \textit{F. Celler} et al. [Commun. Algebra 23, No. 13, 4931--4948 (1995; Zbl 0836.20094)] intended to rapidly generate nearly uniformly distributed random elements in a finite group \(G\) in the following way: choose \(t\) sufficiently larger than the rank (i.e., the minimal number of generators) of \(G\), then choose a \(t\)-tuple of generators \((g_1, \ldots ,g_t)\), and start a random walk in the set of all generating \(t\)-tuples by repeatedly choosing two different indices \(1\leq i, j\leq t\) and replacing \(g_i\) to either of \(g_ig_j\), \(g_ig_j^{-1}\), \(g_jg_i\) or \(g_j^{-1}g_i\); after sufficiently many steps, read off the first element in the resulting \(t\)-tuple. It can be proven that the distribution of the \(t\)-tuple obtained in this way converges rapidly to the uniform distribution on the set of generating \(t\)-tuples. However, \textit{L. Babai} and \textit{I. Pak} [in: Proceedings of the 11th annual ACM-SIAM symposium on discrete algorithms, SODA 2000. Philadelphia, PA: SIAM. 627--635 (2000; Zbl 1005.20055)] showed that the projection of the uniform distribution on generating \(t\)-tuples onto the first component need not give in general the uniform distribution on \(G\): they constructed 2-generated groups \(G\) for which one is far from the other even for \(t\) arbitrarily large. In the paper under review, the authors study the difference between these two distributions in \(G\), for the case where \(G\) is a finitely generated prosolvable group (having previously defined conveniently the two distribution for a profinite group \(G\) as appropriate inverse limits over the chain of all its finite quotients). Under the additional hypotheses of the derived subgroup being pronilpotent, they prove that this bias is bounded away from 1. However, even for solvable groups the Babai-Pak problem [loc. cit.] is unavoidable: they construct a sequence of finite solvable groups of derived length 4 for which the bias gets close to 1.