A probabilistic approach to the asymptotics of the length of the longest alternating subsequence (Q612956)

From MaRDI portal
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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references