The rate of the convergence of the mean score in random sequence comparison

الأصل · EN

We consider a general class of super-additive scores measuring the similarity of two independent sequences of n i.i.d. letters from a finite alphabet. Our object of interest is the mean score by letter lₙ. By the subadditivity lₙ is nondecreasing and converges to a limit l. We give a simple method of bounding the difference l-lₙ and obtaining the rate of convergence. Our result generalizes a previous result of Alexander, where only the special case of the longest common subsequence is considered.