A probabilistic approach to the asymptotics of the length of the longest alternating subsequence (Q612956): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1785916 |
Changed an Item |
||
Property / author | |||
Property / author: Ricardo L. Restrepo / rank | |||
Normal rank |
Revision as of 11:48, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A probabilistic approach to the asymptotics of the length of the longest alternating subsequence |
scientific article |
Statements
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence (English)
0 references
16 December 2010
0 references
Summary: Let \(LA_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 \(LA_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.
0 references
longest alternating subsequence
0 references
random permutations
0 references
random words
0 references
\(m\)-dependence
0 references
central limit theorem
0 references
law of the iterated logarithm
0 references