Stochastic scrabble: large deviations for sequences with scores

Abstract

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₁ · ·· i_m is defined to be V(w)=v(i₁) + · ·· + v(i_m). Let V_n denote the value of the highest-scoring matching contiguous subsequence between X₁X₂ · ·· X_n and Y₁Y₂· ·· 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.