Thought Toys · Chance · Exhibit 124
Riffle a new deck once and it is obviously still sorted. Riffle it four times and it looks mixed — and it is still, to three decimal places, exactly as far from random as when you started. Then, between the fifth shuffle and the eighth, the distance collapses. Randomness does not arrive gradually. It arrives as a cliff, and for fifty-two cards the edge of the cliff is seven.
The deck, left to right; bar height is where each card started ●● rising sequences, alternating
—
—
The row of bars is the deck. Each bar is one card, standing where it is now, and its height is where it started — a fresh deck is a clean staircase from short to tall. A riffle cuts the deck near the middle and lets cards fall from the two halves, each half releasing cards about as often as its share of what is left. That is how people actually shuffle, and it is the shuffle studied by Gilbert, Shannon and Reeds, and later by Bayer and Diaconis.
Press Riffle once. The staircase becomes two interleaved staircases, one amber and one cyan. Every card is still in order with the cards it started next to; they have simply been threaded through one another. Those threads are the rising sequences, and each riffle can at most double their number: two after one shuffle, four after two, eight after three.
Now watch the chart. It shows the deck's distance from a truly random one, computed exactly, not estimated. After four riffles a fifty-two card deck looks thoroughly mixed — and the distance still reads 1.000. Nothing has happened to it that a keen observer could not undo. There is even a bet you can make on such a deck that wins far more often than it should.
Then the fifth riffle moves the needle, the sixth moves it a lot, and the seventh drops it past the halfway mark. After that each shuffle simply halves what is left. The change is a cliff because of the arithmetic of the sequences. For a long time there are far too few of them for the deck to be anywhere near random. Then, once there are enough, every extra shuffle finishes the job twice as well as the last. Mathematicians call this shape a cutoff.
Change the deck size and the cliff moves, but slowly. Eight cards need three riffles, a full deck seven, two decks eight. Multiply the cards by four and you owe about three more shuffles, not four times as many. The textbook rate is one and a half shuffles per doubling of the deck. For real deck sizes the halfway point runs a shuffle or two under that rate: the formula says 8.6 for fifty-two cards, and the exact answer is seven.
Finally, press Perfect shuffles instead. A perfect shuffle cuts exactly in half and alternates the cards one for one, which is what a very skilled dealer can do. After three or four the deck looks at least as mixed as before. But the chart is a flat line at one, because a perfect shuffle is not random at all: it is a single fixed rearrangement, done again. Keep pressing and after eight of them every one of the fifty-two cards is back exactly where it began. The mess was never mixing. Mixing needs the sloppiness.
The rule, exactly. Number the cards 0 to n − 1 in their starting order. An arrangement's rising sequences are the maximal runs of consecutive original cards that still appear in increasing order. Bayer and Diaconis (1992) proved that after k riffles the chance of ending in a given arrangement depends only on its number of rising sequences r:
Pk(arrangement) = C(2k + n − r, n) / 2nkThere are exactly ⟨n, r − 1⟩ arrangements with r rising sequences, an Eulerian number. So the total-variation distance from a uniformly random deck is a finite sum, which the page evaluates in exact integer arithmetic:
distance = ½ ∑r ⟨n, r−1⟩ · | Pk − 1/n! |"Distance from random" is that number. It has a plain meaning: it is the largest possible gap, over every yes-or-no question you could ask about the deck's whole arrangement, between the true chance and the chance for a random deck. The "best possible bet" readout is the same number said as a betting edge, in percentage points of probability. The shuffle itself is the Gilbert–Shannon–Reeds model: a Binomial(n, ½) cut, then drops in proportion to the halves. Real hands tend to drop cards in slightly more regular runs than the model does, which preserves a little more order, so real shuffles are slightly worse than this, not better.
"Exact" should be checkable, so here are the numbers behind the rounding. One riffle of four cards leaves a distance of exactly ½; three riffles of eight cards leave exactly 87751/262144, which is 0.3347. For fifty-two cards the page prints 1.000 through four riffles: through three the true value differs from 1 by less than one part in 1040, because so few arrangements are reachable at all, and after four it is 1 − 4.7×10−7.
Verified in node (improve/verify/124-riffle-shuffle.js, 8 checks, two of them
negative controls, all before this page existed):
The famous "seven" is a rule of thumb for this measure of randomness, and a careful one. Some games care about less than the whole arrangement, and for those the deck can be usable earlier; a few care about more, and for those seven is not enough. The number the page reports is the strict one, and it is exact.
Also in Chance: Buffon's needle →