Statistics Seminar: On the Limiting Distribution of the Length of the longest Common Subsequence

When:
October 17, 2014 @ 3:00 pm – 4:00 pm
2014-10-17T15:00:00-04:00
2014-10-17T16:00:00-04:00
Where:
Statistics Seminar
30 Pryor Street Southwest #796
Georgia State University, Atlanta, GA 30303
USA
Cost:
Free
Contact:
Yichuan Zhao
(404) 413-6446

Fall 2014 Statistics Seminar

Speaker: Professor Christian Houdre, School of Mathematics, Georgia Institute of Technology

Title: On the Limiting Distribution of the Length of the longest Common Subsequence

Abstract: 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)