The longest thread between two random strings

Charged for the variance, not the range ended with a gap that no general inequality closes. For some quantities built from many random inputs, the true fluctuations are far smaller than any concentration bound gives, and the true scale was found only by problem-specific calculation. The longest increasing subsequence of a shuffled deck is the famous case: the longest climb of a shuffle fluctuates on the scale $n^{1/6}$, where the general bounds reach only $n^{1/4}$. A close relative has resisted every such calculation. It is the longest common subsequence of two random strings.

Take two strings of random bits, each of length $n$. A common subsequence is a sequence of bits that can be read in both strings, left to right, skipping freely in each. The longest such sequence measures how similar the two strings are once insertions and deletions are allowed — the measure behind sequence alignment in genetics and the comparison that file-difference tools make. For random strings it is a sum of no independent parts at all, and two of its most basic numbers are unknown: the constant its length grows at, and the scale on which it fluctuates.

A thread that never crosses #

The hero figure draws one longest common subsequence as threads joining equal bits, top to bottom. The threads never cross, since the subsequence must keep its order in both strings, and they skip freely — some bits in each string are left unthreaded. The longest set of non-crossing threads between equal bits has 27 threads here.

Finding it is a standard computation. Let $L(i, j)$ be the length for the first $i$ bits of one string and the first $j$ of the other. Then $L(i, j)$ is one more than $L(i - 1, j - 1)$ if the $i$-th and $j$-th bits agree, and otherwise the larger of $L(i - 1, j)$ and $L(i, j - 1)$. Filling the table takes $n^2$ steps. For the long strings of the later figures the table’s rows are packed into machine words, 32 bits at a time, with a recurrence due to Lloyd Allison and Trevor Dix that updates a whole row with one addition and a few logical operations. The packed computation is checked against the plain table on hundreds of random cases before it is trusted.

Why anyone needed the random baseline #

The question was asked for a practical reason. When two DNA or protein sequences are compared, the length of their best alignment — the longest common subsequence, or a weighted version of it that charges for gaps — is a score, and a score means something only against what unrelated sequences would score. Two random strings of length a thousand already share a thread about 810 long. An observed common subsequence of 830 between two genes is therefore weak evidence of relationship, and one of 900 is strong. The difference is entirely in knowing where the random baseline sits and how much it varies.

That is why the two numbers this essay measures are the ones that matter. The constant $\gamma_2$ fixes the centre of the baseline, and the variance fixes its width, which turns an observed excess into a significance. Michael Waterman’s work on alignment statistics in the 1980s and 1990s took both from simulation, because neither was known in closed form, and they still are not. The same comparison underlies the file-difference tools that report the lines two versions of a program share. For random files the shared fraction would sit near four-fifths for a two-symbol alphabet and fall like $2/\sqrt k$ for $k$ symbols, as the alphabet figure below shows.

About four-fifths of each string #

Two random bits agree half the time, so a thread can be found for at least half the positions by pairing equal bits greedily. The skipping does the rest, and the share of each string in the longest thread climbs well past one half.

For a single bit the share is exactly one half: two bits agree half the time. For strings of length two it is $0.5625$, for length nine $0.6913$, computed exactly over all $4^9 = 262{,}144$ pairs. Sampled at longer lengths it keeps rising — $0.7813$ at a hundred, $0.7992$ at four hundred, $0.8088$ at 3,200 — and the approach to the limit is slow, with the gap shrinking only like a power of $n$. Kenneth Alexander proved in 1994 that the expected length falls short of its limit by at most a constant times $\sqrt{n \log n}$, which allows exactly this kind of crawl.

Václav Chvátal and David Sankoff proved in 1975 that the limiting share exists, and called it $\gamma_2$. Its value is still unknown. The best numerical estimates put it near $0.8122$. The best proved bounds, by George Lueker in 2009, place it between $0.788$ and $0.826$, and narrowing them has needed computations of enormous size, because every rigorous bound comes from analysing strings of a fixed finite length exactly. The share of a random string that another random string shares with it is a constant of nature that nobody can compute to three decimal places with proof.

Why a limit must exist #

That a limit exists at all is a short argument, and the exact small cases show its ingredient.

