Achim Klenke

Computersimulation zufälliger Pflasterungen: Domino und Rauten


Markovketten-Methode

Unter allen Pflasterungen eines Gebietes soll zufällig eine ausgewählt werden. Bei Simulationen mit der Markovkettenmethode werden, ausgehend von einer beliebigen Startkonfiguration, Schritt für Schritt einzelne Positionen gedreht. Da die Verteilung dieser Markovkette gegen die Gleichverteilung auf allen Konfigurationen konvergiert, sollte man nach einer sehr großen Anzahl von Schritten eine etwa gleichverteilte zufällige Pflasterung sehen. Nach dieser Methode sind die beiden forward Simulationen erzeugt worden.

Kopplung aus der Vergangenheit

Die von James Propp und David Wilson, sowie in einer Variante von Jim Fill, vorgeschlagene Methode des coupling from the past erzeugt Schritt für Schritt eine immer ältere Markovkette mit jeweils den gleichen zufälligen Vertauschungen in jedem Schritt.

Jeder Domino-Konfiguration ist ein Höhenprofil zugeordnet, das aus mehreren Ost-West-Pfaden besteht. Hierdurch lassen sich Konfigurationen (halb-)ordnen. Im Gegensatz dazu wird die Halbordnung auf den Rauten-Pflasterungen durch das schon optisch sich andeutende Höhenprofil gegeben.

Die Kette wurde weit genug in der Vergangenheit gestartet, wenn die kleinste und die größte Konfiguration durch die Vertauschungen in die selbe Konfiguration überführt werden. Die entsprechenden Computersimulatioen zeigen daher parallel die aus der größten und aus der kleinster Konfiguration hervorgehenden Pflasterungen und zusätzlich die entsprechenden Pfade.


Java Applets der Simulationen

Im Rahmen ihrer Diplomarbeit hat Frau Kerstin Roll 2007 Simulationen als Java Applets geschrieben. Diese Simulationen können hier gestartet werden.

Domino Pflasterung
Domino
Rauten Pflasterung
Lozenge
Markovkette Markovkette
CFTP CFTP


Link

Eine Übersicht über die aktuelle Entwicklung dieses Forschungsgebietes findet sich auf der Website von David Wilson
ak, 07.11.2009