Some limit results for longest common subsequences

The length l_n of a longest common subsequence before time n sequences (B₁₁, B₁₂, …) (B₂₁, B₂₂, …) is the cardinality of the largest increasing set of pairs of integers {(j_1α, j_2α)}

$\text{l?}\text{j}{}_{11}\text{<}\text{j}{}_{12}\text{<·<}\text{j}{}_{11}{}_{\mathrm{n}}\text{?}\text{n}\text{l?}\text{j}{}_{21}\text{<}\text{j}{}_{22}\text{<·<}\text{j}{}_{21}{}_{\mathrm{n}}\text{?}\text{n}$

such that ?1?α?l_n, (B_1j1α=B_2j2α). If B₁ and B₂ 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 l_n/n converges to a constant c_k a.s. A method of deriving lower bounds for the constants c_k is given, the bounds obtained improving known lower bounds, for k>2. The rate of decrease of c_k with k is shown to be no faster than 1/√k, contrasting with P{B_1i?B_2i}=1/k. Finally, an alternative method of deriving lower bounds is given and used to improve the lower bound for c₂.