Mathematicians Calculate How Randomness Creeps In - Quanta Magazine

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 n³ moves to randomize puzzles of any size. So it would take 4³, or 64, moves for a 4-by-4 board and 10³, 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.

Let's block ads! (Why?)

"how" - Google News
November 12, 2019 at 10:38PM
https://ift.tt/2CyGlB7

Mathematicians Calculate How Randomness Creeps In - Quanta Magazine
"how" - Google News
https://ift.tt/2MfXd3I

Bagikan Berita Ini