The Variance and the Asymptotic Distribution of the Length of Longest k-alternating Subsequences

DOI10.46298/DMTCS.10296arXiv2107.12459OpenAlexW3186837486MaRDI QIDQ6131790FDOQ6131790

Authors: Yunus Emre Demirci, Ümit Işlak 

Publication date: 18 April 2024

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Abstract: We obtain an explicit formula for the variance of the number of $k$-peaks in a uniformly random permutation. This is then used to obtain an asymptotic formula for the variance of the length of longest $k$-alternating subsequence in random permutations. Also a central limit is proved for the latter statistic.

Full work available at URL: https://arxiv.org/abs/2107.12459

Recommendations

• On the limiting distribution for the length of the longest alternating sequence in a random permutation
• A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
• Local extrema in random permutations and the structure of longest alternating subsequences
• On increasing subsequences of random permutations
• Longest alternating subsequences of permutations

zbMATH Keywords

central limit theorempeak\(k\)-alternating subsequencesalternating subsequences

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Central limit and other weak theorems (60F05) Exact enumeration problems, generating functions (05A15)

This page was built for publication: The Variance and the Asymptotic Distribution of the Length of Longest $k$-alternating Subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131790)