SOME LIMIT RESULTS FOR LONGEST COMMON SUBSEQUENCES

The length ln of a longest common subsequence before time n sequences (B11, B12, ...) (B21, B22, ...) is the cardinality of the largest increasing set of pairs of integers {(j1α, j2α)} l≤j11<j12<·<j11n≤n l≤j21<j22<·<j21n≤n such that ∀1≤α≤ln, (B1j1α=B2j2α). If B1 and B2 are independent random sequences with co-ordinates i.i.d. uniform on {1, 2, ..., k}, it follows from Kingman's subadditive ergodic theorem that the ratio ln/n converges to a constant ck a.s. A method of deriving lower bounds for the constants ck is given, the bounds obtained improving known lower bounds, for k>2. The rate of decrease of ck with k is shown to be no faster than 1/√k, contrasting with P{B1i-B2i}=1/k. Finally, an alternative method of deriving lower bounds is given and used to improve the lower bound for c2. © 1979.