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

preprint2012arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.