The longest climb of a shuffle

Any $n$ distinct numbers, in any order, contain a run of about $\sqrt n$ of them that climbs or a run of that length that falls — a pigeonhole argument on two counters per number. That is Erdős and Szekeres’s theorem, and it is exact: there are orders in which no run, up or down, is any longer. It is a statement about the worst order. In 1961 Stanisław Ulam asked about a typical one. Shuffle a deck of $n$ cards thoroughly and deal them out; how long is the longest run of cards that increase?

The answer turned out to be one of the deepest results in probability of the last half-century. The longest increasing run of a random shuffle is almost exactly $2\sqrt n$ — twice the guarantee, and in both directions at once. How much it varies from shuffle to shuffle was settled only in 1999, and the answer connects card shuffles to the eigenvalues of random matrices, the growth of crystals and the edges of fluctuating interfaces.

The figure below is the problem in its most visual form. Four hundred points dropped at random in a square, and the longest chain of them that rises to the right in both coordinates: thirty-four points, where $2\sqrt{400} = 40$.

Points in a square #

The square and the shuffle are the same object. Drop $n$ points at random, sort them left to right, and record the order of their heights: the result is a uniformly random shuffle of $n$ cards, because every order of heights is equally likely. A chain rising to the right in both coordinates is then an increasing subsequence of the shuffle, and the longest such chain is the longest increasing subsequence.

The square version, due to John Hammersley in 1972, makes one fact nearly obvious. Double the side of the square and keep the density of points the same: there are four times as many points, and a rising chain across the big square can be built from rising chains across two small squares placed corner to corner along the diagonal. So the length is at least additive along the diagonal, and a length proportional to the side — that is, to $\sqrt n$ — is the natural scale. Hammersley proved that $L_n / \sqrt n$ settles to a constant, and conjectured it was $2$.

Why $2$ and not something else took five years and two independent proofs. In 1977 Benjamin Logan and Lawrence Shepp, and independently Anatoly Vershik and Sergei Kerov, proved it by identifying not just the longest run but the whole shape of a structure the shuffle determines — the same shape this essay ends with.

Patience sorting counts it #

Finding the longest increasing run of a given shuffle does not require checking every subsequence. A card game does it in one pass.

Deal the cards one at a time. Put each card on the leftmost pile whose top card is larger, and if there is none, start a new pile on the right. The number of piles at the end is the length of the longest increasing subsequence.

Two facts make that true. No increasing run can put two of its cards on the same pile, because each pile decreases from bottom to top, so a run has at most as many cards as there are piles. And when a card is placed on pile $j$, the top card of pile $j - 1$ is smaller than it and was dealt earlier — otherwise the card would have gone there — so following those links back from any card on the last pile traces an increasing run through every pile. The game is a proof as well as an algorithm, and the chain-covering argument of Dilworth and Mirsky is the same proof in the language of ordered sets.

It is also fast. Finding the pile for each card is a binary search, so a million cards take about twenty million comparisons. Every length in the figures below was computed this way, and on the smaller cases checked against a search of every pair.

Two, approached very slowly #

With patience sorting, the average longest run can be measured for shuffles of any reasonable size.

The ratio rises steadily and never reaches $2$. At twenty-five cards it is about $1.5$, at four hundred about $1.8$, at six thousand four hundred about $1.9$. The approach is slow because the correction shrinks only like $n^{-1/3}$ — to halve the distance to $2$ the deck has to grow eightfold. The dashed curve is the leading correction that the 1999 theorem below implies, and the measured points sit a little above it, as a further, smaller correction says they should.

This is a place where small cases genuinely mislead. A reader who shuffled a hundred decks of a hundred cards would measure a ratio near $1.7$ and could reasonably guess the constant was $\sqrt 3$ or $\pi/\sqrt 3$ or $e - 1$. The limit is $2$, and nothing short of a proof — or decks of millions of cards — would reveal it.

The worst order and a typical one #

Erdős and Szekeres’s theorem has an extremal order, and it is worth setting beside a random one.

In the extremal order both the longest climb and the longest fall are about $\sqrt n$, the least the theorem allows. In a random order, the longest climb is about $2\sqrt n$ and so is the longest fall, since reversing a random shuffle gives another random shuffle. The random order has both, twice over, where the theorem promises one, once.

