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

Stochastics Seminar
Thursday, September 4, 2014 - 15:05
1 hour (actually 50 minutes)
Skiles 006
School of Mathematics, Georgia Tech
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 with Umit Islak)