English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 maximum locaux consécutifs.

Local extrema in random permutations and the structure of longest alternating subsequences