Mathematiker berechnen anhand des Beispiels "Tag", wie Zufälligkeiten auftreten

Die Aufgabe des "Tag" -Puzzles besteht darin, die nummerierten Kacheln anzuordnen. Heute haben Mathematiker das umgekehrte Problem gelöst - wie man das Rätsel löst.

Sie haben wahrscheinlich Tag gespielt. Dies ist ein frustrierendes, aber süchtig machendes Spiel, das aus 15 Kacheln und einem leeren Feld in einem Raster von 4 mal 4 besteht. Die Aufgabe besteht darin, die Kacheln zu verschieben und in aufsteigender Reihenfolge der Zahlen anzuordnen oder in einigen Versionen ein Bild daraus zusammenzusetzen.

Nach seinem Erscheinen in den 1870er Jahren trat es in die Standard-Reihe der Spiele ein. Darüber hinaus erregte es die Aufmerksamkeit von Mathematikern, die sich seit mehr als einem Jahrhundert mit Rätseln verschiedener Größe und anfänglicher Konfiguration befassten.

Heute gibt es neue Hinweise auf eine Lösung für das „Spiel um 15“ , allerdings in umgekehrter Reihenfolge. Die Mathematiker Yoon Chu und Robert Howe von der Stony Brook University bestimmten die Anzahl der Züge, die erforderlich waren, um ein geordnetes Feld in ein zufälliges zu verwandeln.

Eine Version des "Tag" -Problems mit Randomisierung wurde 1988 von Percy Deaconess vorgeschlagen. Er schlug vor, dass das Randomisieren von Rätseln jeder Größe ungefähr n ³ Züge erfordere. Das heißt, für ein 4 x 4-Feld sind 4 ³ oder 64 Züge erforderlich, und für ein 10 x 10-Feld sind 10 ³ oder 1.000 Züge erforderlich. (Obwohl sie immer noch als "Fünfzehn" bezeichnet werden, können Felder eine beliebige Anzahl von Leerzeichen enthalten, aus denen das richtige Quadrat besteht.)

Der Mathematiker an der Stanford University, Deaconess, schlug vor, dass seine Version des „15-Spiele“ -Problems für eine große Klasse ähnlicher Randomisierungsprobleme repräsentativ ist. Viele dieser Aufgaben hängen mit den grundlegenden Merkmalen der Natur zusammen, zum Beispiel mit dem Ortswechsel der DNA-Basenpaare, die eine genetische Mutation verursachen, und damit, wie Moleküle voneinander getrennt und ungeordnet werden - dies geschieht, wenn Eis schmilzt.

Die Diakonisse hoffte, dass wir, nachdem wir das Problem der Verflechtung von „Flecken“ verstanden hatten, verstehen würden, wie geordnete Systeme als Ganzes in einen einheitlich gemischten Zustand übergehen.

In Situationen wie "Tag" entwickelt sich die Zufälligkeit schrittweise. Stellen Sie sich ein vollständig geordnetes Feld mit einer Einheit oben links und einem leeren Bereich unten rechts vor. Wir verschieben die Kacheln so, dass sich der leere Raum um ein Feld in eine der vier möglichen Richtungen bewegt: nach oben, unten, links oder rechts. (Aus Gründen der mathematischen Eleganz haben Chu und Howe ein Feld betrachtet, dessen Kanten in einem Ring miteinander verbunden sind, damit die Kacheln nicht in den Ecken hängen bleiben.) Treffen wir eine zufällige Wahl. Jetzt befindet sich das Feld in einer neuen Konfiguration - nicht ganz in einer geordneten, aber nicht weit davon entfernt. Wiederholen Sie diesen Vorgang. Wenn Sie das leere Quadrat weiter verschieben, wird das Feld zunehmend von der ursprünglich bestellten Position entfernt.

Ein wichtiges Merkmal dieses Prozesses ist, dass bei jedem Schritt die nachfolgende Feldkonfiguration nur von der aktuellen Konfiguration abhängt. Dies erinnert an ein Spiel in Monopoly: Die Wahrscheinlichkeit, Würfel zu werfen und zwei Felder vom Park Place zum Boardwalk zu bewegen, hängt nicht von den Rollen ab, die uns zum Park Place Käfig geführt haben.

Die Fifteen Creeps schleichen schrittweise auf die Störung zu. Viele andere Systeme, wie z. B. das Schmelzen von Eis, werden auf die gleiche Weise randomisiert. Mathematiker untersuchen dieses Phänomen mit Modellen, die als Markov-Ketten bezeichnet werden. Markov-Ketten sind eine formale Methode zur Untersuchung von Randomisierungsprozessen, bei denen die nachfolgende Systemkonfiguration nur von der aktuellen Konfiguration abhängt. Sie stehen an der Spitze eines mathematischen Zufallsverständnisses.

