On the limiting law of the length of the longest common and increasing subsequences in random words

Jean-Christophe Breton and Christian Houdré

Stochastic Processes and their Applications, 2017, vol. 127, issue 5, 1676-1720

Abstract: Let X=(Xi)i≥1 and Y=(Yi)i≥1 be two sequences of independent and identically distributed (iid) random variables taking their values, uniformly, in a common totally ordered finite alphabet. Let LCIn be the length of the longest common and (weakly) increasing subsequence of X1⋯Xn and Y1⋯Yn. As n grows without bound, and when properly centered and scaled, LCIn is shown to converge, in distribution, towards a Brownian functional that we identify.

Keywords: Longest common subsequence; Longest increasing subsequence; Random words; Random matrices; Donsker’s theorem; Optimal alignment; Last passage percolation (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414916301557
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:127:y:2017:i:5:p:1676-1720

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2016.09.005

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().