Shuffle a deck or grow a crystal and the same distribution turns up again
Universality within random matrices is remarkable enough: change the entries and the eigenvalue statistics do not notice. What follows is stranger. The Tracy–Widom distribution turns up in problems that have no matrix in them at all, and no obvious way to put one in.
Shuffle a deck of cards and find the longest increasing run. Watch a crystal grow into a corner. Neither has a spectrum, an eigenvalue, or a symmetry class. Both produce the distribution that governs the largest eigenvalue of a random Hermitian matrix, down to the mean, the variance and the lean.
This lesson measures both, from first principles, and checks them against the published constants — and against each other.
Shuffle the numbers 1 to n. Now pick out the longest run of them that increases, reading left to right, taking terms wherever you like as long as you take them in order. How long can you get?
The answer concentrates near 2√n. For a deck of a thousand cards that asymptote is 63.2, and the measured average over 4,000 shuffles was 58.2 with a spread of 2.6 — an increasing run of nearly sixty values, hiding in every shuffle of a thousand, and almost never more than a few away from that. The length is computable in O(n log n) by patience sorting: deal each card onto the leftmost pile whose top is at least as large, or start a new pile, and the number of piles at the end is the answer.
| Statistic | Measured from shuffles | Tracy–Widom (β = 2) |
|---|---|---|
| Mean | — | -1.7711 |
| Variance | — | 0.8132 |
| Skewness | — | 0.2241 |
500 shuffles at each size. The convergence is slow and it is worth being honest about it: over n = 2,500 to 160,000 with far more samples than this button uses, the fitted exponent measured 0.183 rather than 0.167, and the segment-by-segment fits fell steadily — 0.197, then 0.180, then 0.173 — as n grew. The cleaner signal is the last column: sd ÷ n1/6measured 0.843, 0.879, 0.895 and 0.903 across those sizes, against the Tracy–Widom value of 0.9018. The constant arrives; the crude exponent fit lags behind it.
Each sample is one uniformly random permutation, shuffled by Fisher–Yates and measured by patience sorting — deal each card onto the leftmost pile whose top card is at least as large, or start a new pile, and the number of piles at the end is exactly the length of a longest increasing subsequence. No matrix is constructed anywhere in this demo.
Try it: Reshuffle the picture a few times and watch the length of the highlighted run barely move. Then collect a few thousand shuffles and compare the three moments against the Tracy–Widom column. Nothing in this demo constructs a matrix.
What was measured, including what did not work. The 2√n centring converges from below and slowly: the ratio of the mean length to 2√n measured 0.940, 0.962, 0.975 and 0.984 at n = 2,500, 10,000, 40,000 and 160,000. The n1/6 scaling comes out cleanly when tested as a constant — the spread divided by n1/6 measured 0.843, 0.879, 0.895 and 0.903 across those sizes, against Tracy–Widom’s √0.8132 = 0.9018. But fitting the exponent directly on log axes gives 0.183, not 0.167, because over any range this short the still-drifting constant contaminates the slope. The segment fits fall steadily — 0.197, then 0.180, then 0.173 — so it is heading to 1/6, but the fit itself does not get there and it would be wrong to report that it does. At n = 160,000 over 900 shuffles the rescaled sample gave mean −1.766 and variance 0.815, against the published −1.7711 and 0.8132.
Now a different problem entirely. Give every site of a grid an independent waiting time. A site can be occupied once both its neighbours below and to the left are occupied, and then only after its own clock runs out. Start at the corner and let it spread.
Two things emerge. The front settles onto a smooth deterministic curve — and the roughness around that curve does not vanish at the rate you would expect from averaging. It shrinks like the cube root of the time, and the shape of what is left is Tracy–Widom.
A 220 × 220 grid of independent exponential waiting times. A site joins the cluster once both the site below it and the site to its left have joined, and its own clock has finished. Pause the animation and look closely at the front: it tracks the dashed curve, and it is never smooth. That persistent roughness is the subject of the panel below.
Take the time T(n, n) at which the growth reaches the point n steps along the diagonal. Subtract 4n, divide by 24/3n1/3, and collect.
Both constants in that rescaling are checked rather than assumed: over the runs made for this page the mean of T(n, n) reached 92.0%, 95.0%, 96.7% and 98.0% of 4n at n = 50, 100, 200 and 400, climbing steadily toward it. With 6,000 growths at n = 100 the rescaled sample gave mean −1.7518, variance 0.7782 and skewness 0.2569, against Tracy–Widom’s −1.7711, 0.8132 and 0.2241 — and 2,500 growths at n = 200 gave −1.7561, 0.7974 and 0.2512. The fluctuation exponent fitted over n = 40 to 640 came out 0.350 against a predicted 1/3.
What is shown and what is not. This demo measures a growth model and finds Tracy–Widom moments in it. That this model belongs to the KPZ universality class, and that a wide family of unrelated growth processes belongs there with it, is a body of theory well beyond what a browser can establish — it is stated here, not proved here. What is demonstrated is that a specific model with no matrix in it produces the specific distribution the previous lessons found at the edge of a spectrum.
Try it: Pause the animation partway and look at the front against the dashed limit shape. It hugs the curve but never smooths onto it — the roughness is a permanent feature at every scale, not a transient. Then run the fluctuation panel below and compare its three moments with the deck-of-cards demo above. The two problems have nothing in common and they give the same numbers.
Both constants in the rescaling were checked rather than assumed. The mean time to reach n steps along the diagonal came to 92.0%, 95.0%, 96.7% and 98.0% of 4n at n = 50, 100, 200 and 400. The fluctuation exponent fitted over n = 40 to 640 came out 0.350 against a predicted 1/3 — much closer than the corresponding fit for shuffles, and decisively distinct from the 1/2 an average of independent waiting times would give. And with 6,000 growths at n = 100, the rescaled sample gave mean −1.7518, variance 0.7782 and skewness 0.2569, against Tracy–Widom’s −1.7711, 0.8132 and 0.2241.
One caution, stated plainly because it is easy to blur. What is shown here is that this growth model produces Tracy–Widom moments. The larger claim — that a whole family of superficially unrelated growth processes shares this behaviour, under the name of the KPZ universality class — is a body of theory that a browser cannot establish. It is reported here, not demonstrated here.
The list is long, and lists like this are easy to oversell. Each entry below carries a label saying how firmly it is established — measured in this module, proved for specific models, or proved under hypotheses that real problems only approximately satisfy.
The top of the spectrum of a large random Hermitian matrix, centred at the edge and scaled by n^(2/3).
Why it is the same law: This is where the distribution was found, and where the three symmetry classes give the three variants.
Sampled directly in the lesson on the edge, and matched against published moments to within a few percent at n = 400.
The labels matter. Two of these are measured on this page and one in an earlier lesson; the rest are reported results, proved for particular models where exact formulas happen to exist and expected more widely on the strength of that. A list like this is easy to read as a claim that everything is Tracy–Widom, which is not the claim — the claim is that a specific and recognisable family of problems shares a limit, and that the family is much larger than anyone expected it to be.
The way to make sense of all this is to stop thinking of these distributions as descriptions of particular problems and start thinking of them as attractors. A limit law is a fixed point that whole families of problems fall into, and which one you land in is settled by the structure of the problem rather than by its details.
Add up many independent contributions and you land on the Gaussian. Scatter points with nothing keeping them apart and the gaps between them are exponential. Take the largest of many quantities that are pushing against each other — eigenvalues repelling, a growth front dragged forward by its neighbours, a card run competing for room in the shuffle — and you land on Tracy–Widom.
Take the largest of many quantities that are pushing against each other. The competition is the whole mechanism, and it never washes out however large the problem gets.
Everything is standardised to mean 0 and variance 1 before plotting, so location and scale are gone and only shape is left. Watch what happens when you grow the problem. The sum of independent pieces starts skewed and straightens out — its skewness falls like 2/√k, and at 400 terms it is down to 0.1 and still falling. The longest increasing subsequence does not straighten out: its skewness sits near 0.22 at every deck size and stays there. That is the difference between a distribution that is on its way somewhere and one that has arrived.
Try it: Choose the Gaussian panel and grow the number of terms in the sum. The skewness falls like 2/√k — 1.0 at four terms, 0.4 at twenty-five, 0.1 at four hundred — on its way to zero. Now do the same on the Tracy–Widom panel by growing the deck. The skewness does not fall. It sits near 0.22 at every size, because this is not a distribution on its way somewhere; it is where things arrive.