The rate of the convergence of the mean score in random sequence comparison
Jüri Lember, Heinrich Matzinger, Felipe Torres · The Annals of Applied Probability · 2012
We consider a general class of superadditive 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 ln. By subadditivity ln is nondecreasing and converges to a limit l. We give a simple method of bounding the difference l − ln and obtaining the rate of convergence. Our result generalizes the previous result of Alexander [Ann. Appl. Probab. 4 (1994) 1074–1082], where only the special case of the longest common subsequence was considered.