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

Let (Xk)k≥1 and (Yk)k≥1 be two independent sequences of inde-pendent identically distributed random variables having the same law and taking their values in a finite alphabet. Let LCn be the length of longest common subsequences in the two random words X1 · · ·Xn and Y1 · · ·Yn. Under assumptions on the distribution of X1, LCn 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,..., n}, which is shown to be the Tracy-Widom distribution