Limit Distribution of Maximal Non-Aligned Two-Sequence Segmental Score

Consider two independent sequences X₁,…, Xₙ and Y₁,…, Yₙ. Suppose that X₁,…, Xₙ are i.i.d. μX and Y₁,…, Yₙ are i.i.d. μY, where μX and μY are distributions on finite alphabets σX and σY, respectively. A score F: σX × σY→ R is assigned to each pair (Xᵢ, Yⱼ) and the maximal nonaligned segment score is Mₙ = max0≤ i, j≤ n - Δ, Δ ≥ 0 \∑^Δₖ₌₁ F(Xᵢ₊ₖ, Yⱼ₊ₖ)\. The limit distribution of Mₙ is derived here when μX and μY are not too far apart and F is slightly constrained.