A Central Limit Theorem for the Length of the Longest Common Subsequence in Random Words

Christian Houdré, Ümit Işlak

Published 2014-08-07, updated 2014-09-12Version 2

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. Let $LC_n$ be the length of longest common subsequences in the two 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 limiting distribution of the length of longest common subsequences in two independent uniform random permutations of $\{1, \dots, n\}$, which is shown to be the Tracy-Widom distribution.