DMS Analysis and Stochastic Analysis Seminar (SASA)

Speaker: Christian Houdré (Georgia Tech)

Title: Longest common (and increasing) subsequences in random words: differences and similarities

Abstract: Let \(LC_n​\) be the length of the longest common subsequences of two independent random words whose letters are taken in a finite alphabet and when the alphabet is totally ordered, let \(LCI_n\)​ be the length of the longest common and increasing subsequences of the words. Results on the asymptotic means, variances and limiting laws of these well known random objects will be described and compared.