The task of the “tag” puzzle is to arrange the numbered tiles. Today, mathematicians have solved the inverse problem - how to mix up the puzzle.
You probably played tag. This is a frustrating but addictive game consisting of 15 tiles and one empty space, arranged in a 4 by 4 grid. The task is to move the tiles and arrange them in ascending order of numbers or, in some versions, assembling an image from them.
After its appearance in the 1870s, it entered the standard set of games. In addition, it attracted the attention of mathematicians who have studied puzzles of various sizes and initial configurations for more than a century.
Today there is new evidence of the solution to the “game of 15” , but in the reverse order. The mathematicians Yoon Chu and Robert Howe of Stony Brook University determined the number of moves needed to turn an ordered field into a random one.
A version of the “tag” task with randomizations was proposed by Percy Deaconess in 1988. He suggested that randomizing puzzles of any size required approximately n 3 moves. That is, for a 4 by 4 field, 4 3 , or 64 moves are required, and for a 10 by 10 field, 10 3 , or 1,000 moves. (Although they are still referred to as “tag”, fields can have any number of spaces that make up the right square.)
The mathematician at Stanford University, Deaconess, suggested that his version of the “15-game” problem is representative of a large class of similar randomization issues. Many of these tasks are connected with the fundamental features of nature, for example, with the change of places of base pairs of DNA that cause a genetic mutation, and with how molecules are separated from each other and become disordered - this happens when ice melts.
Deaconess hoped that once we figured out the task of entangling “spots”, we would be able to understand how ordered systems as a whole turn into a uniformly mixed state.
In situations like "tag" randomness develops one step at a time. Imagine a fully ordered field, with a unit in the upper left and empty space in the lower right. Move the tiles so that the empty space moves one square in any of the four possible directions: up, down, left, or right. (For the sake of mathematical elegance, Chu and Howe considered a field whose edges are connected to each other in a ring, so the tiles never get stuck in the corners.) Let's make a random choice. Now the field is in a new configuration - not quite in an ordered, but not far from it. Repeat this process. If you continue to move the empty square, the field will move farther and farther from the original ordered location.
An important feature of this process is that at each step the subsequent field configuration depends only on the current configuration. This is reminiscent of a game in Monopoly: the probability of throwing dice and moving two squares from Park Place to Boardwalk does not depend on the rolls that led us to the Park Place cage.
The Fifteen Creeps creep toward the disorder gradually, one step at a time. Many other systems, such as melting ice, are randomized in 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 the subsequent configuration of the system depends only on the current configuration. They are at the forefront of a mathematical understanding of chance.
“Markov’s chains are in the golden mean - on the one hand, we can still analyze them, on the other, they describe many phenomena that are of interest to us,” says mathematician Yuval Perez, who carried out important work in probability theory.
In their new work, Chu and Howe worked with the randomization of "tag" as with the Markov chain. In particular, they considered a set of numbers called the “transition matrix" of the Markov chain. The transition matrix is an extensive set of numbers that determines the likelihood that a “game at 15” will move from one configuration to another if we decide to move empty space randomly.
Understanding the transition matrix is the key to calculating the number of moves needed to randomize or shuffle an ordered field. In particular, Chu and Hou focused on defining the set of numbers that characterize the transition matrix — numbers called “eigenvalues.”
“By collecting enough information about the eigenvalues, we can get very accurate mixing information,” says Howe.
The transition matrix for “spots” contains a huge amount of information that reflects trillions of different configurations that even a small 4 by 4 field can create. This is more information than mathematicians can process directly. Therefore, instead of analyzing the transition matrix at each step of the field’s path to randomization, Chu and Howe found out how to characterize the averaged behavior of the entire transition matrix throughout the journey.
Their approach is similar to how you can find out where we are most likely to end up on the Monopoly field after 1000 dice rolls: you can actually roll the dice so many times, or just take the average of several rolls and extrapolate them.
Using this technique, Chu and Howe calculated the eigenvalues of the transition matrix, which informed them how many moves needed to be made to randomize the “spots”. They even received two answers based on two different definitions of randomness.
First, they considered a randomized field, on which each tile with equal probability can be in any square of the field. With this definition, they found that to randomize a field n to n, n 4 moves would be needed (i.e. 256 steps for a field 4 by 4 and 10,000 steps for a field 10 by 10). This is more than what Diaconis predicted (as we recall, he suggested n 3 steps).
The second definition of chance by Chu and Hou was stricter. They considered a randomized field, which with equal probability could be in any of its many possible configurations. They proved that a little more steps would be required to achieve such a definition of randomness — no more than about n 4 log n moves.
Chu and Howe demonstrated that randomizing the “game of 15” is more difficult than Diaconis predicted; in a sense, this suggests that it takes more time than expected to completely eliminate order in the system. Thanks to their work, “tag” has now become one of the few randomization tasks in which, according to Howe, “in fact, the number of steps necessary for randomization is known.”
Howe and Perez are now working on expanding the evidence. Among other things, they are interested in whether the field reaches a randomized state with increasing size by a sharp jump. Systems with this behavior do not look random at all, and after just one step they suddenly turn out to be so.
“We don’t fully understand which Markov chains show such suddenness,” says Perez. “This is one of the biggest mysteries in this area.”