Mathematics – Probability
Scientific paper
2010-11-11
Mathematics
Probability
18 pages
Scientific paper
The problem of the order of the fluctuation of the Longest Common Subsequence (LCS) of two independent sequences has been open for decades. There exist contradicting conjectures on the topic, due to Chvatal - Sankoff in 1975 and Waterman in 1994. In the present article, we consider a special model of i.i.d. sequences made out of blocks. A block is a contiguous substring consisting only of one type of symbol. Our model allows only three possible block lengths, each been equiprobable picked up. In this context, we introduce a random operation (random modification) on the blocks of one of the sequences. In the present article, we develop the techniques to prove the following: if we suppose that the random modification increases the length of the LCS with high probability, then the order of the fluctuation of the LCS is as conjectured by Waterman. This result is a key technical part in the study of the size of the fluctuation of the LCS for sequences of i.i.d. blocks, developed by Matzinger and Torres.
Matzinger Heinrich
Torres Felipe
No associations
LandOfFree
Random modification effect in the size of the fluctuation of the LCS of two sequences of i.i.d. blocks 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 Random modification effect in the size of the fluctuation of the LCS of two sequences of i.i.d. blocks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random modification effect in the size of the fluctuation of the LCS of two sequences of i.i.d. blocks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-431208