Geodesic
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
The electronic journal of combinatorics, Tome 17 (2010)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
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.
DOI : 10.37236/440
Classification : 60C05, 60F05, 60G15, 60G17, 05A16
Mots-clés : longest alternating subsequence, random permutations, random words, \(m\)-dependence, central limit theorem, law of the iterated logarithm 
Christian Houdré; Ricardo Restrepo. A probabilistic approach to the asymptotics of the length of the longest alternating subsequence. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/440
@article{10_37236_440,
     author = {Christian Houdr\'e and Ricardo Restrepo},
     title = {A probabilistic approach to the asymptotics of the length of the longest alternating subsequence},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/440},
     zbl = {1203.60013},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/440/}
}
TY  - JOUR
AU  - Christian Houdré
AU  - Ricardo Restrepo
TI  - A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/440/
DO  - 10.37236/440
ID  - 10_37236_440
ER  - 
%0 Journal Article
%A Christian Houdré
%A Ricardo Restrepo
%T A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/440/
%R 10.37236/440
%F 10_37236_440

Cité par Sources :