Split each string into a first part of length $m$ and a second of length $n$. A common subsequence of the two first parts followed by one of the two second parts is a common subsequence of the whole strings, so the longest for the whole is at least the sum of the longest for the parts. Taking expectations, $E(m + n) \ge E(m) + E(n)$. The exact values for $n \le 9$ satisfy this in every case, and Fekete’s lemma — the tool a walk that may not step where it has been used for counting self-avoiding walks — turns it into a limit: $E(n)/n$ converges to its least upper bound.

The argument proves the limit exists and gives lower bounds, since every exact $E(n)/n$ is below it. It gives no upper bounds at all, and none of the exact small cases says anything about what the limit is. The value 0.6913 at $n = 9$ is a proved lower bound, and a weak one. Lueker’s bounds needed a different idea, a dynamic programme over pairs of strings of length a few dozen, run as a computation on probability distributions rather than on strings.

How much it varies #

The length of the longest thread is a function of $2n$ random bits, and changing any one bit changes it by at most one. That is the hypothesis of the bounded-differences inequality of no single input can move it far, and its variance form, the Efron–Stein inequality, gives a bound directly. Each bit, resampled, differs from its old value half the time and then moves the length by at most one. Michael Steele used this in 1986 to show that the variance is at most $n/2$ for two-letter strings. The fluctuations are at most of order $\sqrt n$.

The measured variance is far below the bound and grows more slowly. Between $n = 200$ and $n = 3{,}200$ it rises from $8.9$ to $57.9$, a fitted exponent of $0.70$. The slope measured between successive doublings stays near $0.7$ at every step, within its sampling error of about $0.1$. The ratio of variance to $n$, which would level off if the variance were linear, falls by a factor of four over the range.

That is a result to state carefully, because the question it bears on is open. Chvátal and Sankoff guessed in 1975 that the variance was of smaller order than $n$, comparable to $n^{2/3}$. Michael Waterman later conjectured, from simulations, that it is linear. Jüri Lember and Heinrich Matzinger proved in 2009 that it is linear when one of the two letters is much rarer than the other. For fair bits the order of the variance is not known. Over the lengths computed here it behaves like $n^{0.7}$, close to Chvátal and Sankoff’s guess. But a variance that is eventually linear with a slowly emerging constant would look exactly like this at these sizes, and nothing in the figure can tell the two apart.

The gap between the bound and the measurement has a familiar cause. Efron–Stein charges each bit for the most it could matter, but in a long common subsequence most bits barely matter: change one, and the thread usually reroutes around it at no cost. The same kind of slack appeared for the edges of a random spanning tree, whose count in half a grid varied sixteen times less than independent edges would, because the structure absorbed most of each edge’s influence. Here the structure absorbs even more as $n$ grows, which is what a variance growing more slowly than $n$ means, and why no general inequality can be expected to find the true order.

The shape of the fluctuations #

Whatever their scale, the fluctuations have a shape, and it can be measured at one length.

At length 800 the longest common subsequence averages $642.9$ with a standard deviation of $4.7$ — under one per cent of its length. The standardised values follow the bell closely, with a skewness of $-0.04$. That is a clear difference from the longest increasing subsequence of a shuffle. There the fluctuations follow the Tracy–Widom law, visibly lopsided, with a skewness of about $0.22$, and they come from the same structure as the largest eigenvalue of a random matrix.

A bell suggests that the common subsequence behaves like a sum of many weakly dependent pieces, and a bell with linear variance would be the ordinary central limit picture. Central limit theorems have been proved for the biased strings where the variance is known to be linear. For fair bits the shape is, like the scale, a measurement.

Many letters turn it into a climb #

The connection to increasing subsequences is not only an analogy. It becomes exact as the alphabet grows.

With $k$ letters, two random strings agree at a given pair of positions with chance $1/k$, so there are about $n^2/k$ matching pairs, scattered over the $n \times n$ grid of position pairs like random points. A common subsequence is a chain of matching pairs increasing in both coordinates. When matches are rare and scattered, the longest such chain is the longest increasing chain among about $n^2/k$ random points in a square. The longest climb of a shuffle showed that this has length about $2\sqrt{m}$ for $m$ points — Hammersley’s problem.

