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

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:127

Article

Breton, Jean-Christophe¹  Houdre, Christian² 

[1] Univ Rennes 1, IRMAR, UMR 6625, 263 Ave Gen Leclerc CS 74205, F-35042 Rennes, France

[2] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

关键词: Longest common subsequence;    Longest increasing subsequence;    Random words;    Random matrices;    Donsker's theorem;    Optimal alignment;    Last passage percolation;   

DOI  :  10.1016/j.spa.2016.09.005

来源: Elsevier

【 摘 要 】

Let X = (X-i)(i >= 1) and Y = (Y-i)(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 X-1 center dot center dot center dot X-n and Y-1 center dot center dot center dot Y-n. 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. (C) 2016 Elsevier B.V. All rights reserved.

【 授权许可】

Free