|
Eine Markow-Kette (engl. Markov chain, auch Markow-Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov-Kette, Markoff-Kette, Markof-Kette) ist ein spezieller stochastischer Prozess. Man unterscheidet eine Markow-Kette in diskreter und in stetiger Zeit. Der Unterschied in der Bezeichnung »Markow-Ketten« (in stetiger/diskreter Zeit) zu Markow-Prozessen besteht darin, dass der Zustandsraum bei letzteren i. A. stetig ist, während bei diskretem Zustandsraum von Markow-Ketten gesprochen wird. Ziel ist es, Wahrscheinlichkeiten für das Eintreten zukünftiger Ereignisse anzugeben. Das Spezielle einer Markow-Kette ist die Eigenschaft, dass durch Kenntnis einer begrenzten Vorgeschichte ebensogute Prognosen über die zukünftige Entwicklung möglich sind wie bei Kenntnis der gesamten Vorgeschichte des Prozesses. Im Falle einer Markow-Kette erster Ordnung heißt das: Die Zukunft des Systems hängt nur von der Gegenwart (dem aktuellen Zustand) und nicht von der Vergangenheit ab.
Die mathematische Formulierung im Falle einer endlichen Zustandsmenge benötigt lediglich den Begriff der diskreten Verteilung sowie der bedingten Wahrscheinlichkeit, während im zeitstetigen Falle die Konzepte der Filtration sowie der bedingten Erwartung benötigt werden.
Markow-Kette mit drei Zuständen und unvollständigen VerbindungenInhaltsverzeichnis [Verbergen]
1 Beispiele
1.1 Stetige Markow-Kette
1.2 Diskrete, endliche Markow-Kette
1.3 Diskrete, unendliche Markow-Kette: Lamplighter
2 Diskrete Zeit und endliche Zustandsmenge
2.1 Definition
2.2 Rekurrent und transient
2.3 Modellierung
2.3.1 Arrival First (AF)
2.3.2 Departure First (DF)
3 Stetige Zeit und diskreter Zustandsraum
4 Diskrete Zeit und allgemeiner Zustandsraum
5 Anwendungen
6 Siehe auch
7 Literatur
8 Weblinks
Beispiele [Bearbeiten]
Markow-Ketten eignen sich sehr gut, um zufällige Zustandsänderungen eines Systems zu modellieren, falls man Grund zu der Annahme hat, dass die Zustandsänderungen nur über einen begrenzten Zeitraum hinweg Einfluss aufeinander haben oder sogar gedächtnislos sind. Ein Beispiel sind Auslastungen von Bediensystemen mit gedächtnislosen Ankunfts- und Bedienzeiten.
Stetige Markow-Kette [Bearbeiten]
Das Paradebeispiel für einen stetigen Markow-Prozess mit den reellen Zahlen als Zustandsraum ist die Brownsche Bewegung.
Diskrete, endliche Markow-Kette [Bearbeiten]
Ein populäres Beispiel für eine zeitdiskrete Markow-Kette mit endlichem Zustandsraum ist die zufällige Irrfahrt (engl. Random Walk) auf einem diskreten Kreis, modelliert durch den Restklassenring . Dies führt zum endlichen Zustandsraum . Hierbei startet man in der Äquivalenzklasse [0] der 0, und bewegt sich in jedem Schritt aus dem aktuellen Zustand [i] jeweils mit Wahrscheinlichkeit 1 / 2 nach [i + 1] oder nach [i − 1] (also anschaulich: einen Schritt nach links oder nach rechts).
Bei einem anderen Beispiel wirft man eine Münze immer wieder und notiert bei jedem Wurf, wie oft bislang 'Kopf' erschienen ist. Die Abfolge der so gebildeten Zahlen bildet ebenfalls einen zeitdiskreten Markow-Prozess, diesmal mit Zustandsraum mit jeweils der Übergangswahrscheinlichkeit 1 / 2 für den Übergang von [i] nach [i + 1] und für das Verbleiben in [i].
Diskrete, unendliche Markow-Kette: Lamplighter [Bearbeiten]
Bei einer zufälligen Irrfahrt auf wird zu jedem Zeitpunkt eine Lampe am jeweiligen Standort ein- oder ausgeschaltet. Der aktuelle Zustand zum Zeitpunkt n des Markow-Prozesses wird durch zwei Variablen beschrieben: den aktuellen Ort Pn des Lamplighters und die Lampenkonfiguration η (z. B. durch eine Abbildung von nach {0,1}). Dann ist (Pn, η) ein Markow-Prozess und sogar (Pn) alleine ist ein Markow-Prozess; für sich alleine ist (η) aber kein Markow-Prozess.
Diskrete Zeit und endliche Zustandsmenge [Bearbeiten]
Definition [Bearbeiten]
Im Fall einer endlichen Zustandsmenge und der diskreten Zeit ist eine Markow-Kette n-ter Ordnung auf S ein stochastischer Prozess mit Werten in S und der Eigenschaft
Die Gleichung bedeutet, dass die Wahrscheinlichkeit für den Zustand zum Zeitpunkt t + 1 nur von den n vorhergehenden Zuständen abhängt. Von besonderem Interesse sind Markow-Ketten erster Ordnung, also Ketten mit
Das heißt, dass das Verhalten des Systems nur vom aktuellen Zustand und nicht von den vorigen Zuständen abhängt. Diese Eigenschaft bezeichnet man als Gedächtnislosigkeit oder auch Markow-Eigenschaft. Üblicherweise meint man mit dem Begriff Markow-Kette lediglich eine Markow-Kette erster Ordnung; dies wird auch im Rest des Artikels so gehandhabt.
Ein Wahrscheinlichkeitsvektor π ist ein Vektor im Rm mit der Eigenschaft, dass für alle i und . Dieser Vektor induziert per P({si}) = πi eine Wahrscheinlichkeitsverteilung auf dem Zustandsraum S. Der Einfachheit halber sagen wir zu π auch Verteilung. (Man beachte, dass – genau wie bei der unten eingeführten Übergangsmatrix – die zugeordnete Verteilung von der Nummerierung des Zustandsraumes abhängt, und daher nur modulo Basisumordnung eindeutig ist.)
Wir betrachten nun im Folgenden eine zeitdiskrete Markow-Kette auf einem endlichen Zustandsraum . Der Wahrscheinlichkeitsvektor μ, der durch
μi = P(X0 = si)
gegeben ist, heißt Anfangsverteilung. Die Übergangswahrscheinlichkeiten (engl. transition probabilities) sind gegeben durch
und werden in einer Übergangsmatrix (auch Transitionsmatrix) zusammengefasst:
[Falls einige bedingte Wahrscheinlichkeiten nicht definiert sind, wird anstelle derselben einfach 0 in die Matrix geschrieben.]
Sind die Übergangswahrscheinlichkeiten unabhängig von dem Zeitpunkt t, gilt also pij = pij(t) für alle t, so spricht man von einer homogenen Markow-Kette.
Für eine homogene Markow-Kette kann die Wahrscheinlichkeit, in n Schritten vom Zustand i in den Zustand j überzugehen, mit Hilfe der n-ten Potenz der Übergangsmatrix berechnet werden:
Hieraus folgt auch leicht, dass die Verteilung von Xn durch μ und M bereits eindeutig bestimmt ist,
.
Eine Verteilung π * heißt stationär (bezüglich der Markow-Kette), falls für alle j gilt
Dies lässt sich so interpretieren: Würfelt man gemäß π * einen Zustand aus, und wendet nun die durch die homogene Markow-Kette beschriebene zufällige Transition auf diesen Zustand an, so erhält man zwar im Allgemeinen ein anderes Ergebnis, aber die Wahrscheinlichkeitsverteilung bleibt dieselbe; der durch π * beschriebene Zufall ist also invariant unter der Transformation der Markow-Kette. Anders gesagt: Würde man anstatt mit μ mit π * als Startverteilung beginnen, so hätte man einen stationären Prozess vorliegen. (Manchmal wird auch, etwas ungenau, von einem stationären Zustand gesprochen.)
Es kann durchaus mehr als eine stationäre Verteilung geben; im degenerierten Extremfall, dass die Transition durch die Einheitsmatrix beschrieben wird (die Markow-Kette also stets gleich dem Anfangswert ist), sind sogar alle Verteilungen stationär. Es gibt aber eine große Klasse von interessanten Markovprozessen, für die es genau eine stationäre Verteilung gibt:
Eine irreduzible, aperiodische homogene Markow-Kette besitzt genau eine stationäre Verteilung π * , vgl. den Satz von Perron-Frobenius; diese kann man auf zwei Arten beschreiben: Ist erstens M die Übergangsmatrix, so konvergiert die Folge der Matrizen Mn gegen die Matrix, welche in jeder Zeile die Verteilung π * einbeschrieben hat. Bezeichnet man zweitens mit μi,j die durchschnittliche Wartezeit, die der Prozess braucht, um von dem Punkt si zu dem Punkt sj zu gelangen, so folgt π * (i) = 1 / μi,i für alle i. Die erste Beziehung lässt sich auch noch anders formulieren: Für die Verteilungen von Xn hat man :, die Verteilungen der Markow-Kette konvergieren also gegen die stationäre Verteilung.
Beispiel: Als ein Beispiel, wie die zweite Beziehung genutzt werden kann, betrachten wir die (symmetrische) zufällige Irrfahrt auf der Menge {0,1,2}; hier ist die Übergangsmatrix gegeben durch
Wir überlegen zunächst, was die durchschnittliche Wartezeit von einem Punkt zu einem von diesem verschiedenen ist. Weil die Matrix invariant unter Permutationen der Elemente des Zustandsraumes ist, ist diese Wartezeit immer die gleiche. Betrachten wir also die Wartezeit von Punkt 0 zu Punkt 1. Mit Wahrscheinlichkeit : ist sie 1, mit Wahrscheinlichkeit : treffen wir im ersten Zug anstatt der '1' die '2'. In diesem Falle müssen wir nun von der '2' zur '0'; die Wartezeit hierfür ist jedoch im Mittel dieselbe wie für den Weg von '1' zur '0'. Wir erhalten also die Beziehung
Diese Gleichung hat die eindeutige Lösung μ1,0 = 2. Nun betrachten wir die durchschnittliche Wartezeit, um von '0' nach '0' zu gelangen. Der Prozess wird in Schritt 1 in jedem Fall auf die '1' oder die '2' wandern; in beiden Fällen beträgt die erwartete Restwartezeit, wie oben errechnet, 2 Schritte, wir erhalten also μ0,0 = 3 und damit . Aus Symmetriegründen gilt dann auch . Hier ist also die Gleichverteilung stationär.
Rekurrent und transient [Bearbeiten]
Definition: Ein Zustand ist genau dann rekurrent, wenn die Wahrscheinlichkeit dafür, dass dieser Zustand unendlich oft eintritt gleich 1 ist, d. h.
Pi(Xn = i tritt unendlich oft ein) = 1.
Andernfalls heißt i transient. Eine Markow-Kette heißt rekurrent (transient), falls jeder Zustand rekurrent (transient) ist.
Modellierung [Bearbeiten]
Oft hat man in Anwendungen eine Modellierung vorliegen, in welcher die Zustandsänderungen der Markow-Kette durch eine Folge von zu zufälligen Zeiten stattfindenden Ereignissen bestimmt wird (man denke an obiges Beispiel von Bediensystemen mit zufälligen Ankunfts- und Bedienzeiten). Hier muss bei der Modellierung entschieden werden, wie das gleichzeitige Auftreten von Ereignissen (Ankunft vs. Erledigung) behandelt wird. Meist entscheidet man sich dafür, künstlich eine Abfolge der gleichzeitigen Ereignisse einzuführen. Üblicherweise unterscheidet man dabei zwischen den Möglichkeiten Arrival First und Departure First.
Arrival First (AF) [Bearbeiten]
Bei dieser Disziplin wird zu Beginn eines Zeitschrittes das Bedienen gestartet. Danach treffen neue Forderungen ein, und erst am Ende eines Zeitschrittes tritt das Bedien-Ende auf.
Der Vorteil dieser Disziplin ist, dass Forderungsankünfte immer vor einem möglichen Bedien-Ende eintreffen und damit die BASTA-Eigenschaft gilt. Mit Hilfe dieser Eigenschaft lassen sich für Ankünfte, die als Bernoulli-Prozess modelliert sind, unter anderem sehr einfach für Bediensysteme wichtige Eigenschaften wie die Verlustwahrscheinlichkeit PV rechnen.
Als Nachteil kann eine Forderung die im Zeitschlitz zt eintrifft frühestens in zt + 1 fertig bedient werden. Dies führt unter Umständen zu einer höheren Anzahl von benötigten Warteplätzen im modellierten System.
Departure First (DF) [Bearbeiten]
Im Fall von Departure First kommen zu Beginn eines Zeitschrittes Forderungen im System an. Darauf folgt der Start von Bedienzeiten und am Ende eines Zeitschrittes das Ende von Bedienzeiten.
Bei diesem Ansatz gilt die BASTA Eigenschaft nicht mehr, was im Allgemeinen zu komplizierteren Berechnungen als im Falle von Arrival First führt. Eine Forderung kann im selben Zeitschritt eintreffen und fertig bedient werden.
Stetige Zeit und diskreter Zustandsraum [Bearbeiten]
Analog lässt sich die Markow-Kette auch für kontinuierliche Zeit und diskreten Zustandsraum bilden. Das heißt, dass sich zu bestimmten Zeitpunkten der Zustand sprunghaft ändert.
Sei ein stochastischer Prozess mit kontinuierlicher Zeit und diskretem Zustandsraum. Dann gilt bei einem homogenen Markow-Prozess
Auch hier lassen sich Übergangsmatrizen bilden: P(t): = [pi,j(t)] für alle t > 0 und P(0): = I (Hierbei steht I wie üblich für die Einheitsmatrix).
Es gilt die Chapman-Kolmogorow-Gleichung und ist entsprechend eine Halbgruppe, die unter gewissen Voraussetzungen einen infinitesimalen Erzeuger, nämlich die Q-Matrix hat.
Diskrete Zeit und allgemeiner Zustandsraum [Bearbeiten]
Markow-Ketten können auch auf allgemeinen messbaren Zustandsräumen definiert werden. Ist der Zustandsraum nicht abzählbar so benötigt man hierzu den stochastischen Kern als Verallgemeinerung zur Übergangsmatrix. Dabei ist eine Markow-Kette durch die Startverteilung auf dem Zustandsraum und den stochastischen Kern (auch Übergangskern oder Markowkern) schon eindeutig bestimmt.
Auf dem Gebiet der allgemeinen Markow-Ketten gibt es noch viele offene Probleme. Gut erforscht sind lediglich Harris-Ketten.
Anwendungen [Bearbeiten]
Markow-Ketten werden in unterschiedlichen Bereichen verwendet.
In den Wirtschaftswissenschaften bei der Warteschlangentheorie. Hier unterstellt man eine homogene Markow-Kette. Dort werden die zu einer Periode wartende Anzahl an Kunden betrachtet. Die Wahrscheinlichkeiten für Ankunft oder Abfertigung eines Kunden sind zeitinvariant (unabhängig von der Periode).
Bioinformatik: Markow-Ketten werden in der Bioinformatik dazu verwendet, Sequenzabschnitte auf bestimmte Eigenschaften zu untersuchen. Hierzu zählt z. B. das Vorhandensein von CpG-Inseln, da in diesen die Übergangswahrscheinlichkeiten zwischen C-G und G-C erhöht sind.
In der Musik zur Komposition algorithmischer Werke, zum Beispiel bei Iannis Xenakis.
Im Qualitätsmanagement zur Bestimmung der Zuverlässigkeit eines Systems und dessen Teilkomponenten
Siehe auch [Bearbeiten]
Endlicher Automat
Hidden Markov Model
Irreduzible Markow-Kette
Markow-Filter
Semi-Markow-Prozess
Geburts- und Todesprozess
Literatur [Bearbeiten]
Philipp von Hilgers, Wladimir Velminski (Hg.): Andrej A. Markov. Berechenbare Künste, Zürich/Berlin: diaphanes, 2007. ISBN 978-3-935300-69-8
Classical Text in Translation: Andrei A. Markov, An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains, trans. David Link. Science in Context 19.4 (2006): 591-600. Online: http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=637500
Pierre Brémaud: Markov Chains. Springer Verlag, 1999, ISBN 0-387-98509-3
Ehrhard Behrends: Introduction to Markov Chains. Vieweg, 2000, ISBN 3-528-06986-4
Olle Häggström: Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002
Weblinks [Bearbeiten]
Markov und die Folgen - Projekt an der Humboldt-Universität zu Berlin
mathematik.uni-ulm.de – Skript Markov-Ketten
aiplayground.org – Markow-Text-Generator: Prinzip und Algorithmus
Markow geometrisch - ein anschaulicher Ansatz (ein Programm für MuPad 4.0)
Von „http://de.wikipedia.org/wiki/Markow-Kette“
Kategorie: Stochastischer Prozess
|
