DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.15

Cycle Structure of Random Standardized Permutations

Authors: Aurélien Guerder

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

In this article, we study a model of random permutations, which we call random standardized permutations, and which is based on a sequence of i.i.d. random variables. This model generalizes other ones, such as the riffle shuffle and the major-index-biased permutations. We first establish an exact result on the joint distribution of the number of cycles of given lengths, involving the notion of primitive words. From this result, we obtain various convergence results, most of which are proved using the method of moments. We prove that the number of small cycles may have either a Poisson limit distribution, or a limit distribution given by a countable sum of independent geometric distributions. Then, we establish a limit distribution for large cycles, which is the Poisson-Dirichlet process. Finally, we prove a central limit theorem for the total number of cycles.

Cite as

Aurélien Guerder. Cycle Structure of Random Standardized Permutations. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{guerder:LIPIcs.AofA.2026.15,
  author =	{Guerder, Aur\'{e}lien},
  title =	{{Cycle Structure of Random Standardized Permutations}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.15},
  URN =		{urn:nbn:de:0030-drops-262864},
  doi =		{10.4230/LIPIcs.AofA.2026.15},
  annote =	{Keywords: Random permutations, primitive words, combinatorics, asymptotic distribution, method of moments}
}

Search Results

Documents authored by Guerder, Aurélien

Cycle Structure of Random Standardized Permutations

Abstract

Cite as

Thanks for your feedback!

Could not send message