Mathematicians Calculate How Randomness Creeps In
Lucy Reading-Ikkanda/Quanta Magazine
Introduction
You’ve probably played a 15 puzzle. It’s that frustrating yet addictive game with 15 tiles and a single empty space in a 4-by-4 grid. The goal is to slide the tiles around and put them in numerical order or, in some versions, arrange them to form an image.
The game has become a staple of party-favor bags since it was introduced in the 1870s. It has also caught the attention of mathematicians, who’ve spent more than a century studying solutions to puzzles of different sizes and startling configurations.
Now, a new proof solves the 15 puzzle, but in reverse. The mathematicians Yang Chu and Robert Hough of Stony Brook University have identified the number of moves required to turn an ordered board into a random one.
Persi Diaconis posed the randomization version of the 15-puzzle problem in 1988. He conjectured that it would take about n3 moves to randomize puzzles of any size. So it would take 43, or 64, moves for a 4-by-4 board and 103, or 1,000, moves for a 10-by-10 board. (While they’re still referred to as “15 puzzles,” boards can have any number of spaces that make up a perfect square.)
Diaconis, a mathematician at Stanford University, suggested that his version of the 15-puzzle problem was representative of a large class of similar randomization questions. Many of those problems have to do with fundamental features of the natural world, like the way base pairs in DNA exchange places to cause a genetic mutation, and how molecules split apart from each other and become disordered — which is what happens when ice melts.
By understanding problems like how a 15 puzzle scrambles, Diaconis hoped to get a handle on how ordered systems in general unwind into a uniformly mixed-up state.
In situations like a 15 puzzle, randomness develops one step at a time. Imagine a perfectly ordered board with the “1” tile in the upper left and the empty space in the lower right. Next, shift the tiles so that the empty space moves one square in any of four possible directions: up, down, left or right. (For the sake of mathematical elegance, Chu and Hough considered a board whose sides wrap around and meet each other, so that tiles are never stuck in corners.) Make the choice at random. The board will now be in a new configuration — no longer exactly in order, but not that far off either. Repeat this process. As you continue sliding the empty square around, the board will depart further from the original ordered arrangement.
An important feature of this process is that at each step, the subsequent configuration of the board depends only on the current configuration. It’s like how in a game of Monopoly, the odds of rolling the dice and moving two squares from Park Place to Boardwalk don’t depend on the rolls that got you to Park Place in the first place.
A 15 puzzle creeps toward disorder one step at a time. Many other systems, like melting ice, randomize the same way. Mathematicians study this phenomenon using models called Markov chains. Markov chains are a formal way of studying any randomization process in which a system’s subsequent configuration depends only on its current configuration. They are at the cutting edge of the mathematical understanding of randomness.
“They’re in this sweet spot where we can still analyze them, [yet] they describe many phenomena of interest,” said Yuval Peres, a mathematician who’s done important work in probability theory.
In their new work, Chu and Hough treated the randomization of the 15 puzzle as a Markov chain. In particular, they looked at a collection of numbers called the “transition matrix” of the Markov chain. The transition matrix is a vast set of numbers that specifies the likelihood that the 15 puzzle will go from one configuration to the next, if you decide at random how to move the empty space.
Understanding the transition matrix is the key to figuring out the number of moves needed to randomize, or mix, an ordered board. More specifically, Chu and Hough focused on identifying a set of numbers that characterize the transition matrix — numbers called “eigenvalues.”
“Once you know enough information about the eigenvalues, then you can get very precise information about the mixing,” said Hough.
The transition matrix for a 15 puzzle contains an overwhelming amount of information, reflecting the trillions of different configurations that even a small 4-by-4 board can take. It’s more information than mathematicians can grapple with directly. So instead of analyzing the transition matrix at each step in the board’s path toward randomization, Chu and Hough figured out how to characterize the average behavior of the transition matrix over the whole journey.
Their approach is similar to how, if you wanted to know where you’re likely to end up on a Monopoly board after 1,000 rolls of the dice, you could actually roll the dice that many times, or you could take the average value of a few rolls and extrapolate from there.
Using this technique, Chu and Hough calculated the eigenvalues of the transition matrix — which told them exactly how many moves it takes to randomize a 15 puzzle. They even came up with two answers based on two different definitions of randomness.
In the first, they considered a board to be randomized when every tile is equally likely to be located in any given square on the board. Under this definition, they found it takes about n4 steps to randomize an n-by-n board (so 256 steps for a 4-by-4 board and 10,000 steps for a 10-by-10 board). This is more steps than Diaconis predicted (remember he conjectured n3 steps).
Chu and Hough’s second definition of randomness was more stringent. They considered a board to be randomized when it was equally likely to be in any one of its many possible configurations. They proved it takes slightly more moves to achieve this definition of randomness — at most about n4 log n moves.
Chu and Hough demonstrated that it’s harder to randomize a 15 puzzle than Diaconis predicted — suggesting, in a way, that it takes longer than anticipated to completely efface order in a system. Thanks to their work, the 15 puzzle is now one of a relatively small number of randomization problems in which the “number of steps needed to randomize is essentially known,” said Hough.
Hough is now working with Peres to extend the proof. Among other things, they’re interested in knowing whether the puzzle board reaches a randomized state abruptly as the size of the board increases. Systems with this behavior don’t look random at all — and then with one more step, suddenly they are.
“We don’t fully understand which [Markov] chains” exhibit this abruptness, said Peres. “That’s one of the biggest mysteries of the subject.”
