Title: The Chvátal-Sankoff problem: Understanding random string comparison through stochastic processes Show Chinese title

Title: Chvátal-Sankoff问题：通过随机过程理解字符串比较

Abstract: Given two equally long, uniformly random binary strings, the expected length of their longest common subsequence (LCS) is asymptotically proportional to the strings' length. Finding the proportionality coefficient $\gamma$, i.e. the limit of the normalised LCS length for two random binary strings of length $n \to \infty$, is a very natural problem, first posed by Chv\'atal and Sankoff in 1975, and as yet unresolved. This problem has relevance to diverse fields ranging from combinatorics and algorithm analysis to coding theory and computational biology. Using methods of statistical mechanics, as well as some existing results on the combinatorial structure of LCS, we link constant $\gamma$ to the parameters of a certain stochastic particle process, which we use to obtain a new estimate for $\gamma$. Show Chinese abstract

Abstract: 给定两个长度相等的均匀随机二进制字符串，它们的最长公共子序列（LCS）的期望长度在渐近意义上与字符串的长度成正比。 找到比例系数$\gamma$，即对于长度为$n \to \infty$的两个随机二进制字符串的归一化 LCS 长度的极限，是一个非常自然的问题，最早由 Chvátal 和 Sankoff 在 1975 年提出，但至今仍未解决。 这个问题与从组合数学和算法分析到编码理论和计算生物学的多个领域都有关联。 使用统计力学的方法以及一些关于 LCS 组合结构的现有结果，我们将常数$\gamma$与某种随机粒子过程的参数联系起来，我们利用这个过程得到了$\gamma$的新估计。