The Chvátal-Sankoff problem: Understanding random string comparison through stochastic processes
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909286338134016 |
|---|---|
| author | Tiskin, Alexander |
| author_facet | Tiskin, Alexander |
| contents | 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 $γ$, 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átal 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 $γ$ to the parameters of a certain stochastic particle process, which we use to obtain a new estimate for $γ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_01582 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Chvátal-Sankoff problem: Understanding random string comparison through stochastic processes Tiskin, Alexander Combinatorics Discrete Mathematics Probability 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 $γ$, 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átal 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 $γ$ to the parameters of a certain stochastic particle process, which we use to obtain a new estimate for $γ$. |
| title | The Chvátal-Sankoff problem: Understanding random string comparison through stochastic processes |
| topic | Combinatorics Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2212.01582 |