La tarea del rompecabezas de "etiqueta" es organizar las fichas numeradas. Hoy, los matemáticos han resuelto el problema inverso: cómo mezclar el rompecabezas.Probablemente jugaste etiqueta. Este es un juego frustrante pero adictivo que consta de 15 fichas y un espacio vacío, organizado en una cuadrícula de 4 por 4. La tarea es mover las fichas y organizarlas en orden ascendente de números o, en algunas versiones, ensamblar una imagen a partir de ellas.
Después de su aparición en la década de 1870, ingresó al conjunto estándar de juegos. Además, atrajo la atención de matemáticos que han estudiado acertijos de varios tamaños y configuraciones iniciales durante más de un siglo.
Hoy
hay nuevas pruebas de una solución para el "juego a los 15" , pero en orden inverso. Los matemáticos Yoon Chu y
Robert Howe de la Universidad Stony Brook determinaron la cantidad de movimientos necesarios para convertir un campo ordenado en uno aleatorio.
Percy Deaconess propuso una versión del problema de "etiqueta" con la aleatorización en 1988. Sugirió que aleatorizar rompecabezas de cualquier tamaño requería aproximadamente
n 3 movimientos. Es decir, para un campo de 4 por 4, se requerirán 4
3 o 64 movimientos, y para un campo de 10 por 10, 10
3 o 1,000 movimientos. (Aunque todavía se conocen como "Quince", los campos pueden tener cualquier cantidad de espacios que componen el cuadrado correcto).
El matemático de la Universidad de Stanford, Deaconess, sugirió que su versión del problema de los "15 juegos" es representativa de una gran clase de problemas de aleatorización similares. Muchas de estas tareas están relacionadas con las características fundamentales de la naturaleza, por ejemplo, con el cambio de lugares de los pares de bases de ADN que causan una mutación genética, y con la forma en que las moléculas se separan unas de otras y se desordenan; esto sucede cuando el hielo se derrite.
Deaconess esperaba que al haber entendido el problema del enredo de "puntos", pudiéramos entender cómo los sistemas ordenados en su conjunto se convierten en un estado uniformemente mixto.
En situaciones como "etiqueta", la aleatoriedad se desarrolla paso a paso. Imagine un campo completamente ordenado, con una unidad en la esquina superior izquierda y un espacio vacío en la esquina inferior derecha. Muevemos las fichas para que el espacio vacío se mueva un cuadrado en cualquiera de las cuatro direcciones posibles: arriba, abajo, izquierda o derecha. (En aras de la elegancia matemática, Chu y Howe consideraron un campo cuyos bordes están conectados entre sí en un anillo, por lo que las fichas nunca se atascan en las esquinas). Hagamos una elección al azar. Ahora el campo está en una nueva configuración, no del todo ordenada, pero no muy lejos de ella. Repite este proceso. Si continúa moviendo el cuadrado vacío, el campo se alejará cada vez más de la ubicación ordenada original.
Una característica importante de este proceso es que en cada paso la configuración de campo posterior depende solo de la configuración actual. Esto recuerda a un juego en Monopoly: la probabilidad de lanzar dados y mover dos casillas de Park Place a Boardwalk no depende de las tiradas que nos llevaron a Park Place.
Los Quince Creeps se arrastran gradualmente hacia el desorden, un paso a la vez. Muchos otros sistemas, como el derretimiento del hielo, se aleatorizan de la misma manera. Los matemáticos estudian este fenómeno utilizando modelos llamados "cadenas de Markov". Las cadenas de Markov son una forma formal de estudiar cualquier proceso de aleatorización en el que la configuración posterior del sistema depende solo de la configuración actual. Están a la vanguardia de una comprensión matemática del azar.
"Las cadenas de Markov están en el medio dorado: por un lado, todavía podemos analizarlas, por otro, describen muchos de los fenómenos que nos interesan", dice el matemático Yuval Pérez, quien realizó un trabajo importante en la teoría de la probabilidad.
En su nuevo trabajo, Chu y Howe trabajaron con la aleatorización de "etiqueta" como con la cadena de Markov. En particular, consideraron un conjunto de números llamado "matriz de transición" de la cadena de Markov. La matriz de transición es un extenso conjunto de números que determina la probabilidad de que un "juego a 15" se mueva de una configuración a otra si decidimos mover el espacio vacío al azar.
Comprender la matriz de transición es la clave para calcular el número de movimientos necesarios para aleatorizar o barajar un campo ordenado. En particular, Chu y Hou se centraron en definir el conjunto de números que caracterizan la matriz de transición, números llamados "valores propios".
"Al recopilar suficiente información sobre los valores propios, podemos obtener información de mezcla muy precisa", dice Howe.
La matriz de transición para "puntos" contiene una gran cantidad de información que refleja billones de configuraciones diferentes que incluso puede crear un pequeño campo de 4 por 4. Esta es más información de la que los matemáticos pueden procesar directamente. Por lo tanto, en lugar de analizar la matriz de transición en cada paso de la ruta de campo hacia la aleatorización, Chu y Howe descubrieron cómo caracterizar el comportamiento promedio de toda la matriz de transición a lo largo del viaje.
Su enfoque es similar a cómo puede averiguar dónde es más probable que terminemos en el campo Monopolio después de 1000 tiradas de dados: en realidad puede tirar los dados tantas veces, o simplemente tomar el promedio de varias tiradas y extrapolarlas.
Usando esta técnica, Chu y Howe calcularon los valores propios de la matriz de transición, que les indicó cuántos movimientos debían hacerse para aleatorizar los "puntos". Incluso recibieron dos respuestas basadas en dos definiciones diferentes de aleatoriedad.
Primero, consideraron un campo aleatorio, en el que cada ficha con la misma probabilidad puede estar en cualquier cuadrado del campo. Con esta definición, descubrieron que para aleatorizar un campo
nn , se necesitarían
n 4 movimientos (es decir, 256 pasos para un campo 4 por 4 y 10,000 pasos para un campo 10 por 10). Esto es más de lo que Diaconis predijo (como recordamos, sugirió
n 3 pasos).
La segunda definición de oportunidad de Chu y Hou era más estricta. Consideraron un campo aleatorio, que con igual probabilidad podría estar en cualquiera de sus muchas configuraciones posibles. Probaron que se necesitarían un poco más de pasos para lograr tal definición de aleatoriedad, no más de aproximadamente
n 4 log
n movimientos.
Chu y Howe demostraron que aleatorizar el "juego de 15" es más difícil de lo que Diaconis predijo; en cierto sentido, esto sugiere que lleva más tiempo del esperado para eliminar completamente el orden en el sistema. Gracias a su trabajo, la "etiqueta" se ha convertido en una de las pocas tareas de aleatorización en las que, según Howe, "de hecho, se conoce el número de pasos necesarios para la aleatorización".
Howe y Pérez ahora están trabajando para expandir la evidencia. Entre otras cosas, están interesados en saber si el campo alcanza un estado aleatorio con un tamaño creciente mediante un salto brusco. Los sistemas con este comportamiento no parecen aleatorios en absoluto, y después de un solo paso, de repente resultan ser así.
"No entendemos completamente qué cadenas de Markov demuestran tal brusquedad", dice Pérez. "Este es uno de los mayores misterios en esta área".