A derivation of a law of large numbers for the highest-scoring matching subsequence is given. Let Xk,Yk be i.i.d. qµ=(q(i))iÅ∈S letters from a finite alphabet S and ℝi>nµ=(ν(i))iÅ∈S be a sequence of non-negative real number assigned to the letters of S. Using a scoring system similar to that of the game Scrabble, the score of a word w=i1ëëëim is defined to be V(w)=ν(i1)+ëëë+ν(im). Let Vn denote the value of the highest-scoring matching contiguous subsequence between X1X2ëëëXn and Y1Y2ëëëYn. In this paper, the authors show that Vn/Klog(n)∈1 a.s. where K∈K(qµ,ℝi>nµ). The method employed here involves ‘stuttering’ the letters to construct a Markov chain and applying previous results for the length of the longest matching subsequence. An explicit form for ℝi>bµ∈Pr(S), where β(i) denotes the proportion of letter i found in the highest-scoring word, is given. A similar treatment for Markov chains is also included. Implicit in these results is a large-deviation result for the additive functional, H∈∈nÅ∈Åτν(Xn), for a Markov chain stopped at the hitting time τ of some state. The authors give this large deviation result explicitly, for Markov chains in discrete time and in continuous time.
