20251119_Houdre

Christian Houdré
Professor and Associate Chair for Research
Georgia Institute of Technology
Date: Nov. 19, Wednesday, 2025
Time: 12:10pm -- 13:00pm
Host: Le Chen
Room: Parker 328
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.

This talk will be extracted in part from the following published papers:

On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distributions
Authors: Clément Deslandes, Christian Houdré
arXiv:1906.06544
On the limiting law of the length of the longest common and increasing subsequences in random words
Authors: Jean-Christophe Breton, Christian Houdré
arXiv:1505.06164 · doi:10.1016/j.spa.2016.09.005
A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
Authors: Christian Houdré, Ümit Işlak
doi:10.1214/22-EJP894