Editing Longest common subsequence (section)

== Behavior on random strings ==
{{main|Chvátal–Sankoff constants}}
Beginning with {{harvtxt|Chvátal|Sankoff|1975}},<ref>{{citation
 | last1 = Chvátal | first1 = Václáv | author1-link = Václav Chvátal
 | last2 = Sankoff | first2 = David | author2-link = David Sankoff
 | journal = Journal of Applied Probability
 | mr = 0405531
 | pages = 306–315
 | title = Longest common subsequences of two random sequences
 | volume = 12
 | issue = 2 | year = 1975 | doi=10.2307/3212444| jstor = 3212444 | s2cid = 250345191 }}.</ref> a number of researchers have investigated the behavior of the longest common subsequence length when the two given strings are drawn randomly from the same alphabet. When the alphabet size is constant, the expected length of the LCS is proportional to the length of the two strings, and the constants of proportionality (depending on alphabet size) are known as the [[Chvátal–Sankoff constants]]. Their exact values are not known, but upper and lower bounds on their values have been proven,<ref>{{citation
 | last = Lueker | first = George S.
 | doi = 10.1145/1516512.1516519
 | issue = 3
 | journal = [[Journal of the ACM]]
 | mr = 2536132
 | at = A17
 | title = Improved bounds on the average length of longest common subsequences
 | volume = 56
 | year = 2009| s2cid = 7232681
 }}.</ref> and it is known that they grow inversely proportionally to the square root of the alphabet size.<ref>{{citation
 | last1 = Kiwi | first1 = Marcos
 | last2 = Loebl | first2 = Martin
 | last3 = Matoušek | first3 = Jiří | author3-link = Jiří Matoušek (mathematician)
 | doi = 10.1016/j.aim.2004.10.012 | doi-access=free
 | issue = 2
 | journal = [[Advances in Mathematics]]
 | mr = 2173842
 | pages = 480–498
 | title = Expected length of the longest common subsequence for large alphabets
 | volume = 197
 | year = 2005| arxiv = math/0308234
 }}.</ref> Simplified mathematical models of the longest common subsequence problem have been shown to be controlled by the [[Tracy–Widom distribution]].<ref>{{citation
 | last1 = Majumdar | first1 = Satya N.
 | last2 = Nechaev | first2 = Sergei
 | doi = 10.1103/PhysRevE.72.020901
 | pmid = 16196539
 | issue = 2
 | journal = Physical Review E
 | mr = 2177365
 | pages = 020901, 4
 | title = Exact asymptotic results for the Bernoulli matching model of sequence alignment
 | volume = 72
 | year = 2005| arxiv = q-bio/0410012
 | bibcode = 2005PhRvE..72b0901M
 | s2cid = 11390762
 }}.</ref>