A Central Limit Theorem for the Length of the Longest Common Subsequence in Random Words
Résumé
Let (X_k )_{k≥1} and (Y_k )_{k≥1} be two independent sequences of independent 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 X_1 * * * X_n and Y_1 * * * Y_n . Under assumptions on the distribution of X1 , 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, . . . , n}, which is shown to be the Tracy-Widom distribution.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...