The exact asymptotic match fraction for independent binary sequences
Let $(X_i)_{i \ge 1}$ and $(Y_i)_{i \ge 1}$ be independent sequences of independent fair bits, and let $L_n$ be the length of a longest common subsequence of $X_1 \cdots X_n$ and $Y_1 \cdots Y_n$. Chvátal and Sankoff proved that $\mathbb{E}[L_n]/n$ converges to a constant $\gamma_2$, the Chvátal–Sankoff constant. Lueker proved $0.788071 \le \gamma_2 \le 0.826280$; the upper bound lies below $2/(1 + \sqrt2) \approx 0.828427$, the value conjectured by Steele. Soiffer, Salls, Miller, Reichman, Sárközy and Heineman raised the lower bound to $0.792665992$.
Problem. Determine the exact value of $\gamma_2 = \lim_{n \to \infty} \mathbb{E}[L_n]/n$. An exact evaluation, or a characterization that determines the constant explicitly, is sought, not further numerical bounds or a restatement of this limit.
Source: Chvátal and Sankoff (1975), who proved that the limit exists; see Lueker (2009) and Dixon (2013).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, longest common subsequences, random sequences
References
@article{chvatal1975,
author = {Chv{\'a}tal, V{\'a}clav and Sankoff, David},
title = {Longest common subsequences of two random sequences},
journal = {J. Appl. Probability},
volume = {12},
number = {2},
year = {1975},
pages = {306--315},
doi = {10.2307/3212444},
}
@article{lueker2009,
author = {Lueker, George S.},
title = {Improved bounds on the average length of longest common subsequences},
journal = {J. ACM},
volume = {56},
number = {3},
year = {2009},
pages = {Art. 17, 38 pp.},
doi = {10.1145/1516512.1516519},
}
@misc{dixon2013,
author = {Dixon, John D.},
title = {Longest common subsequences in binary sequences},
year = {2013},
eprint = {1307.2796},
archivePrefix = {arXiv},
}
@inproceedings{soiffer2025,
author = {Soiffer, Duncan and Salls, Andrew and Miller, Chase and Reichman, Daniel and S{\'a}rk{\"o}zy, G{\'a}bor and Heineman, George},
title = {Improved lower bounds on the expected length of longest common subsequences},
booktitle = {2025 IEEE International Symposium on Information Theory (ISIT)},
publisher = {IEEE},
year = {2025},
pages = {1--6},
doi = {10.1109/ISIT63088.2025.11195592},
eprint = {2407.10925},
archivePrefix = {arXiv},
}
@misc{aim-binary-lcs-constant,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The exact asymptotic match fraction for independent binary sequences}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/277-binary-lcs-constant.md},
note = {Entry 277 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-00409, "The exact asymptotic match fraction for independent binary sequences", clopen.solutions.