A Probabilistic Approach to the Asymptotics of the Length of the Longest Alternating Subsequence

Citations Over TimeTop 11% of 2010 papers

Abstract

Let $LA_{n}(\tau)$ be the length of the longest alternating subsequence of a uniform random permutation $\tau\in\left[ n\right] $. Classical probabilistic arguments are used to rederive the asymptotic mean, variance and limiting law of $LA_{n}\left( \tau\right) $. Our methodology is robust enough to tackle similar problems for finite alphabet random words or even Markovian sequences in which case our results are mainly original. A sketch of how some cases of pattern restricted permutations can also be tackled with probabilistic methods is finally presented.

Related Papers

• → On Two Variants of the Longest Increasing Subsequence Problem(2009)7 cited
• → The Longest Subsequence-Repeated Subsequence Problem(2023)4 cited
• → Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem(2010)3 cited
• → The Constrained Longest Common Subsequence Problem for Degenerate Strings(2007)4 cited
• → Longest (Sub-)Periodic Subsequence(2022)1 cited