"Markovs Ketten sind im goldenen Mittel - einerseits können wir sie noch analysieren, andererseits beschreiben sie viele der Phänomene, die uns interessieren", sagt der Mathematiker Yuval Perez, der wichtige Arbeiten in der Wahrscheinlichkeitstheorie durchgeführt hat.

In ihrer neuen Arbeit arbeiteten Chu und Howe mit der Randomisierung von "tag" wie mit der Markov-Kette. Insbesondere betrachteten sie eine Reihe von Zahlen, die als "Übergangsmatrix" der Markov-Kette bezeichnet werden. Die Übergangsmatrix ist ein umfangreicher Satz von Zahlen, der die Wahrscheinlichkeit bestimmt, dass sich ein „Spiel mit 15“ von einer Konfiguration zur nächsten bewegt, wenn wir uns dazu entschließen, den leeren Raum zufällig zu verschieben.

Das Verständnis der Übergangsmatrix ist der Schlüssel zur Berechnung der Anzahl von Zügen, die zum Randomisieren oder Mischen eines geordneten Feldes erforderlich sind. Insbesondere konzentrierten sich Chu und Hou auf die Definition der Zahlen, die die Übergangsmatrix charakterisieren - Zahlen, die als "Eigenwerte" bezeichnet werden.

„Wenn wir genügend Informationen über die Eigenwerte sammeln, können wir sehr genaue Mischungsinformationen erhalten“, sagt Howe.

Die Übergangsmatrix für „Flecken“ enthält eine große Menge an Informationen, die Billionen verschiedener Konfigurationen widerspiegeln, die selbst ein kleines 4 × 4-Feld erzeugen kann - mehr Informationen, als Mathematiker direkt verarbeiten können. Anstatt daher die Übergangsmatrix bei jedem Schritt des Feldwegs zur Randomisierung zu analysieren, fanden Chu und Howe heraus, wie das durchschnittliche Verhalten der gesamten Übergangsmatrix während der gesamten Fahrt zu charakterisieren ist.

Ihr Ansatz ähnelt dem, wie Sie herausfinden können, wo wir nach 1000 Würfeln am wahrscheinlichsten auf dem Monopoly-Feld landen: Sie können die Würfel tatsächlich so oft würfeln oder einfach den Durchschnitt mehrerer Würfel nehmen und sie extrapolieren.

Mit dieser Technik berechneten Chu und Howe die Eigenwerte der Übergangsmatrix, aus denen hervorging, wie viele Züge erforderlich waren, um die „Flecken“ zufällig zu ordnen. Sie erhielten sogar zwei Antworten, die auf zwei unterschiedlichen Definitionen der Zufälligkeit beruhten.

Zunächst wurde ein zufälliges Feld betrachtet, auf dem sich jede Kachel mit gleicher Wahrscheinlichkeit in einem beliebigen Feldquadrat befinden kann. Mit dieser Definition stellten sie fest, dass zum Randomisieren eines Feldes n zu n n ⁴ Bewegungen erforderlich wären (d. H. 256 Schritte für ein Feld 4 mal 4 und 10.000 Schritte für ein Feld 10 mal 10). Dies ist mehr als von Diaconis vorhergesagt (wie wir uns erinnern, schlug er ³ Schritte vor).

Die zweite Definition des Zufalls von Chu und Hou war strenger. Sie betrachteten ein randomisiertes Feld, das mit gleicher Wahrscheinlichkeit in einer der vielen möglichen Konfigurationen vorliegen könnte. Sie haben bewiesen, dass ein wenig mehr Schritte erforderlich wären, um eine solche Definition der Zufälligkeit zu erreichen - nicht mehr als etwa ⁴ log n Züge.

Chu und Howe zeigten, dass es schwieriger ist, das „15er-Spiel“ zufällig zuzuordnen, als Diaconis vorausgesagt hatte. In gewissem Sinne bedeutet dies, dass es länger als erwartet dauert, um die Ordnung im System vollständig zu beseitigen. Dank ihrer Arbeit ist „Tag“ mittlerweile eine der wenigen Randomisierungsaufgaben, bei denen laut Howe „tatsächlich die Anzahl der für die Randomisierung erforderlichen Schritte bekannt ist“.

Howe und Perez arbeiten nun daran, die Beweise zu erweitern. Sie interessieren sich unter anderem dafür, ob das Feld durch einen scharfen Sprung mit zunehmender Größe einen zufälligen Zustand erreicht. Systeme mit diesem Verhalten sehen überhaupt nicht zufällig aus, und nach nur einem Schritt stellen sie sich plötzlich als solche heraus.

"Wir verstehen nicht ganz, welche Markov-Ketten eine solche Plötzlichkeit aufweisen", sagt Perez. "Dies ist eines der größten Geheimnisse in diesem Bereich."