Stochastic scrabble: large deviations for sequences with scores

A derivation of a law of large numbers for the highest-scoring matching subsequence is given. Let X k , Y k be i.i.d. q =( q ( i )) i ∊ S letters from a finite alphabet S and v =( v ( i )) i ∊ S be a sequence of non-negative real numbers assigned to the letters of S. Using a scoring system similar to that of the game Scrabble, the score of a word w = i 1 · ·· i m is defined to be V ( w )= v ( i 1 ) + · ·· + v ( i m ). Let V n denote the value of the highest-scoring matching contiguous subsequence between X 1 X 2 · ·· X n and Y 1 Y 2 · ·· Y n . In this paper, we show that V n /K log( n ) → 1 a.s. where K ≡ K ( q , v ). 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 β ∊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 < τ v ( X n ), for a Markov chain stopped at the hitting time τ of some state. We give this large deviation result explicitly, for Markov chains in discrete time and in continuous time.