Übergangsgraph
Übergangsgraphen sind spezielle gerichtete Graphen mit Kantengewichten, die eine Verbindung zwischen Stochastik und Graphentheorie schlagen. Sie eignen sich besonders zur anschaulichen Darstellung von zeitdiskreten homogenen Markow-Ketten.
Definition
Ein gerichteter und kantengewichteter Graph <math> G </math> heißt Übergangsgraph, wenn für jeden Knoten <math>i</math> die Kantengewichte der von <math>i</math> ausgehenden Kanten größer 0 sind und sich zu 1 aufsummieren:
- <math> \sum_{j \in N_G^+(i)} c_{ij}=1 </math>.
Dabei ist <math>N_G^+(i)</math> die Nachfolgermenge von Knoten <math>i</math>, also die Menge aller Knoten, die durch von <math>i</math> ausgehende Kanten erreicht werden können.
Äquivalent dazu ist, dass der Graph <math> G </math> Adjazenzgraph einer zeilenstochastischen Matrix ist.
Verwendung
Übergangsgraphen dienen zur anschaulichen Darstellung von homogenen Markow-Ketten mit endlichem Zustandsraum in diskreter Zeit. Dabei entspricht jeder Knoten einem Zustand des Systems und die Kantengewichte sind die Übergangswahrscheinlichkeiten zwischen den Zuständen. Dann ist <math> c_{ij} </math> genau die Wahrscheinlichkeit, vom Zustand <math> i </math> in den Zustand <math> j </math> zu wechseln. Einige Eigenschaften der Markow-Kette finden sich direkt im Übergangsgraph wieder:
- Der Übergangsgraph ist genau dann stark zusammenhängend, wenn die Markow-Kette irreduzibel ist.
- Der Zustand <math> j </math> ist von dem Zustand <math> i </math> aus erreichbar, wenn es einen <math>i-j</math>-Pfad im Übergangsgraph gibt.
- Zwei Zustände i und j kommunizieren genau dann, wenn sowohl ein <math> i-j</math>-Pfad als auch ein <math> j-i</math>-Pfad im Übergangsgraph existiert.
- Ist der Übergangsgraph bipartit, so hat jeder Zustand der Markow-Kette gerade Periode.
- Ist der Übergangsgraph bipartit und zusammenhängend, so hat die Markow-Kette gerade Periode.
Anwendungsbeispiel
Mit Hilfe von Übergangsgraphen lässt sich das Wahl- und Kaufverhalten visualisieren. Dargestellt werden die prozentuale Zahl von Wieder- und Wechselwählern. Bezogen auf die obigen Abbildung würden 60 % der Partei bzw. dem Produkt A treu bleiben und 40 % zu Partei bzw. Produkt E wechseln. Die Zahl der Wiederwähler bei Partei bzw. Produkt E liegt bei 30 %, die Zahl der Wechselwähler bei 70 %. Allerdings wird der Übergangsgraph schon ab vier Parteien bzw. Produkten recht unübersichtlich.
Literatur
- {{#invoke:Vorlage:Literatur|f}}
- Marion Patyna, Klaus Schilling: Lineare Algebra: Mehrstufige Prozesse – Matrizenrechnung, Eins Verlag Köln, 1. Auflage 2011, S. 104–118, ISBN 978-3-427-04440-6.