Local extrema in random permutations and the structure of longest alternating subsequences
International audience Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and $\te...
Published in: | Discrete Mathematics & Theoretical Computer Science |
---|---|
Main Author: | |
Other Authors: | , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01215067 https://hal.inria.fr/hal-01215067/document https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf https://doi.org/10.46298/dmtcs.2956 |
id |
ftunivnantes:oai:HAL:hal-01215067v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivnantes:oai:HAL:hal-01215067v1 2023-05-15T16:52:48+02:00 Local extrema in random permutations and the structure of longest alternating subsequences Romik, Dan Department of Mathematics Univ California Davis (MATH - UC Davis) University of California Davis (UC Davis) University of California (UC)-University of California (UC) Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://hal.inria.fr/hal-01215067 https://hal.inria.fr/hal-01215067/document https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf https://doi.org/10.46298/dmtcs.2956 en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2956 hal-01215067 https://hal.inria.fr/hal-01215067 https://hal.inria.fr/hal-01215067/document https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf doi:10.46298/dmtcs.2956 info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215067 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.825-834, ⟨10.46298/dmtcs.2956⟩ longest alternating subsequences permutation statistics random permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftunivnantes https://doi.org/10.46298/dmtcs.2956 2022-11-30T02:07:25Z International audience Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. From Stanley's result it can be shown that after rescaling, $\textbf{as}_n$ converges in the limit to the Gaussian distribution. In this extended abstract we present a new approach to the study of $\textbf{as}_n$ by relating it to the sequence of local extrema of a random permutation, which is shown to form a "canonical'' longest alternating subsequence. Using this connection we reprove the abovementioned results in a more probabilistic and transparent way. We also study the distribution of the values of the local minima and maxima, and prove that in the limit the joint distribution of successive minimum-maximum pairs converges to the two-dimensional distribution whose density function is given by $f(s,t) = 3(1-s)t e^{t-s}$. Pour une permutation aléatoire d'ordre $n$, on désigne par $\textbf{as}_n$ la longueur maximale d'une de ses sous-suites alternantes. Stanley a étudié la distribution de $\textbf{as}_n$ en utilisant des méthodes algébriques, et il a démontré en particulier que $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ et $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. A partir du résultat de Stanley on peut montrer qu'après changement d'échelle, $\textbf{as}_n$ converge vers la distribution normale. Nous présentons ici une approche nouvelle pour l'étude de $\textbf{as}_n$, en la reliant à la suite des extrema locaux d'une permutation aléatoire, dont nous montrons qu'elle constitue une sous-suite alternante maximale "canonique''. En utilisant cette relation, nous prouvons à nouveau les résultats mentionnés ci-dessus d'une façon plus probabiliste et transparente. En plus, nous prouvons un résultat asymptotique sur la distribution limite des paires formées d'un minimum et d'un ... Conference Object Iceland Université de Nantes: HAL-UNIV-NANTES Discrete Mathematics & Theoretical Computer Science DMTCS Proceeding Proceedings |
institution |
Open Polar |
collection |
Université de Nantes: HAL-UNIV-NANTES |
op_collection_id |
ftunivnantes |
language |
English |
topic |
longest alternating subsequences permutation statistics random permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
spellingShingle |
longest alternating subsequences permutation statistics random permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Romik, Dan Local extrema in random permutations and the structure of longest alternating subsequences |
topic_facet |
longest alternating subsequences permutation statistics random permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
description |
International audience Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. From Stanley's result it can be shown that after rescaling, $\textbf{as}_n$ converges in the limit to the Gaussian distribution. In this extended abstract we present a new approach to the study of $\textbf{as}_n$ by relating it to the sequence of local extrema of a random permutation, which is shown to form a "canonical'' longest alternating subsequence. Using this connection we reprove the abovementioned results in a more probabilistic and transparent way. We also study the distribution of the values of the local minima and maxima, and prove that in the limit the joint distribution of successive minimum-maximum pairs converges to the two-dimensional distribution whose density function is given by $f(s,t) = 3(1-s)t e^{t-s}$. Pour une permutation aléatoire d'ordre $n$, on désigne par $\textbf{as}_n$ la longueur maximale d'une de ses sous-suites alternantes. Stanley a étudié la distribution de $\textbf{as}_n$ en utilisant des méthodes algébriques, et il a démontré en particulier que $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ et $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. A partir du résultat de Stanley on peut montrer qu'après changement d'échelle, $\textbf{as}_n$ converge vers la distribution normale. Nous présentons ici une approche nouvelle pour l'étude de $\textbf{as}_n$, en la reliant à la suite des extrema locaux d'une permutation aléatoire, dont nous montrons qu'elle constitue une sous-suite alternante maximale "canonique''. En utilisant cette relation, nous prouvons à nouveau les résultats mentionnés ci-dessus d'une façon plus probabiliste et transparente. En plus, nous prouvons un résultat asymptotique sur la distribution limite des paires formées d'un minimum et d'un ... |
author2 |
Department of Mathematics Univ California Davis (MATH - UC Davis) University of California Davis (UC Davis) University of California (UC)-University of California (UC) Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel |
format |
Conference Object |
author |
Romik, Dan |
author_facet |
Romik, Dan |
author_sort |
Romik, Dan |
title |
Local extrema in random permutations and the structure of longest alternating subsequences |
title_short |
Local extrema in random permutations and the structure of longest alternating subsequences |
title_full |
Local extrema in random permutations and the structure of longest alternating subsequences |
title_fullStr |
Local extrema in random permutations and the structure of longest alternating subsequences |
title_full_unstemmed |
Local extrema in random permutations and the structure of longest alternating subsequences |
title_sort |
local extrema in random permutations and the structure of longest alternating subsequences |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/hal-01215067 https://hal.inria.fr/hal-01215067/document https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf https://doi.org/10.46298/dmtcs.2956 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215067 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.825-834, ⟨10.46298/dmtcs.2956⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2956 hal-01215067 https://hal.inria.fr/hal-01215067 https://hal.inria.fr/hal-01215067/document https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf doi:10.46298/dmtcs.2956 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.46298/dmtcs.2956 |
container_title |
Discrete Mathematics & Theoretical Computer Science |
container_volume |
DMTCS Proceeding |
container_issue |
Proceedings |
_version_ |
1766043231009636352 |