On the Limiting Distribution of the Length of the Longest Common Subsequence

Abstract: Let (X_k)_{k \geq 1} and (Y_k)_{k\geq1} be two independent sequences of independent identically distributed random variables having the same law and taking their values in a finite alphabet \mathcal{A}_m. Let LC_n be the length of the longest common subsequence of the random words X_1\cdots X_n and Y_1\cdots Y_n. Under assumptions on the distribution of X_1, LC_n is shown to satisfy a central limit theorem. This is in contrast to the Bernoulli matching problem or to the random permutations case, where the limiting law is the Tracy-Widom one. (Joint work with Umit Islak)