A probabilistic approach to the asymptotics of the length of the longest alternating subsequence

Abstract

Let $L{A}_n(\tau )$ be the length of the longest alternating subsequence of a uniform random permutation $\tau \in [n]$. Classical probabilistic arguments are used to rederive the asymptotic mean, variance and limiting law of $L{A}_n(\tau )$. 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.

Final version with a new title and various extensions

References in corpus (2)

• Wavelet thresholding for nonnecessarily Gaussian noise: functionality
• On the Limiting Shape of Markovian Random Young Tableaux