The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups (Q324208): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:59, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups |
scientific article |
Statements
The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups (English)
0 references
10 October 2016
0 references
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.
0 references
probability distributions
0 references
product replacement algorithm
0 references
pro-soluble groups.
0 references