With $m = n^2/k$ that gives a length of $2n/\sqrt k$, so $\gamma_k \sqrt k \to 2$, as Marcos Kiwi, Martin Loebl and Jiří Matoušek proved in 2005. The figure shows the product rising from $1.14$ for bits, through $1.44$ for eight letters, to $1.74$ for sixty-four. It approaches 2 slowly, and more slowly still at finite length, where boundary effects pull it down. For bits the problem is something else; for a large alphabet it is Hammersley’s, and the same theorem suggests that for large alphabets the fluctuations should approach the Tracy–Widom scale. Where between two letters and infinitely many the behaviour changes is not known.

A path through a grid of matches #

There is a picture in which the two answers on offer are two universality classes. Draw an $n \times n$ grid whose rows are the positions of one string and whose columns are the positions of the other, and mark a cell when the two bits there agree — about half the cells for bits. A common subsequence is a path through marked cells moving strictly down and to the right, and the longest one is the path collecting the most marks. That makes the longest common subsequence a last-passage percolation time: the largest total weight along a monotone path through a random environment.

Last-passage percolation with independent weights in every cell is one of the solved members of the Kardar–Parisi–Zhang class. Its fluctuations are of order $n^{1/3}$, its variance $n^{2/3}$, and its limiting law is Tracy–Widom, by the same exact formulas that settle increasing subsequences. Growth models like the shape a random ball grows into are believed to share these exponents. If the common subsequence belonged to that class, its variance would grow like $n^{2/3}$ and its fluctuations would be skewed.

But the weights in the common-subsequence grid are not independent. Whether cell $(i, j)$ is marked depends on bit $i$ of one string and bit $j$ of the other, so every row’s marks are tied together by one bit and every column’s by another. Only $2n$ random bits make $n^2$ marks. That dependence is exactly what could change the class, and it is why neither the KPZ exponents nor the linear ones can be taken over. The measured exponent of $0.70$ sits near the KPZ value, and the measured shape sits near the bell, which belongs to the other answer. The two halves of the evidence point in different directions, which is the clearest sign that these lengths are not yet in the asymptotic regime.

What the computations can and cannot say #

Every figure here is either exact — the small-$n$ means, the superadditivity — or a sample with an error that can be estimated. The sample means agree with the known bounds, and the variance stays below Steele’s bound as it must. What the samples cannot do is decide the asymptotic order of the variance, which is the question of most interest. A measured exponent of $0.70$ over a range of sixteen in $n$ is evidence, and the competing hypotheses make predictions that differ only by a factor that grows like $n^{1/3}$, a factor of about $2.5$ over the whole range. A slowly varying constant could absorb that.

Nor do the figures say anything about the structure of the longest common subsequences themselves: how many there are, how much two of them overlap, how far the threads stray from the diagonal. Those are the quantities that a proof of the fluctuation order would probably have to control, and they are harder to measure than the length.

Still open: the constant and the variance #

$\gamma_2$ is unknown, and so is every $\gamma_k$ for finite $k$; no closed form has been proposed for any of them that matches the numerics. The rigorous bounds narrow only with great computational effort, because each improvement needs exact analysis of longer finite strings.

The order of the variance for fair bits is open, and it matters beyond this problem. If it is linear, the common subsequence belongs with sums of nearly independent pieces, and the general concentration inequalities are sharp for it. If it is smaller, like $n^{2/3}$, the common subsequence belongs with the increasing subsequence and the last-passage percolation models of the Kardar–Parisi–Zhang universality class, whose fluctuations come from random-matrix theory. The bit strings sit between those two worlds, and which one they belong to is exactly the kind of question that no single input can move it far and its successors can bound but not answer.

A comparison of two strings, measured #

The longest common subsequence is about the most natural similarity measure for two strings, and for random strings it has a definite average share, $0.8122$ to the best of anyone’s computation. That share exists by a two-line argument, has bounds that cost decades of computing to narrow, and approaches its limit too slowly to read off. The fluctuations around it are bounded by a general inequality and measured to grow like $n^{0.7}$ across every length that can be sampled. That exponent falls between the two answers on offer, and the measurements cannot choose between them. Over a large alphabet the whole problem turns into the longest increasing subsequence, where the answers are known. For two letters, the simplest case, they are not.