Counting records in a random, non-uniform, permutation
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910781914742784 |
|---|---|
| author | Pittel, Boris |
| author_facet | Pittel, Boris |
| contents | Counting permutations of $[n]$ by the number of records, i.e. left-to-right maxima, is a classic problem in combinatorial enumeration. In the first volume of ``The Art of Computer Programming", Donald Knuth demonstrated its relevance for analysis of average case complexity of a basic algorithm for determining a maximum in a linear list of numbers. It is well known that the expected, and likely, number of those records in a {\it uniformly\/} random permutation is asymptotic to $\log n$. Cyril Banderier, Rene Beier, and Kurt Mehlhorn studied the case of a non-uniform random permutation, which is obtained from a generic permutation of $[n]$ by selecting its elements one after another independently with probability $p$, and permuting the selected elements uniformly at random. They proved that $E_n(p)$, the largest expected number of the maxima, is between $\text{const}\sqrt{n/p}$ and $O\bigl(\sqrt{(n/p)\log n}\bigr)$ if $p$ is fixed. For $p\gg 1/n$ and simultaneously $1-p\ge \text{const }n^{-1/2}\log n$, we prove that $E_n(p)$ is exactly of order $(1-p)\sqrt{n/p}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06905 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting records in a random, non-uniform, permutation Pittel, Boris Combinatorics 60C05, 05C05, 92510 Counting permutations of $[n]$ by the number of records, i.e. left-to-right maxima, is a classic problem in combinatorial enumeration. In the first volume of ``The Art of Computer Programming", Donald Knuth demonstrated its relevance for analysis of average case complexity of a basic algorithm for determining a maximum in a linear list of numbers. It is well known that the expected, and likely, number of those records in a {\it uniformly\/} random permutation is asymptotic to $\log n$. Cyril Banderier, Rene Beier, and Kurt Mehlhorn studied the case of a non-uniform random permutation, which is obtained from a generic permutation of $[n]$ by selecting its elements one after another independently with probability $p$, and permuting the selected elements uniformly at random. They proved that $E_n(p)$, the largest expected number of the maxima, is between $\text{const}\sqrt{n/p}$ and $O\bigl(\sqrt{(n/p)\log n}\bigr)$ if $p$ is fixed. For $p\gg 1/n$ and simultaneously $1-p\ge \text{const }n^{-1/2}\log n$, we prove that $E_n(p)$ is exactly of order $(1-p)\sqrt{n/p}$. |
| title | Counting records in a random, non-uniform, permutation |
| topic | Combinatorics 60C05, 05C05, 92510 |
| url | https://arxiv.org/abs/2501.06905 |