Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets

Details Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets

2004-10-18

arxiv.org/abs/math/0410404v1

Mathematics

Combinatorics

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-399483