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

2019/06/15 by Deslandes, Clément, Houdré, Christian
#05A05 #60505 #60C05 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1906.06544

Abstract

Let (X_k)_{k≥ 1} and (Y_k)_{k≥ 1} be two independent sequences of i.i.d. random variables, with values in a finite and totally ordered alphabet A_m:=\1,…,m\, and having respective probability mass function p^X₁,…,p^X_m and p^Y₁,…,p^Y_m. Let LCI_n be the length of the longest common and weakly increasing subsequences in (X₁,...,X_n) and (Y₁,...,Y_n). Once properly centered and normalized, LCI_n is shown to have a limiting distribution which is expressed as a functional of two independent multidimensional Brownian motions.

Related

• On the Longest Increasing Subsequence for Finite and Countable Alphabets
• Repetition-free longest common subsequence of random sequences
• Longest common subsequences between words of very unequal length
• Length of the longest common subsequence between overlapping words
• Expected length of the longest common subsequence for large alphabets