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.