Chvátal–Sankoff constant for a binary alphabet
Description of constant
Let $\lambda_{n,2}$ be the random variable assigning two uniformly random binary strings of length $n$ the length of their longest common subsequence. Then $C_{31a}$ is the (well-defined) limit $C_{31a} := \lim_{n \to \infty}\frac{\mathbb{E}[\lambda_{n,2}]}{n}$.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | Trivial | |
| $0.837623$ | [DP1995] | |
| $0.826280$ | [L2009] | Computer assisted |
| $0.825101$* | [J2026] | Computer assisted. Lueker’s automaton $M_h$ of [L2009] (Section 3.2) run with history length $h=9$: 51,425,006 accepting states, $z=0.3298$, certified $\lambda(z)\le 0.364708361184292$ (upward rounding), bound $2\log(2z)/\log\lambda(z)$. The same code reproduces Table II of [L2009] for $h\le 8$. |
| $0.824120$* | [J2026] | Same method with $h=10$: 400,253,317 accepting states, $z=0.3376$, certified $\lambda(z)\le 0.385532705434511$. |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $0$ | Trivial | |
| $> 0$ | [CS1975] | Showed existence of limit |
| $0.773911$ | [D1994] | Computer assisted |
| $0.788071$ | [L2009] | Computer assisted |
| $0.792665992$ | [H2024] | Computer assisted |
| $0.79970$ | [AA2026] | AI and computer assisted (unverified). Monte Carlo with a Hoeffding margin: the mean length of a width-100 beam-search common subsequence over $10^6$ random pairs of binary strings of length $1000$ is $0.803417$, minus $0.003717$ from Hoeffding’s inequality with $\delta = 10^{-12}$. So the statement holds with probability $1 - 10^{-12}$ over the sampled strings. It is not a deterministic lower bound. |
Additional comments
References
- [CS1975] Chvatal, Václáv, and David Sankoff. “Longest common subsequences of two random sequences.” Journal of applied probability 12.2 (1975): 306-315. Available at https://par.cse.nsysu.edu.tw/resource/paper/2013/131230/CS-TR-75-477.pdf
- [H2024] Heineman, George T., et al. “Improved Lower Bounds on the Expected Length of Longest Common Subsequences.” arXiv preprint (2024) arXiv:2407.10925.
- [J2026] Jack, Leandre. “An improved upper bound on the binary Chvátal–Sankoff constant.” (2026). Code, certificates and instructions at https://github.com/leandrejack-afk/chvatal-sankoff-bound (commit cd99c68).
- [L2009] Lueker, George S. “Improved bounds on the average length of longest common subsequences.” Journal of the ACM (JACM) 56.3 (2009): 1-38. Available at https://dl.acm.org/doi/pdf/10.1145/1516512.1516519
- [DP1995] Dančík, Vlado, and Mike Paterson. “Upper bounds for the expected length of a longest common subsequence of two binary sequences.” Random Structures & Algorithms 6.4 (1995): 449-458. Available at https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.3240060408
- [D1994] Dancík, Vladimír. Expected length of longest common subsequences. Diss. University of Warwick, 1994. Available at https://wrap.warwick.ac.uk/id/eprint/107547/1/WRAP_Theses_Dancik_1994.pdf
- [AA2026] Archivara Agent. “An Improved Lower Bound on the Chvátal–Sankoff Constant for Binary Strings via Monte Carlo Beam Search.” (2026). Available at https://archivara.org/paper/1a5c6a48-a106-40e4-a5f0-97833f3a25a7. Code and reproducible data at https://github.com/spicylemonade/constant.
Contribution notes
The [J2026] rows were prepared with the help of a large language model; the computation was checked as described in the linked repository.
- The description of the [AA2026] method in the lower-bound table (Monte Carlo with a Hoeffding margin) was added with Claude Code (Anthropic), from the [AA2026] repository README.