An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916347833745408 |
|---|---|
| author | Godbole, Anant Swickheimer, Hannah |
| author_facet | Godbole, Anant Swickheimer, Hannah |
| contents | Let $π_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, the authors of a recent paper showed that the expected number of distinct consecutive patterns of all lengths $k\in\{1,2,\ldots,n\}$ in $π_n$ is $\frac{n^2}{2}(1-o(1))$ as $n\to\infty$. This exhibited the fact that random permutations pack consecutive patterns near-perfectly. We use entirely different methods, namely the Stein-Chen method of Poisson approximation, to reprove and slightly improve their result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_14071 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation Godbole, Anant Swickheimer, Hannah Combinatorics Probability 05A99, 60C05 Let $π_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, the authors of a recent paper showed that the expected number of distinct consecutive patterns of all lengths $k\in\{1,2,\ldots,n\}$ in $π_n$ is $\frac{n^2}{2}(1-o(1))$ as $n\to\infty$. This exhibited the fact that random permutations pack consecutive patterns near-perfectly. We use entirely different methods, namely the Stein-Chen method of Poisson approximation, to reprove and slightly improve their result. |
| title | An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation |
| topic | Combinatorics Probability 05A99, 60C05 |
| url | https://arxiv.org/abs/2310.14071 |