Visuell erklärt
von Victor Powell
mit Text von Lewis Lehe
Markov-Ketten, benannt nach Andrey Markov, sind mathematische Systeme, die von einem „Zustand“ (einer Situation oder einem Satz von Werten) zu einem anderen springen. Wenn man zum Beispiel ein Markov-Kettenmodell des Verhaltens eines Babys erstellt, könnte man „Spielen“, „Essen“, „Schlafen“ und „Weinen“ als Zustände einbeziehen, die zusammen mit anderen Verhaltensweisen einen „Zustandsraum“ bilden könnten: eine Liste aller möglichen Zustände. Zusätzlich zum Zustandsraum gibt eine Markov-Kette die Wahrscheinlichkeit an, mit der man von einem Zustand in einen anderen übergehen kann – z. B, die Wahrscheinlichkeit, dass ein Baby, das gerade spielt, in den nächsten fünf Minuten einschläft, ohne vorher zu weinen.
Eine einfache Markov-Kette mit zwei Zuständen ist unten dargestellt.
Geschwindigkeit
Bei zwei Zuständen (A und B) in unserem Zustandsraum gibt es vier mögliche Übergänge (nicht zwei, da ein Zustand in sich selbst zurückkehren kann). Wenn wir uns bei ‚A‘ befinden, können wir nach ‚B‘ übergehen oder bei ‚A‘ bleiben. Wenn wir bei ‚B‘ sind, können wir zu ‚A‘ übergehen oder bei ‚B‘ bleiben. In diesem Diagramm mit zwei Zuständen ist die Wahrscheinlichkeit des Übergangs von einem Zustand zu einem anderen Zustand 0,5.
Natürlich zeichnen echte Modellierer nicht immer Markov-Ketten-Diagramme. Stattdessen verwenden sie eine „Übergangsmatrix“, um die Übergangswahrscheinlichkeiten zu ermitteln. Jeder Zustand im Zustandsraum ist einmal als Zeile und einmal als Spalte enthalten, und jede Zelle in der Matrix gibt die Wahrscheinlichkeit des Übergangs vom Zustand in der Zeile zum Zustand in der Spalte an. In der Matrix erfüllen die Zellen also die gleiche Aufgabe wie die Pfeile im Diagramm.
A B
Wenn der Zustandsraum einen Zustand hinzufügt, fügen wir eine Zeile und eine Spalte hinzu, so dass zu jeder bestehenden Spalte und Zeile eine Zelle hinzukommt. Das bedeutet, dass die Anzahl der Zellen quadratisch wächst, wenn wir unserer Markov-Kette Zustände hinzufügen. Eine Übergangsmatrix ist also schnell zur Hand, es sei denn, man möchte ein Markov-Ketten-Diagramm zeichnen.
Eine Verwendung von Markov-Ketten ist die Einbeziehung realer Phänomene in Computersimulationen. So könnte man zum Beispiel prüfen, wie häufig ein neuer Damm überläuft, was von der Anzahl der aufeinanderfolgenden Regentage abhängt. Um dieses Modell zu erstellen, gehen wir von folgendem Muster von Regentagen (R) und Sonnentagen (S) aus:
Eine Möglichkeit, dieses Wetter zu simulieren, wäre einfach zu sagen: „Die Hälfte der Tage ist regnerisch. Daher hat jeder Tag in unserer Simulation eine fünfzigprozentige Chance auf Regen.“ Diese Regel würde in der Simulation die folgende Sequenz erzeugen:
Haben Sie bemerkt, dass die obige Sequenz nicht ganz wie das Original aussieht? Die zweite Sequenz scheint umherzuspringen, während die erste (die realen Daten) eine „Stetigkeit“ zu haben scheint. Wenn es in den realen Daten an einem Tag sonnig (S) ist, dann ist es am nächsten Tag auch viel wahrscheinlicher, dass es sonnig ist.
Wir können diese „Stickyness“ mit einer Markov-Kette mit zwei Zuständen abbilden. Wenn sich die Markov-Kette im Zustand „R“ befindet, hat sie eine Wahrscheinlichkeit von 0,9, an Ort und Stelle zu bleiben, und eine Wahrscheinlichkeit von 0,1, in den Zustand „S“ zu wechseln. Ebenso hat der Zustand „S“ eine Wahrscheinlichkeit von 0,9, an Ort und Stelle zu bleiben, und eine Wahrscheinlichkeit von 0,1, in den Zustand „R“ überzugehen.
In den Händen von Metereologen, Ökologen, Informatikern, Finanzingenieuren und anderen Personen, die große Phänomene modellieren müssen, können Markov-Ketten ziemlich groß und mächtig werden. Der Algorithmus, den Google verwendet, um die Reihenfolge der Suchergebnisse zu bestimmen, PageRank genannt, ist eine Art Markov-Kette.
Oben haben wir eine Markov-Ketten-„Spielwiese“ eingefügt, auf der Sie Ihre eigenen Markov-Ketten erstellen können, indem Sie mit einer Übergangsmatrix herumspielen. Hier sind ein paar Beispiele: ex1, ex2, ex3 oder generieren Sie eine zufällig. Der Text der Übergangsmatrix wird rot, wenn es sich bei der angegebenen Matrix nicht um eine gültige Übergangsmatrix handelt. Die Zeilen der Übergangsmatrix müssen die Summe 1 ergeben und es müssen genauso viele Zeilen wie Spalten vorhanden sein.
Sie können auch eine Vollbildversion unter setosa.io/markov
aufrufen