کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4583657 1630446 2016 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
The limiting distribution of the product replacement algorithm for finitely generated prosoluble groups
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algebra - Volume 468, 15 December 2016, Pages 49–71
نویسندگان
, , ,