A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
ABSTRACT: 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...
- Autores:
-
Restrepo López, Ricardo
Houdré, Christian
- Tipo de recurso:
- Article of investigation
- Fecha de publicación:
- 2010
- Institución:
- Universidad de Antioquia
- Repositorio:
- Repositorio UdeA
- Idioma:
- eng
- OAI Identifier:
- oai:bibliotecadigital.udea.edu.co:10495/40130
- Acceso en línea:
- https://hdl.handle.net/10495/40130
- Palabra clave:
- Teorema del límite central
Central limit theorem
Logaritmos
Logarithms
Longest alternating subsequence
Random permutations
Random words
M-dependence
http://id.loc.gov/authorities/subjects/sh85021905
http://id.loc.gov/authorities/subjects/sh85078091
- Rights
- openAccess
- License
- https://creativecommons.org/licenses/by-nc-sa/4.0/
| id |
UDEA2_fcd178d6ada9c7185c4d9a051161b606 |
|---|---|
| oai_identifier_str |
oai:bibliotecadigital.udea.edu.co:10495/40130 |
| network_acronym_str |
UDEA2 |
| network_name_str |
Repositorio UdeA |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence |
| title |
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence |
| spellingShingle |
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence Teorema del límite central Central limit theorem Logaritmos Logarithms Longest alternating subsequence Random permutations Random words M-dependence http://id.loc.gov/authorities/subjects/sh85021905 http://id.loc.gov/authorities/subjects/sh85078091 |
| title_short |
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence |
| title_full |
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence |
| title_fullStr |
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence |
| title_full_unstemmed |
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence |
| title_sort |
A probabilistic approach to the asymptotics of the length of the longest alternating subsequence |
| dc.creator.fl_str_mv |
Restrepo López, Ricardo Houdré, Christian |
| dc.contributor.author.none.fl_str_mv |
Restrepo López, Ricardo Houdré, Christian |
| dc.contributor.researchgroup.spa.fl_str_mv |
Análisis Numérico y Financiero: Matemáticas aplicadas para la industria |
| dc.subject.lcsh.none.fl_str_mv |
Teorema del límite central Central limit theorem Logaritmos Logarithms |
| topic |
Teorema del límite central Central limit theorem Logaritmos Logarithms Longest alternating subsequence Random permutations Random words M-dependence http://id.loc.gov/authorities/subjects/sh85021905 http://id.loc.gov/authorities/subjects/sh85078091 |
| dc.subject.proposal.spa.fl_str_mv |
Longest alternating subsequence Random permutations Random words M-dependence |
| dc.subject.lcshuri.none.fl_str_mv |
http://id.loc.gov/authorities/subjects/sh85021905 http://id.loc.gov/authorities/subjects/sh85078091 |
| description |
ABSTRACT: 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. |
| publishDate |
2010 |
| dc.date.issued.none.fl_str_mv |
2010 |
| dc.date.accessioned.none.fl_str_mv |
2024-06-18T20:40:32Z |
| dc.date.available.none.fl_str_mv |
2024-06-18T20:40:32Z |
| dc.type.spa.fl_str_mv |
Artículo de investigación |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.redcol.spa.fl_str_mv |
https://purl.org/redcol/resource_type/ART |
| dc.type.coarversion.spa.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/article |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| format |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| status_str |
publishedVersion |
| dc.identifier.uri.none.fl_str_mv |
https://hdl.handle.net/10495/40130 |
| dc.identifier.doi.none.fl_str_mv |
10.37236/440 |
| dc.identifier.eissn.none.fl_str_mv |
1077-8926 |
| url |
https://hdl.handle.net/10495/40130 |
| identifier_str_mv |
10.37236/440 1077-8926 |
| dc.language.iso.spa.fl_str_mv |
eng |
| language |
eng |
| dc.relation.ispartofjournalabbrev.spa.fl_str_mv |
Electron. J. Comb. |
| dc.relation.citationendpage.spa.fl_str_mv |
18 |
| dc.relation.citationstartpage.spa.fl_str_mv |
1 |
| dc.relation.citationvolume.spa.fl_str_mv |
17 |
| dc.relation.ispartofjournal.spa.fl_str_mv |
Electronic Journal of Combinatorics |
| dc.rights.uri.spa.fl_str_mv |
https://creativecommons.org/licenses/by-nc-sa/4.0/ |
| dc.rights.uri.*.fl_str_mv |
http://creativecommons.org/licenses/by-nc-sa/2.5/co/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
https://creativecommons.org/licenses/by-nc-sa/4.0/ http://creativecommons.org/licenses/by-nc-sa/2.5/co/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.spa.fl_str_mv |
19 páginas |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Electronic Journal of Combinatorics |
| dc.publisher.place.spa.fl_str_mv |
Atlanta, Estados Unidos |
| institution |
Universidad de Antioquia |
| bitstream.url.fl_str_mv |
https://bibliotecadigital.udea.edu.co/bitstreams/4320e5a0-38b1-44ab-8d0e-d1820447600e/download https://bibliotecadigital.udea.edu.co/bitstreams/48f699ca-32ab-4cc6-a76c-b019af6f5a4d/download https://bibliotecadigital.udea.edu.co/bitstreams/3a79e871-f5dc-4332-862f-16b2a5d8e106/download https://bibliotecadigital.udea.edu.co/bitstreams/05437351-2e2a-418c-beee-7efd08087f6f/download https://bibliotecadigital.udea.edu.co/bitstreams/f4cc3516-57be-41ac-853c-e677503517e6/download |
| bitstream.checksum.fl_str_mv |
a976882cad9fad4276ad73dfcab03700 e2060682c9c70d4d30c83c51448f4eed 8a4605be74aa9ea9d79846c1fba20a33 79ea1886757ca90ee7643ee5d045e0fc a7efca993a95703ac4105dc83c7f32b5 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional de la Universidad de Antioquia |
| repository.mail.fl_str_mv |
aplicacionbibliotecadigitalbiblioteca@udea.edu.co |
| _version_ |
1851052385651130368 |
| spelling |
Restrepo López, RicardoHoudré, ChristianAnálisis Numérico y Financiero: Matemáticas aplicadas para la industria2024-06-18T20:40:32Z2024-06-18T20:40:32Z2010https://hdl.handle.net/10495/4013010.37236/4401077-8926ABSTRACT: 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.COL010637119 páginasapplication/pdfengElectronic Journal of CombinatoricsAtlanta, Estados Unidoshttps://creativecommons.org/licenses/by-nc-sa/4.0/http://creativecommons.org/licenses/by-nc-sa/2.5/co/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Teorema del límite centralCentral limit theoremLogaritmosLogarithmsLongest alternating subsequenceRandom permutationsRandom wordsM-dependencehttp://id.loc.gov/authorities/subjects/sh85021905http://id.loc.gov/authorities/subjects/sh85078091A probabilistic approach to the asymptotics of the length of the longest alternating subsequenceArtículo de investigaciónhttp://purl.org/coar/resource_type/c_2df8fbb1https://purl.org/redcol/resource_type/ARThttp://purl.org/coar/version/c_970fb48d4fbd8a85info:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionElectron. J. Comb.18117Electronic Journal of CombinatoricsPublicationORIGINALRestrepoRicardo_2010_ProbabilisticApproachAsymptotics.pdfRestrepoRicardo_2010_ProbabilisticApproachAsymptotics.pdfArtículo de investigaciónapplication/pdf3009061https://bibliotecadigital.udea.edu.co/bitstreams/4320e5a0-38b1-44ab-8d0e-d1820447600e/downloada976882cad9fad4276ad73dfcab03700MD51trueAnonymousREADCC-LICENSElicense_rdflicense_rdfapplication/rdf+xml; charset=utf-81051https://bibliotecadigital.udea.edu.co/bitstreams/48f699ca-32ab-4cc6-a76c-b019af6f5a4d/downloade2060682c9c70d4d30c83c51448f4eedMD52falseAnonymousREADLICENSElicense.txtlicense.txttext/plain; charset=utf-81748https://bibliotecadigital.udea.edu.co/bitstreams/3a79e871-f5dc-4332-862f-16b2a5d8e106/download8a4605be74aa9ea9d79846c1fba20a33MD53falseAnonymousREADTEXTRestrepoRicardo_2010_ProbabilisticApproachAsymptotics.pdf.txtRestrepoRicardo_2010_ProbabilisticApproachAsymptotics.pdf.txtExtracted texttext/plain38https://bibliotecadigital.udea.edu.co/bitstreams/05437351-2e2a-418c-beee-7efd08087f6f/download79ea1886757ca90ee7643ee5d045e0fcMD54falseAnonymousREADTHUMBNAILRestrepoRicardo_2010_ProbabilisticApproachAsymptotics.pdf.jpgRestrepoRicardo_2010_ProbabilisticApproachAsymptotics.pdf.jpgGenerated Thumbnailimage/jpeg10760https://bibliotecadigital.udea.edu.co/bitstreams/f4cc3516-57be-41ac-853c-e677503517e6/downloada7efca993a95703ac4105dc83c7f32b5MD55falseAnonymousREAD10495/40130oai:bibliotecadigital.udea.edu.co:10495/401302025-03-26 21:29:05.834https://creativecommons.org/licenses/by-nc-sa/4.0/open.accesshttps://bibliotecadigital.udea.edu.coRepositorio Institucional de la Universidad de Antioquiaaplicacionbibliotecadigitalbiblioteca@udea.edu.coTk9URTogUExBQ0UgWU9VUiBPV04gTElDRU5TRSBIRVJFClRoaXMgc2FtcGxlIGxpY2Vuc2UgaXMgcHJvdmlkZWQgZm9yIGluZm9ybWF0aW9uYWwgcHVycG9zZXMgb25seS4KCk5PTi1FWENMVVNJVkUgRElTVFJJQlVUSU9OIExJQ0VOU0UKCkJ5IHNpZ25pbmcgYW5kIHN1Ym1pdHRpbmcgdGhpcyBsaWNlbnNlLCB5b3UgKHRoZSBhdXRob3Iocykgb3IgY29weXJpZ2h0Cm93bmVyKSBncmFudHMgdG8gRFNwYWNlIFVuaXZlcnNpdHkgKERTVSkgdGhlIG5vbi1leGNsdXNpdmUgcmlnaHQgdG8gcmVwcm9kdWNlLAp0cmFuc2xhdGUgKGFzIGRlZmluZWQgYmVsb3cpLCBhbmQvb3IgZGlzdHJpYnV0ZSB5b3VyIHN1Ym1pc3Npb24gKGluY2x1ZGluZwp0aGUgYWJzdHJhY3QpIHdvcmxkd2lkZSBpbiBwcmludCBhbmQgZWxlY3Ryb25pYyBmb3JtYXQgYW5kIGluIGFueSBtZWRpdW0sCmluY2x1ZGluZyBidXQgbm90IGxpbWl0ZWQgdG8gYXVkaW8gb3IgdmlkZW8uCgpZb3UgYWdyZWUgdGhhdCBEU1UgbWF5LCB3aXRob3V0IGNoYW5naW5nIHRoZSBjb250ZW50LCB0cmFuc2xhdGUgdGhlCnN1Ym1pc3Npb24gdG8gYW55IG1lZGl1bSBvciBmb3JtYXQgZm9yIHRoZSBwdXJwb3NlIG9mIHByZXNlcnZhdGlvbi4KCllvdSBhbHNvIGFncmVlIHRoYXQgRFNVIG1heSBrZWVwIG1vcmUgdGhhbiBvbmUgY29weSBvZiB0aGlzIHN1Ym1pc3Npb24gZm9yCnB1cnBvc2VzIG9mIHNlY3VyaXR5LCBiYWNrLXVwIGFuZCBwcmVzZXJ2YXRpb24uCgpZb3UgcmVwcmVzZW50IHRoYXQgdGhlIHN1Ym1pc3Npb24gaXMgeW91ciBvcmlnaW5hbCB3b3JrLCBhbmQgdGhhdCB5b3UgaGF2ZQp0aGUgcmlnaHQgdG8gZ3JhbnQgdGhlIHJpZ2h0cyBjb250YWluZWQgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWxzbyByZXByZXNlbnQKdGhhdCB5b3VyIHN1Ym1pc3Npb24gZG9lcyBub3QsIHRvIHRoZSBiZXN0IG9mIHlvdXIga25vd2xlZGdlLCBpbmZyaW5nZSB1cG9uCmFueW9uZSdzIGNvcHlyaWdodC4KCklmIHRoZSBzdWJtaXNzaW9uIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCB5b3UgZG8gbm90IGhvbGQgY29weXJpZ2h0LAp5b3UgcmVwcmVzZW50IHRoYXQgeW91IGhhdmUgb2J0YWluZWQgdGhlIHVucmVzdHJpY3RlZCBwZXJtaXNzaW9uIG9mIHRoZQpjb3B5cmlnaHQgb3duZXIgdG8gZ3JhbnQgRFNVIHRoZSByaWdodHMgcmVxdWlyZWQgYnkgdGhpcyBsaWNlbnNlLCBhbmQgdGhhdApzdWNoIHRoaXJkLXBhcnR5IG93bmVkIG1hdGVyaWFsIGlzIGNsZWFybHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkCndpdGhpbiB0aGUgdGV4dCBvciBjb250ZW50IG9mIHRoZSBzdWJtaXNzaW9uLgoKSUYgVEhFIFNVQk1JU1NJT04gSVMgQkFTRUQgVVBPTiBXT1JLIFRIQVQgSEFTIEJFRU4gU1BPTlNPUkVEIE9SIFNVUFBPUlRFRApCWSBBTiBBR0VOQ1kgT1IgT1JHQU5JWkFUSU9OIE9USEVSIFRIQU4gRFNVLCBZT1UgUkVQUkVTRU5UIFRIQVQgWU9VIEhBVkUKRlVMRklMTEVEIEFOWSBSSUdIVCBPRiBSRVZJRVcgT1IgT1RIRVIgT0JMSUdBVElPTlMgUkVRVUlSRUQgQlkgU1VDSApDT05UUkFDVCBPUiBBR1JFRU1FTlQuCgpEU1Ugd2lsbCBjbGVhcmx5IGlkZW50aWZ5IHlvdXIgbmFtZShzKSBhcyB0aGUgYXV0aG9yKHMpIG9yIG93bmVyKHMpIG9mIHRoZQpzdWJtaXNzaW9uLCBhbmQgd2lsbCBub3QgbWFrZSBhbnkgYWx0ZXJhdGlvbiwgb3RoZXIgdGhhbiBhcyBhbGxvd2VkIGJ5IHRoaXMKbGljZW5zZSwgdG8geW91ciBzdWJtaXNzaW9uLgo= |