To rigorously study fast mixing, Diaconis used a powerful mathematical tool called a Markov chain.
“A Markov chain is any repeated action whose 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 outcome of the seventh deck depends only on the order of the cards after the sixth deck, not how the deck was shuffled the previous five times.
Markov chains are widely used in statistics and computer science to handle sequences of random events, whether they be decks of cards, 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 happens now, not what happened before.
Despite their simplicity, Markov chains can be used to make predictions about the probability of certain events after many iterations. Google’s PageRank algorithm, which ranks websites in its search engine results, is based on a Markov chain that models the behavior of billions of Internet users who randomly click on web links.
Working with Dave Bayer, a mathematician at Columbia University in New York, Diaconis showed that the Markov chain that describes fast mixing transitions sharply from ordered to random after seven mixing. This behavior, known to mathematicians as a shear phenomenon, is a common feature of problems involving mixtures. Think of mixing the cream with the coffee: as you stir, the cream forms fine white streaks in the black coffee before suddenly and irreversibly mixing.
Knowing which side of the court a deck of cards is on, whether it was shuffled correctly, or still retains some memory of its original order, gives players a distinct advantage against the house.
In the 1990s, a group of Harvard and MIT students were able to beat the odds playing blackjack in US casinos by using card counting and other methods to detect if the deck was shuffled correctly. Casinos responded by introducing more sophisticated machines to shuffle cards and shuffle the deck before it is fully played, as well as intensifying surveillance of players. But it is still rare to see a deck of cards shuffled by a machine the required seven times in a casino.
Casino executives may not have paid much attention to Diaconis and his research, but he continues to have a huge influence on mathematicians, statisticians, and computer scientists who study randomness. At a conference held at Stanford in January 2020 to honor Diaconis’s 75th birthday, colleagues from around the world gave talks on the math of genetic sorting, how cereal settles in a shaker box, and, of course, how shuffle the cards.
Diaconis is not much into gambling, says there are better and more interesting ways to make a living. But he doesn’t envy players who try to gain an advantage using their brains.
“Thinking is not cheating,” he says. “Thinking is thinking.”
*Shane Keating is a science writer and sSenior Lecturer in Mathematics and Oceanography at the University of New South Wales, Sydney
Join a million future fans by liking us on Facebookor follow us on Twitter either Instagram.
If you liked this story sign up for the weekly bbc.com feature newslettercalled “The Essential List” – a handpicked selection of BBC stories Future, Culture, Laboral life, Trip Y Reel delivered to your inbox every Friday.
Leave a Comment