That gap between guarantee and typical is the same one the previous essay found for convex polygons, where random crowds hold far larger convex polygons than the worst crowds are forced to. Extremal orders are rigid and rare: the blocks must be arranged exactly, and a single misplaced card lengthens a run. Out of all $n!$ orders, the ones with both runs close to $\sqrt n$ are a vanishing fraction, and the probability that a random shuffle’s longest climb falls below $(2 - \varepsilon)\sqrt n$ decays like $e^{-c\,n}$ — faster than for almost any other statistic of a shuffle.

The comparison is worth setting against the rest of Ramsey theory, where randomness usually plays the opposite part. For the party problem, a random colouring is the best escape anyone knows: Erdős proved in 1947 that colouring each pair by a coin toss avoids a large one-coloured group far better than any explicit colouring does, and nobody has constructed colourings that match it. For sequences it is the other way round. A random order is a poor escape — its runs are twice as long as necessary — and the best escape is a rigid construction of blocks. Whether randomness helps or hinders escaping depends on whether the structure being avoided is rare, as a one-coloured group is, or everywhere, as a rising chain is.

Fluctuations of size n to the one-sixth #

Knowing the average is not knowing how much a single shuffle can differ from it, and here the problem produced its biggest surprise.

If the longest run were a sum of many independent pieces, its fluctuations would be of size $\sqrt{\text{mean}}$, which here is about $n^{1/4}$. They are much smaller: of size $n^{1/6}$, about three and a half cards when $n = 2{,}000$. A shuffle of two thousand cards almost always has a longest climb within a handful of cards of $2\sqrt n - 1.77\,n^{1/6}$.

And the shape of the fluctuations is not the bell curve. In 1999 Jinho Baik, Percy Deift and Kurt Johansson proved that $(L_n - 2\sqrt n)/n^{1/6}$ converges to a distribution Craig Tracy and Harold Widom had found five years earlier in a completely different place: the largest eigenvalue of a large random Hermitian matrix, rescaled at the edge of the spectrum. It is lopsided, with a thin tail to the right and a thinner one to the left, mean $-1.77$ and spread $0.90$. The histogram shows its lopsidedness at two thousand cards: the bars fall off more slowly on the right than on the left.

That a card game and a random matrix share a limit law is the surprising connection this essay turns on, and it has since spread. The same Tracy–Widom distribution describes the fluctuations of a growing crystal’s edge in certain models, the position of the fastest particle in a simple model of traffic in which cars hop forward only into empty spaces, and the interface of a turbulent liquid crystal measured in the laboratory in 2010. The shared structure is a random growth process in which each step depends on a maximum over earlier steps — which is exactly what the longest rising chain is.

The shape a shuffle grows #

The 1977 proofs of the constant $2$ did not study the longest run alone. They studied a whole shape attached to the shuffle, of which the longest run is one measurement.

The Robinson–Schensted correspondence inserts the cards of a shuffle one at a time into rows, each card bumping the smallest larger card from its row down into the next. The result is a staircase-shaped arrangement of $n$ boxes — a partition of $n$, drawn as a diagram — and Craige Schensted proved in 1961 that the length of its first row is the longest increasing subsequence, and of its first column the longest decreasing one. Curtis Greene later showed that the first $k$ rows together give the largest union of $k$ increasing subsequences, so the whole shape measures the shuffle’s increasing structure at every scale.

Scaled by $\sqrt n$ and turned on its corner, the shape of a random shuffle’s diagram approaches a single curve,

$$\Omega(u) = \frac{2}{\pi}\Big(u \arcsin\frac u2 + \sqrt{4 - u^2}\Big), \qquad |u| \le 2,$$

meeting the two lines $v = |u|$ at $u = \pm 2$. The first row of the diagram runs out along one of those lines, and it reaches to $u = 2$ — which, undoing the scaling and rotation, is a row of length $2\sqrt n$. The constant in the longest-run problem is where the limit curve touches the corner.

It is worth comparing with the shape a random partition takes, which is a different curve for a different reason. There, every partition of $n$ was equally likely. Here, a partition’s chance is the number of shuffles that produce it, which by the correspondence is the square of the number of ways to fill its diagram with $1, \ldots, n$ increasing along rows and columns — the Plancherel weighting, which favours balanced shapes. Two natural ways of choosing a random partition, two different limit curves, and both found by solving a variational problem for the most likely shape.

Counting shuffles with random matrices #

The link to random matrices is not only a coincidence of limit laws. There is an exact identity underneath it, found by Ira Gessel in 1990 and put in its sharpest form by Eric Rains in 1998.

