Coming up trumps

THERE'S not much Persi Diaconis can't do with a deck of cards. As well as the usual tricks, he can perform many of his own devising, and without a hint of boastfulness he declares that when he shuffles a deck- even with only one hand - the cards interleave in perfect sequence. But unlike most magicians, Diaconis's skills go beyond pulling the queen of hearts out of your ear. Thirty-one years ago he turned himself into a mathematician.

But he hasn't abandoned his first love. Diaconis, now a professor at Stanford University in Palo Alto, California, has a penchant for translating mathematical problems into questions about cards. Ten years ago, along with David Bayer of Columbia, he made headlines for proving that it takes seven ordinary "riffle" shuffles to randomise a deck. So it was no surprise when he got a letter from a major manufacturer of card-shuffling machines asking his advice.

The company, whose identity Diaconis considerately shields, had produced a prototype for a new automated card shuffler, intended for the casinos of Las Vegas. But the engineers weren't sure whether the machine truly randomised the deck. Could Diaconis help?

The company had good reason to be anxious. Not long before, it had discovered that a gang of hustlers were exploiting one of its other machines - an elaborate six-deck shuffler with a glass window - by training a hidden video camera on the glass, then transmitting the pictures by radio to a car parked in the casino's lot. Their partners outside would slow down the tape to figure out how the cards were falling and broadcast the sequence to the gamblers inside. The hustlers won millions of dollars before they were finally caught , Understandably, the company wanted to make sure that the new machine was hustler-proof. "When the company got in touch with me, my reaction was, 'Really, they're going to let me come and look at the machines?'" says Diaconis. "I'd pay them to look. It was very exciting." Soon, he and his collaborator, Susan Holmes, a statistician at Stanford, found themselves in the company's Las Vegas showroom.

The new machine is a "shelf shuffler". It pulls cards one by one from the bottom of the deck, and slides each card onto one of 10 platforms. A random number generator chooses a number between 1 and 10 to decide which platform each card lands on. A second random number generator decides whether to put the card on the top or bottom of the pile already on the platform. Finally, when all the cards have been dealt, a third random number generator picks the order in which the 10 piles of cards are spat out to build up the shuffled deck. Sounds pretty random.

Yet by the end of Diaconis and Holmes's analysis, they had not only shown that the machine fails to randomise the deck, but discovered formulae that might illuminate more abstract questions about the far reaches of modern mathematics and physics.

Diaconis is no stranger to the stratagems of gamblers, having been a card counter in his magician years. "But I realised that you make much more money proving theorems than you do counting cards in a casino," he says. A card counter memorises the sequence in which cards are played, to gain some advantage. For example, if the cards are gathered and then imperfectly shuffled, the counter can make an educated guess about the order of the next deal, gaining enough of an edge to make money.

So how do you test how well a shuffling machine is doing its job? One way would be to put deck after deck through the machine and see whether each possible card sequence emerges from the machine as often as every other. But the number of arrangements of 52 cards is enormous - roughly l followed by 58 zeros, or more than the number of atoms in the Sun.

Since brute force doesn't work, Diaconis and Holmes set about abstracting the essential elements of the device. It's easiest to understand if you start with a deck in a standard order. Let's say, going from top to bottom of the pack, ace to king of spades, then ace to king of hearts, then diamonds and clubs.
When a deck is passed through the shelf shuffler, cards put on top of any pile on a platform end up in the same order in which they appeared before the shuffle. For instance, if the three and eight of spades are both put on the top of the pile on platform four, the three will be above the eight, because it was put on the pile later. In the same way, the cards put on the bottom of a pile will be in the opposite order from their original sequence. So since the machine has 10 platforms, the deck will end up consisting of 20 groups of cards which alternate between ascending and descending card orders.

That means you can get exactly the same result by labelling each card randomly with a number from 1 to 20, then gathering into piles the cards with the same number. First gather the cards labelled "one", preserving their order in the deck, then the cards labelled "two", reversing their order, then the "threes", preserving their order, then the "fours", reversing their order, and so on. When you look at it this way, it becomes clear that the final act of the machine - spitting out the piles in random order- achieves nothing at all, since the cards have already been assigned numbers in a random way.

Perhaps the first bit of randomising is good enough to do the job anyway? Not so. Diaconis and Holmes noticed that the ace of spades is too likely to be on top after the shuffle. If a deck is properly shuffled, the chance that the top card is the ace of spades is just 1 in 52. But using the shelf shuffler on our standard pack, the ace of spades has a 1 in 20 chance of being assigned to group number 1, and if it is, it must be on top, as it is the top card in the deck. So the chance that the shelf-shuffler will leave the ace on top of the pack when it's reassembled is an inordinate 1 in 20.

Just knowing that the probabilities are biased for one card wouldn't change things much for the games played in casinos, Diaconis says. But if the same is true for lots of cards, most games would be vulnerable to hustlers.

Diaconis's previous work on riffle shuffles - in which two piles of cards on a flat surface are merged by pulling up and releasing the edge of each pile - provided the answer. He used a generalised form of the riffle shuffle analysis, involving abstract algebraic entities called Coxeter groups. "The amazing thing was that the shelf shuffling problem boiled down to this mathematics we had previously done for our esoteric purposes," he says. "There were some very contrived ways of shuffling we had analysed, and I remember saying at the time, 'Why are we doing this? It's just ridiculous.' But one of those mathematical models turned out to fit this physical model perfectly." And it showed that the shelf shuffler mixes the deck only a little better than three riffle shuffles - well shy of the seven shuffles needed to randomise a deck.

Diaconis and Holmes were left with the problem of explaining their discovery to the company's engineers. "I could hardly start talking to them about Coxeter groups," Diaconis says. What the manufacturers really wanted to know was how many cards a gambler could guess correctly if a deck was mixed in the shelf shuffler.

Holmes became fascinated by this puzzle. In a randomly mixed deck, if you try to guess the value of the first card, you have only a l in 52 chance of being correct. On the next card you have a 1 in 51 chance of guessing right, as one card has been eliminated. You have a 1 in 50 chance of guessing the third card, and so on. If you guess your way through the whole deck, you can expect to be right about four or five times.
But if the deck has gone through the shelf shuffler, and you know what the order of cards was to start with, you can do much better, That is because the order of cards that emerges has a sawtooth pattern, alternating between upward and downward sequences. With our standard deck, you should start by guessing the ace of spades as you have a l in 20 chance of being right. If that guess is correct, guess the two of spades next, as it also has a 1 in 20 chance of being in group number one, and if it is, then it must come right after the ace. But if the first card was the four of hearts, say, guess the five of hearts next, for the same reason.

Each time a card is shown to you, make your next guess the card one higher than the card you've just seen, until the card that's shown to you is lower than the sequence of cards so far. At that point, the sequence has shifted to one of the downwards parts of the sawtooth, so you should switch to guessing downwards. If you see the eight of diamonds, say, guess that the next card will be the seven of diamonds (unless the seven has already been turned up, in which case you should guess the six). Keep guessing downwards until a card comes up that's higher than the one before it, then switch back to guessing upwards. Holmes showed that by following the switching strategy, you can expect to guess correctly nine or ten cards in the deck. This was enough to unsettle the company engineers. "They were aghast," Diaconis recalls.

They haven't told Diaconis how they plan to fix the problem. One plan was to have someone shuffle the deck once or twice before putting it in the machine, but that would surely defeat the purpose. They will probably have to change the internal workings of the machine.

All is not lost, however, because the shelf shuffler might have something to teach mathematicians. After realising that the ace of spades was likely to remain at the top of the deck after a shuffle, Diaconis started looking for formulae for how many cards would remain in their original positions after the deck was passed through the machine. His postdoctoral student Jason Fulman, now at the University of Pittsburgh in Pennsylvania, carried the question one step further, figuring out precise formulae to predict how many cards would have their positions exchanged with each other or cycled around in some more complex way after the shuffle.

Unexpectedly, Fulman's formulae linked shelf shuffling to a strange kind of geometry called noncommutative geometry. Some physicists hope this might lead to a new model of the Universe that reconciles quantum mechanics and Einstein's general theory of relativity. In noncommutative geometry, on extremely tiny scales of distance the smooth structure of Einstein's space-time is replaced by a messy geometry in which a particle is not located at a point but instead is smeared out over a "cell", in keeping with the ideas of quantum mechanics. Fulman's formulae provide a new way to count the number of holes in this strange geometry. "The shelf-shuffling formulae might lead to new physics," Diaconis says.

Now he has conquered both ordinary riffle shuffling and shelf shuffling, it might seem that there are no more card-shuffling peaks left to climb. But for Diaconis, the Everest of shuffling still looms before him: "shmooshing". This technique, beloved of children, involves spreading the cards on the table and, well, shmooshing them around, then gathering them up. How long do you have to shmoosh a deck before it's randomised? "That's one of the great open problems of my life," he says.