OP-00410 Open

Is the variance of fair binary sequence alignment linear?

Let $X_1, \dots, X_n$ and $Y_1, \dots, Y_n$ be independent fair binary strings, and let $L_n$ be the length of their longest common subsequence: the largest $k$ for which there are indices $i_1 < \dots < i_k$ and $j_1 < \dots < j_k$ in $\{1, \dots, n\}$ with $X_{i_r} = Y_{j_r}$ for all $r$. Chvátal and Sankoff proved that $\mathbb{E}L_n / n$ converges, and from simulations conjectured $\operatorname{Var}(L_n) = o(n^{2/3})$. Steele proved the upper bound $\operatorname{Var}(L_n) \le n/2$, and Waterman asked whether this linear bound can be improved. Lember and Matzinger proved a lower bound of order $n$ when each letter is $1$ with a small enough probability instead of $1/2$.

Problem. Is there a constant $c > 0$ such that $\operatorname{Var}(L_n) \ge cn$ for every sufficiently large $n$?

Source: Chvátal and Sankoff (1975), who conjectured from simulations that Var(Lₙ) = o(n^{2/3}) for fair binary strings, and Waterman (1994), who asked whether Steele's linear upper bound can be improved; see Lember and Matzinger (2009). Stated by AIM — Open Applied Problems as a linear lower bound.

Imported from github.com/MColbrook/AIM.

Classification

Primary: PR — Probability
Secondary: CO
Keywords: AIM Open Applied Problems, longest common subsequences, sequence alignment, variance bounds

References

@article{chvatal1975,
  author  = {Chv{\'a}tal, V{\'a}clav and Sankoff, David},
  title   = {Longest common subsequences of two random sequences},
  journal = {J. Appl. Probab.},
  volume  = {12},
  number  = {2},
  year    = {1975},
  pages   = {306--315},
  doi     = {10.2307/3212444},
}
@article{waterman1994,
  author  = {Waterman, Michael S.},
  title   = {Estimating statistical significance of sequence alignments},
  journal = {Philos. Trans. R. Soc. Lond. B},
  volume  = {344},
  number  = {1310},
  year    = {1994},
  pages   = {383--390},
  doi     = {10.1098/rstb.1994.0077},
}
@article{steele1986,
  author  = {Steele, J. Michael},
  title   = {An {E}fron--{S}tein inequality for nonsymmetric statistics},
  journal = {Ann. Statist.},
  volume  = {14},
  number  = {2},
  year    = {1986},
  pages   = {753--758},
  doi     = {10.1214/aos/1176349952},
}
@article{lember2009,
  author        = {Lember, J{\"u}ri and Matzinger, Heinrich},
  title         = {Standard deviation of the longest common subsequence},
  journal       = {Ann. Probab.},
  volume        = {37},
  number        = {3},
  year          = {2009},
  pages         = {1192--1235},
  doi           = {10.1214/08-AOP436},
  eprint        = {0907.5137},
  archivePrefix = {arXiv},
}
@misc{aim-binary-lcs-linear-variance,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Is the variance of fair binary sequence alignment linear?}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/286-binary-lcs-linear-variance.md},
  note         = {Entry 286 at commit a153f46, 2026-10-13},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00410, "Is the variance of fair binary sequence alignment linear?", clopen.solutions.