Author: Federico Bonetto Heinrich Matzinger

Title: Fluctuations Of The Longest Common Subsequence In The Asymmetric Case Of 2- And 3-Letter Alphabets

Abstract: We investigate the asymptotic standard deviation of the Longest Common Subsequence (LCS) of two independent i.i.d. sequences of length $n$. The first sequence is drawn from a three letter alphabet {0,1,a}, whilst the second sequence is binary. The main result of this article is that in this asymmetric case, the standard deviation of the length of the LCS is of order square root of n. This confirms Waterman's conjecture Waterman-estimation for this special case. Our result seems to indicate that in many other situations the order of the standard deviation is also square root of n.

Keywords: Sequence comparison, longest common subsequnce

Federico Bonetto
School of Mathematics
Gerogia Institute of Technology
Atlanta, GA 30309
email: bonetto@math.gatech.edu

Heinrich Matzinger
School of Mathematics
Gerogia Institute of Technology
Atlanta, GA 30309
email: matzi@math.gatech.edu