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.

Detomi, E., Lucchini, A., Morigi, M. (2016). The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups. JOURNAL OF ALGEBRA, 468, 49-71 [10.1016/j.jalgebra.2016.08.008].

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

MORIGI, MARTA
2016

Abstract

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
Detomi, E., Lucchini, A., Morigi, M. (2016). The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups. JOURNAL OF ALGEBRA, 468, 49-71 [10.1016/j.jalgebra.2016.08.008].
Detomi, Eloisa; Lucchini, Andrea; Morigi, Marta
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/570332
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact