Global AI and Data Science

Global AI & Data Science

Train, tune and distribute models with generative AI and machine learning capabilities

 View Only

Seven Shuffles

By Moloy De posted Fri October 28, 2022 08:37 PM

  
Diaconis, a magician-turned-mathematician at Stanford University, is regarded as the world's foremost expert on the mathematics of card shuffling. Throughout the surprisingly large scholarly literature on the topic, his name keeps popping up like the ace of spades in a magician's sleight-of-hand trick. So, when the Las Vegus company executives contacted him and offered to let him see the inner workings of their shuffling machine – a literal "black box" – he couldn't believe his luck.

With his collaborator Susan Holmes, a statistician at Stanford, Diaconis travelled to the company’s Las Vegas showroom to examine a prototype of their new machine. The pair soon discovered a flaw. Although the mechanical shuffling action appeared random, the mathematicians noticed that the resulting deck still had rising and falling sequences, which meant that they could make predictions about the card order.

To prove this to the company executives, Diaconis and Holmes devised a simple technique for guessing which card would be turned over next. If the first card flipped was the five of hearts, say, they guessed that the next card was the six of hearts, on the assumption that the sequence was rising. If the next card was actually lower – a four of hearts, for instance – this meant they were in a falling sequence, and their next guess was the three of hearts. With this simple strategy, the mathematicians were able to correctly guess nine or 10 cards per deck – one-fifth of the total – enough to double or triple the advantage of a competent card-counter.

Diaconis has spent a lifetime studying problems that live on the borderlands between order and randomness. Whether it is decoding scrambled messages, reassembling strands of DNA, or optimising web search engines, he has a knack for transforming these problems into a question about card shuffling.

His interest in cards began with a chance encounter in 1958. At age 13, at Tannen's Magic Emporium in New York City's Times Square, Diaconis met Alex Elmsley, a soft-spoken Scottish computer scientist and magician who had mastered the "perfect shuffle". Sometimes called the "faro shuffle" or simply "the technique", the perfect shuffle involves splitting a deck into two stacks of exactly 26 cards each and perfectly weaving them together like a zipper, alternately interleaving one card from each hand. Very few people can do it correctly in less than 10 seconds. Diaconis is one.

The perfect shuffle has been used by gamblers and magicians for centuries because it gives the illusion of randomly shuffling the cards. But it is far from random. In fact, if you perform the same sequence of perfect shuffles eight times in a row, the deck will magically restore its original order.

Diaconis says that he will have "seven shuffles suffice" carved on his tombstone. He is referring to his most famous realisation: that it takes seven "riffle shuffles" to sufficiently randomise a deck of cards. The riffle shuffle is the familiar technique, used by casinos and serious card players, in which the deck is cut in two and then thumbed together with a satisfying zip, often ending with a bridge finish that gathers the cards together into a neat pile.

The riffle shuffle is the unruly twin of the perfect shuffle. Instead of perfectly interleaving the two halves of the decks, the halves are mixed together in disorderly clumps, planting a seed of randomness that progressively mixes the cards with each shuffle.

After one or two riffle shuffles, some cards will remain in their original sequence. Even after four or five shuffles – far more than most casinos typically use – the deck will retain some trace of order. But once you shuffle the deck seven times, the cards become truly mixed, at least as far as most statistical tests can prove. Beyond that point, further mixing will not do much. "It's just as close to random as can be," Diaconis says.

To study riffle shuffles rigorously, Diaconis used a powerful mathematical tool called a Markov chain.

"A Markov chain is any repeated action where the outcome depends only on the current state and not on how that state was reached", explains Sami Hayes Assaf, a mathematician at the University of Southern California. This means that Markov chains have no "memory" of what came before. This is a pretty good model for shuffling cards, says Assaf. The result of the seventh shuffle depends only on the order of the cards after the sixth shuffle, not on how the deck was shuffled the five times prior to that.

Markov chains are widely used in statistics and computer science to handle sequences of random events, whether they are card shuffles or vibrating atoms or fluctuations in stock prices. In each case, the future "state" – the order of the deck, the energy of an atom, the value of a stock – depends only on what's happening now, not what happened before.

Despite their simplicity, Markov chains can be used to make predictions about the likelihood of certain events after many iterations. Google's PageRank algorithm, which ranks websites in their search engine results, is based on a Markov chain that models the behaviour of billions of internet users randomly clicking on web links.

Working with Dave Bayer, a mathematician at Columbia University in New York, Diaconis showed that the Markov chain describing riffle shuffles has a sharp transition from ordered to random after seven shuffles. This behaviour, known to mathematicians as a cut-off phenomenon, is a common feature of problems involving mixing. Think of stirring cream into coffee: as you stir, the cream forms thin white streaks in the black coffee before they suddenly, and irreversibly, become mixed.

Knowing which side of the cut-off a deck of cards is on – whether it is properly shuffled or if it still preserves some memory of its original order – gives gamblers a distinct advantage against the house.

In the 1990s, a group of students at Harvard and MIT were able to beat the odds playing blackjack at casinos around the US by using card counting and other methods to detect if the deck was properly shuffled. Casinos responded by introducing more sophisticated card-shuffling machines, and shuffling the deck before it is fully played, as well as stepped-up surveillance of players. But it is still rare to see a deck of cards shuffled by machine the requisite seven times at a casino.

Casino executives may not have paid much heed to Diaconis and his research, but he continues to have an enormous influence on mathematicians, statisticians and computer scientists who study randomness. At a conference held at Stanford in January 2020 to honour Diaconis's 75th birthday, colleagues from around the world gave talks on the mathematics of genetic classification, how cereal settles in a shaking box, and, of course, card shuffling.

Diaconis doesn't care for gambling much himself – he says there are better and more interesting ways to make a living. But he doesn't begrudge players who try to get an edge by using their brains.

"Thinking isn't cheating," he says. "Thinking is thinking."

QUESTION I: How many arrangements are possible with 52 cards?
QUESTION II: Pick up 5 cards randomly from a deck. What is the probability that it has an Ace?

REFERENCE: How a magician-mathematician revealed a casino loophole []
#GlobalAIandDataScience
#GlobalDataScience
0 comments
13 views

Permalink

https://community.ibm.com/community/user/blogs/moloy-de1/2022/10/23/points-to-ponder