Pick a $k \times k$ unitary matrix at random — uniformly, in the sense that makes every rotation of complex $k$-space equally likely — and take its trace, the sum of its diagonal entries. The trace is a complex number whose size fluctuates from matrix to matrix. Rains proved that the average of its size raised to the power $2n$ is a whole number, and that the whole number is the count of shuffles of $n$ cards whose longest increasing run is at most $k$:

$$\begin{aligned} \mathbb{E}\,\bigl|\operatorname{tr} U\bigr|^{2n} &= \#\{\text{shuffles of } n \\ &\phantom{= \#\{}\text{with longest climb} \le k\}. \end{aligned}$$

For $k \ge n$ every shuffle qualifies and the average is $n!$. For $k = 1$ only the fully decreasing order qualifies, and a $1 \times 1$ unitary matrix is a point on the unit circle, whose size is one: the average is $1$. In between, the identity turns a question about cards into an integral over a group of matrices, and the integral can be analysed by the same methods that describe how eigenvalues crowd together — which is how Baik, Deift and Johansson proved their theorem.

Matrix integrals counting combinatorial objects have appeared before: the Gaussian integral that counts ways to pair a polygon’s edges, organised by the genus of the surface each pairing makes. The shuffle identity is a relative. In both, an average over random matrices is secretly a sum over arrangements, and the matrix side is where the asymptotics are tractable.

A process that sorts itself #

There is a way to watch the constant $2$ emerge rather than compute it, and it comes from turning the square on its side.

Sweep a vertical line across Hammersley’s square from left to right, and keep, at each moment, a set of marks on the line: one mark for each pile of the patience-sorting game run on the points passed so far, placed at the height of that pile’s top card. When the sweeping line meets a new point, the lowest mark above the point jumps down to it — the card goes on the leftmost pile whose top is larger — or a new mark appears if none is above. The number of marks when the line reaches the far side is the longest rising chain.

David Aldous and Persi Diaconis showed in 1995 that this system of jumping marks behaves, at large scale, like a fluid obeying a simple conservation law. The marks thin out as they are pushed downward and replenished from above, and solving the fluid equation for their density gives the answer: $2\sqrt n$ marks at the end. It is a proof by physics — a hydrodynamic limit — and it explains the constant as the solution of a differential equation rather than as the corner of a limit shape.

That two such different proofs give the same $2$, one through the shape of a tableau and one through the flow of a fluid of marks, is part of why the answer is trusted as deeply as it is. Neither proof, though, gives the fluctuations, and it was the matrix identity above that finally did.

What sampling cannot settle #

Every number in these figures is a sample. Two hundred shuffles at each size estimate the mean to about one per cent; fifteen hundred shuffles show the shape of the fluctuation law only roughly; one shuffle of two thousand five hundred cards shows the limit shape once. The claims that the ratio tends to exactly $2$, that the fluctuations are exactly of order $n^{1/6}$, and that their law is exactly Tracy–Widom’s are theorems, and the figures are consistent with them rather than evidence strong enough to have found them.

The finite sizes also hide how slowly everything converges. The histogram’s mean is $-1.6$ at two thousand cards, not the limiting $-1.77$, and the difference is a correction of relative size $n^{-1/3}$, the same slowness the growth figure shows. Anybody estimating the constants from simulation would be misled in the same direction at every size they could afford.

And the pictures are all of the uniform shuffle. Shuffles that are not uniform — a deck given only a few riffle shuffles, or points concentrated along the diagonal of the square — have longest runs governed by other laws, and the rigidity of $2\sqrt n$ is a property of complete randomness.

Still open: the constant in higher dimensions #

Hammersley’s square has a natural extension. Drop $n$ points at random in a $d$-dimensional cube and ask for the longest chain rising in every coordinate at once. Its length is about $c_d\, n^{1/d}$, and Béla Bollobás and Peter Winkler proved in 1988 that the constant $c_d$ exists for every $d$ and that $c_d$ tends to $e$ as the dimension grows.

For $d = 2$ the constant is $2$, by the theorems above. For $d = 3$ and every higher dimension, the value of $c_d$ is not known. It lies between known bounds, and simulations estimate it, but there is no Robinson–Schensted correspondence for three-dimensional orders, no limit shape to compute, and none of the algebraic structure that made the planar problem exactly solvable. The same question that has a closed answer in the plane has, one dimension up, only an estimate.