The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups (Q324208): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Enric Ventura Capell / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20F05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20P05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20F19 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20E18 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6636981 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
probability distributions | |||
Property / zbMATH Keywords: probability distributions / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
product replacement algorithm | |||
Property / zbMATH Keywords: product replacement algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pro-soluble groups. | |||
Property / zbMATH Keywords: pro-soluble groups. / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jalgebra.2016.08.008 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2510423341 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4952678 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generating random elements of a finite group / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Probability and Bias in Generating Supersoluble Groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bias of group generators in the solvable case. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bias of group generators in finite and profinite groups: known results and open problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Die Eulersche Funktion endlicher auflösbarer Gruppen / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: THE EULERIAN FUNCTIONS OF A GROUP / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The probability of generating a finite classical group / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generating wreath products / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The X-Dirichlet polynomial of a finite group / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the probability of generating prosoluble groups. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Positively finitely generated groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the probability of generating free prosoluble groups of small rank. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2759638 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A polynomial bound for the orders of primitive solvable groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Enumerating finite groups of given order / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Solvable and Nilpotent Subgroups of <i>GL</i>(<i>n</i>,<i>q</i><sup><i>m</i></sup>) / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 17:34, 12 July 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
0 references