We investigate the asymptotic standard deviation of the Longest Common
Subsequence (LCS) of two i.i.d. sequences of length n which are independent
of each other. The rst sequence is drawn from a three letter alphabet f0; 1; ag,
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 (pn).
This con rms Waterman's conjecture Waterman (1994) for this special case. This
is very interesting considering that it is believed that for equal probability of 0 and
1 the order is o(n1=3); (see the Sanko -Chvatal conjecture in Chvatal and Sanko
(1975)).
The order of the
uctuation of the LCS of two i.i.d. binary sequences is a long
open standing question. In a subsequent paper, we use the techniques developped
in this article to solve this problem when the two sequences are binary, but 0 and
1 have suciently di erent probabilities.
The LCS problems can also be viewed as First Passage Problems (FPP) on a graph
with correlated weights. For standard FPP the order of the
uctuations has been
an open question for decades.