Dan Romik
-
Local extrema in random permutations and the structure of longest alternating subsequences
dmtcs:2956 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2011,
DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
-
https://doi.org/10.46298/dmtcs.2956
Local extrema in random permutations and the structure of longest alternating subsequencesArticle
Authors: Dan Romik 1
NULL
Dan Romik
1 Department of Mathematics [Univ California Davis]
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}$.
CAREER: Combinatorial probability, limit shapes and enumeration; Funder: National Science Foundation; Code: 0955584
Bibliographic References
2 Documents citing this article
İlker Arslan;Ümit Işlak;Cihan Pehlivan, 2018, On unfair permutations, Statistics & Probability Letters, 141, pp. 31-40, 10.1016/j.spl.2018.05.011.
Igor Pak;Robin Pemantle, 2015, On the Longest $k$-Alternating Subsequence, The Electronic Journal of Combinatorics, 22, 1, 10.37236/4480, https://doi.org/10.37236/4480.