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

Abstract

Let $X=(X_i{)}_{i\ge 1}$ and $Y=(Y_i{)}_{i\ge 1}$ be two sequences of independent and identically distributed (iid) random variables taking their values, uniformly, in a common totally ordered finite alphabet. Let LCI${}_n$ be the length of the longest common and (weakly) increasing subsequence of $X_1\cdots X_n$ and $Y_1\cdots Y_n$. As $n$ grows without bound, and when properly centered and normalized, LCI${}_n$ is shown to converge, in distribution, towards a Brownian functional that we identify.

Some corrections from the published version are provided, some typos are also corrected

References in corpus (2)

• A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
• GUE minors, maximal Brownian functionals and longest increasing subsequences

Cited by in corpus (2)

• A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distributions