A central limit theorem for the length of the longest common subsequences in random words
Electronic Journal of Probability, cilt.28, 2023 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 28
- Basım Tarihi: 2023
- Doi Numarası: 10.1214/22-ejp894
- Dergi Adı: Electronic Journal of Probability
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, MathSciNet, zbMATH, Directory of Open Access Journals
- Anahtar Kelimeler: central limit theorem, edit/Levenshtein distance, last passage percolation, longest common subsequences, optimal alignments, random permutations, random words, Stein’s method, supersequences, Tracy-Widom distribution, Ulam’s problem
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Let (Xi)i≥1 and (Yi)i≥1 be two independent sequences of independent identically distributed (iid) random variables taking their values in a common finite alphabet and having the same law. Let LCn be the length of the longest common subsequences of the two random words X1 · · · Xn and Y1 · · · Yn. Under a lower bound assumption on the order of its variance, LCn is shown to satisfy a central limit theorem. This is in contrast to the limiting distribution of the length of the longest common subsequences in two independent uniform random permutations of {1, …, n}, which is shown to be the Tracy-Widom distribution.