Markow-Kette

Markow-Kette mit drei Zuständen und unvollständigen Verbindungen

Eine Markow-Kette (englisch Markov chain; auch Markow-Prozess, nach Andrei Andrejewitsch Markow; andere Schreibweisen Markov-Kette, Markoff-Kette, Markof-Kette) ist ein stochastischer Prozess. Ziel bei der Anwendung von Markow-Ketten ist es, Wahrscheinlichkeiten für das Eintreten zukünftiger Ereignisse anzugeben. Eine Markow-Kette ist darüber definiert, dass durch Kenntnis einer nur begrenzten Vorgeschichte ebenso gute Prognosen über die zukünftige Entwicklung möglich sind wie bei Kenntnis der gesamten Vorgeschichte des Prozesses.

Man unterscheidet Markow-Ketten unterschiedlicher Ordnung. Im Falle einer Markow-Kette erster Ordnung heißt das: Der zukünftige Zustand des Prozesses ist nur durch den aktuellen Zustand bedingt und wird nicht durch vergangene Zustände beeinflusst. 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.

Die Begriffe Markow-Kette und Markow-Prozess werden im Allgemeinen synonym verwendet. Zum Teil sind aber zur Abgrenzung mit Markow-Ketten Prozesse in diskreter Zeit (diskreter Zustandsraum) gemeint und mit Markow-Prozessen Prozesse in stetiger Zeit (stetiger Zustandsraum).

Einführende Beispiele

Numerisches Beispiel einer einfachen Markow-Kette mit den zwei Zuständen E und A. Jede Zahl steht für die Wahrscheinlichkeit, dass der Markov-Prozess von einem Zustand in einen anderen wechselt, wobei die Richtung durch den Pfeil angegeben ist. Befindet sich der Markov-Prozess beispielsweise im Zustand A, so ist die Wahrscheinlichkeit, dass er in den Zustand E wechselt, 0.4, während die Wahrscheinlichkeit, dass er im Zustand A bleibt, 0.6 beträgt. (Hinweis: Als Dezimaltrennzeichen wurde der Punkt vom Bild im Text übernommen.)

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.

Diskrete, endliche Markow-Kette

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 $\mathbb {Z} /n\mathbb {Z}$. Dies führt zum endlichen Zustandsraum $S=\left\{0,1,2,\dots ,(n-1)\right\}$. 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).

Eine (endliche) zufällige Irrfahrt mit zwei absorbierenden Zuständen (ganz links und ganz rechts). Die Zustände „-1“, „0“ und „1“ haben jeweils die gleiche Übergangswahrscheinlichkeit (0,5) zu den Zuständen links und rechts von ihnen.

Diskrete, unendliche Markow-Kette

Als Beispiel für einen abzählbar unendlichen Zustandsraum 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 eine (zeitdiskrete) Markow-Kette, diesmal mit Zustandsraum $S=\{0,1,2,\dots \}$ mit jeweils der Übergangswahrscheinlichkeit $1/2$ für den Übergang von $[i]$ nach $[i+1]$ und für das Verbleiben in $[i]$.

Ein weiteres Beispiel für eine Markow-Kette mit unendlichem Zustandsraum ist der Galton-Watson-Prozess, der oftmals zur Modellierung von Populationen genutzt wird.

Diskrete Zeit und höchstens abzählbar unendliche Zustandsmenge

Definition

Gegeben sei eine Familie von Zufallsvariablen $Y=(X_{t})_{t\in \mathbb {N} }$, wobei alle $X_{t}$ nur Werte aus dem höchstens abzählbaren Zustandsraum $S=\{s_{1},s_{2},s_{3},\dots \}$ annehmen. Dann heißt $Y$ eine (diskrete) Markow-Kette genau dann, wenn

${\begin{aligned}&\ P(X_{t+1}=s_{j_{t+1}}\mid X_{t}=s_{j_{t}},X_{t-1}=s_{j_{t-1}},\dots ,X_{0}=s_{j_{0}})\\=&\ P(X_{t+1}=s_{j_{t+1}}\mid X_{t}=s_{j_{t}}).\end{aligned}}$

gilt. Die Übergangswahrscheinlichkeiten hängen also nur von dem aktuellen Zustand ab und nicht von der gesamten Vergangenheit. Dies bezeichnet man als Markow-Eigenschaft oder auch als Gedächtnislosigkeit. Seien

$p_{ij}(t):=P(X_{t+1}=s_{j}\mid X_{t}=s_{i}),\quad i,j=1,\dots ,m$

die Übergangswahrscheinlichkeiten. Diese lassen sich dann in eine quadratische Übergangsmatrix zusammenfassen:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \mathbf {M} (t)=(p_{ij}(t))_{s_{i},s_{j}\in S}}

Sind die Übergangswahrscheinlichkeiten unabhängig vom Zeitpunkt $t$, gilt also Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle p_{ij}(t)=p_{ij}} für alle $t$, so heißt die Markow-Kette homogen oder Kette mit stationären Übergangswahrscheinlichkeiten. Bei Homogenität einer Kette definiert man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{ij}^n=P(X_{n}=s_j \mid X_0=s_i) } als die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Schritt-Übergangswahrscheinlichkeit.

Markow-Kette n-ter Ordnung

Gelegentlich werden auch Markow-Ketten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -ter Ordnung untersucht. Bei diesen hängt der zukünftige Zustand von den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} vorherigen Zuständen ab:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} &\ P(X_{t+1}=s_{j_{t+1}}\mid X_t=s_{j_t}, X_{t-1}=s_{j_{t-1}},\dots,X_0=s_{j_0})\\ =&\ P(X_{t+1}=s_{j_{t+1}}\mid X_t=s_{j_t},\dots,X_{t-n+1}=s_{j_{t-n+1}}). \end{align}}

In diesem Sinn sind die oben betrachteten Markow-Ketten Ketten erster Ordnung. Ketten höherer Ordnung werden hier aber nicht weiter betrachtet.

Grundlegende Eigenschaften

• Die Verteilung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_0 } wird manchmal auch als Startverteilung oder Anfangsverteilung bezeichnet. Bei Vorgabe einer Startverteilung sind alle weiteren Verteilungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_t } eindeutig bestimmt. Daher hat sich teilweise die verkürzte Notation eingebürgert, nur die Startverteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha } und den Zeitschritt von Interesse anzugeben:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P^\alpha(X_t=i):=P(X_t=i|X_0 \ \text{ hat Verteilung } \ \alpha) }

Startet man in einem eindeutigen Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j } , so wird meist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P^j(X_t=i) } geschrieben.

• Bei einem endlichen Zustandsraum lassen sich Markow-Ketten mittels der Übergangsmatrix und von Wahrscheinlichkeitsvektoren beschreiben. Wählt man einen stochastischen Startvektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_0 } (als Zeilenvektor) als Startverteilung, so ergibt sich die Verteilung zum Zeitpunkt 1 durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_1=v_0M } . Damit folgt induktiv Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_n=v_0M^n } . Dabei ist dann genau der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -te Eintrag von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_n } die Wahrscheinlichkeit zum Zeitpunkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} im Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} zu sein, wenn mit der Startverteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_0 } gestartet wurde.
• Gemäß der obigen Ausführung lassen sich im Falle der Homogenität und der Endlichkeit des Zustandsraumes leicht die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Schritt-Übergangswahrscheinlichkeiten berechnen. Diese sind dann genau

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{ij}^n=\left[ M^n\right]_{i,j} } ,

also der Eintrag, der in der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -ten Zeile und der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} -ten Spalte der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -ten Potenz der Übergangsmatrix steht.

• Allgemein gilt die Chapman-Kolmogorow-Gleichung. Im Falle eines endlichen Zustandsraumes ist sie genau das komponentenweise Ausschreiben der Matrixmultiplikation.
• Markow-Ketten sind diskrete dynamische Systeme. Der Zeitraum ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{N} } , der Index der Zufallsvariable. Den Zustandsraum im Sinne des dynamischen Systems bilden dann alle Verteilungen auf dem Zustandsraum im Sinne der Markow-Kette. Die Operation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Phi } ordnet dann der Verteilung im Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} -ten Zeitschritt die Verteilung im Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (t+1)} -ten Zeitschritt zu. Im Falle eines endlichen Zustandsraumes der Markow-Kette ist dies dann genau die iterierte Anwendung der Übergangsmatrix wie oben beschrieben. Einige Begriffe aus der Theorie der dynamischen Systeme haben ein Pendant in der Theorie der Markow-Ketten wie z. B. kritische Punkte und stationäre Verteilungen.
• Homogene Markow-Ketten mit einer stationären Verteilung als Startverteilung sind stark stationäre stochastische Prozesse. Somit sind zeitdiskrete Markow-Ketten mit abzählbarem Zustandsraum maßerhaltende dynamische Systeme, wenn sie in ihrer invarianten Verteilung starten. Sind sie zusätzlich positiv rekurrent sowie irreduzibel, so sind sie sogar ergodische stochastische Prozesse und erlauben die Anwendung von Aussagen der Ergodentheorie wie zum Beispiel des individuellen Ergodensatzes.
• Die oben definierte Übergangsmatrix ist unendlichdimensional, wenn der Zustandsraum abzählbar unendlich ist. Nur im Falle der Endlichkeit des Zustandsraumes handelt es sich um eine Matrix im Sinne der Linearen Algebra.

Beispiele

Endlicher Zustandsraum

Übergangsgraph für die beschriebene Markow-Kette

Wir versuchen, mithilfe einer Markow-Kette eine einfache Wettervorhersage zu bilden. Dazu kodieren wir 1 = „die Sonne scheint“, 2 = „es ist bewölkt“ und 3 = „es regnet“. Als Zeitschritt wählen wir einen Tag. Aus Erfahrung wissen wir, dass wenn heute die Sonne scheint, die Wahrscheinlichkeit, dass es morgen regnet, ungefähr 80 % ist und die Wahrscheinlichkeit, dass es bewölkt ist, ca. 20 % beträgt. Außerdem treffen wir die Annahme, dass sich diese Wahrscheinlichkeiten nicht ändern, die Markow-Kette also homogen ist. Somit wissen wir nun

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(X_{t+1}=i|X_t=1)= \begin{cases} 0 & \text{ falls }\quad i=1 \\ 0{,}2 & \text{ falls }\quad i=2, \\ 0{,}8 & \text{ falls }\quad i=3 \end{cases} }

Ist es aber bewölkt, so regnet es mit Wahrscheinlichkeit 0,5 am folgenden Tag und mit Wahrscheinlichkeit von 0,5 scheint die Sonne. Es gilt also

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(X_{t+1}=i|X_t=2)= \begin{cases} 0{,}5 & \text{ falls }\quad i=1 \\ 0 & \text{ falls }\quad i=2, \\ 0{,}5 & \text{ falls }\quad i=3 \end{cases} }

Regnet es heute, so scheint danach nur mit Wahrscheinlichkeit von 0,1 die Sonne und mit Wahrscheinlichkeit von 0,9 ist es bewölkt. Damit folgt für die Übergangswahrscheinlichkeiten

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(X_{t+1}=i|X_t=3)= \begin{cases} 0{,}1 & \text{ falls }\quad i=1 \\ 0{,}9 & \text{ falls }\quad i=2, \\ 0 & \text{ falls }\quad i=3 \end{cases} }

Damit ist die Markow-Kette vollständig beschrieben. Anschaulich lassen sich solche Markow-Ketten gut durch Übergangsgraphen darstellen, wie oben abgebildet. Ordnet man nun die Übergangswahrscheinlichkeiten zu einer Übergangsmatrix an, so erhält man

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = \begin{bmatrix} 0 & 0{,}2 & 0{,}8 \\ 0 {,}5 & 0 & 0{,}5 \\ 0{,}1 & 0{,}9 & 0 \end{bmatrix}}

Wir wollen nun wissen, wie sich das Wetter entwickeln wird, wenn heute die Sonne scheint. Dazu geben wir die Anfangsverteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_0 } vor in Form des stochastischen Startvektors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_0=(1;0;0) } . Wir starten also fast sicher im Zustand 1. Multiplikation von rechts mit der Übergangsmatrix liefert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_1=v_0M=(0;0{,}2;0{,}8) } . Mit achtzigprozentiger Wahrscheinlichkeit regnet es also. Am dritten Tag gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_3=v_0M^3\approx (0{,}3700; 0{,}1260; 0{,}5040) } . Somit ist die Regenwahrscheinlichkeit am dritten Tag knapp über 50 % und die Sonnenwahrscheinlichkeit knapp unter 40 %. Somit lässt sich für jedes vorgegebene Wetter am Starttag die Regen- und Sonnenwahrscheinlichkeit an einem beliebigen Tag angeben. Auch Fragestellungen wie: „Heute scheint die Sonne. Wie groß ist die Wahrscheinlichkeit, dass es vor drei Tagen geregnet hat?“ lassen sich mit dem Satz von Bayes beantworten.

Abzählbar unendlicher Zustandsraum

Definieren wir nun eine Markow-Kette auf dem Zustandsraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{Z} } und mit Übergangswahrscheinlichkeiten

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(X_{t+1}=i|X_t=j)= \begin{cases} p & \text{ falls }\quad i=j+1 \\ q & \text{ falls }\quad i=j-1, \\ 0 & \text{sonst} \end{cases} }

wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p+q=1 , p,q \geq 0 } gilt. Dies lässt sich so veranschaulichen: Startet man an einem beliebigen Punkt, so bewegt man sich entweder mit einer Wahrscheinlichkeit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p } nach „rechts“, sprich begibt sich zu der nächsthöheren Zahl. Mit Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q } wandert man nach „links“ zu einer niedrigeren Zahl. Entsprechend diesem Vorgehen irrt man dann über den Zahlenstrahl. Daher wird diese Markow-Kette auch Irrfahrt auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{Z} } genannt. Gelegentlich wird für solche Markow-Ketten auch der Begriff des Random Walk verwendet. Starten wir im Zustand 0, so ist mit den obigen Übergangswahrscheinlichkeiten

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P^0(X_1=i)= \begin{cases} p & \text{ falls }\quad i=1 \\ q & \text{ falls }\quad i=-1, \\ 0 & \text{ sonst} \end{cases} }

Daraus folgt dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P^0(X_2=-2)=q^2, P^0(X_2=0)=2pq, P^0(X_2=2)=p^2 } . Hier zeigt sich ein gewisser Zusammenhang zur Binomialverteilung. Außerdem gilt aber auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P^0(X_2=-1)=P^0(X_2=1)=0 } . Gewisse Zustände können also nur zu bestimmten Zeiten besucht werden, eine Eigenschaft, die Periodizität genannt wird.

Ist allgemeiner Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (Z_n)_{n \in \N}} eine Folge unabhängiger und identisch verteilter Zufallsvariablen mit Werten in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z} , dann ist durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_t = \sum_{n=1}^t Z_n}

eine Markow-Kette Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (X_t)_{t \in \N}} mit Übergangswahrscheinlichkeiten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{ij} = P(Z_1 = j-i)} gegeben.

Klassische Beispiele

Einige der bekanntesten Markow-Ketten sind

• Die Irrfahrt auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{Z}^D } sowie Verallgemeinerungen auf Graphen.
• Der Galton-Watson-Prozess, welcher die Fortpflanzung einer sich eingeschlechtlich fortpflanzenden Spezies modelliert
• Das Ehrenfest-Modell zur Modellierung der Diffusion von Molekülen durch Membrane.

Attribute

Markow-Ketten können gewisse Attribute zukommen, welche insbesondere das Langzeitverhalten beeinflussen. Dazu gehören beispielsweise die folgenden:

Irreduzibilität

→ Hauptartikel: Irreduzible Markow-Kette

Irreduzibilität ist wichtig für die Konvergenz gegen einen stationären Zustand. Vereinfacht gesagt ist eine Markow-Kette irreduzibel, wenn für alle Zustände Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j } gilt, dass die Wahrscheinlichkeit, in endlicher Zeit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j } zu kommen, echt positiv ist. Gilt dies für fixierte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j } , so sagt man auch, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j } miteinander kommunizieren.

Periodizität

→ Hauptartikel: Periodische Markow-Kette

Periodische Markow-Ketten erhalten trotz aller Zufälligkeit des Systems gewisse deterministische Strukturen. Ist eine Markow-Kette periodisch mit Periode Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d } , so kann sie höchstens alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d } Zeitschritte wieder zu ihrem Startpunkt zurückkehren (dies ist aber nicht zwingend).

Rekurrenz und Transienz

→ Hauptartikel: Rekurrente Markow-Kette

Die Rekurrenz und die Transienz beschreiben das Langzeitverhalten einer Markow-Kette. Wird ein Zustand fast sicher unendlich oft besucht, so heißt er rekurrent, ansonsten transient. Sind alle Zustände rekurrent (transient), so heißt die Markow-Kette rekurrent (transient). Wichtiges Hilfsmittel zur Bestimmung von Rekurrenz ist die Green-Funktion.

Absorbierende Zustände

→ Hauptartikel: Absorbierender Zustand

Absorbierende Zustände sind Zustände, welche nach dem Betreten nicht wieder verlassen werden können. Hier interessiert man sich insbesondere für die Absorptionswahrscheinlichkeit, also die Wahrscheinlichkeit, einen solchen Zustand zu betreten.

Stationäre Verteilungen

→ Hauptartikel: Stationäre Verteilung

In der Anwendung sind oftmals besonders stationäre Verteilungen interessant. Gibt man diese Verteilungen als Startverteilung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_0 } vor, so sind alle darauf folgenden Verteilungen der Zustände Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_n} für beliebiges Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n } gleich der Startverteilung. Interessant ist hier die Frage, wann solche Verteilungen existieren und wann eine beliebige Verteilung gegen solch eine stationäre Verteilung konvergiert.

Reversibilität

→ Hauptartikel: Reversible Markow-Kette

Bei reversiblen Markow-Ketten lässt sich nicht unterscheiden, ob sie in der Zeit vorwärts oder rückwärts laufen, sie sind also invariant unter Zeitumkehr. Insbesondere folgt aus Reversibilität die Existenz eines stationären Zustandes.

Modellierung

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)

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.

Datei:Mk af.png

Der Vorteil dieser Disziplin ist, dass Forderungsankünfte immer vor einem möglichen Bedien-Ende eintreffen und damit die PASTA-Eigenschaft (Poisson Arrivals See Time Averages) 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_V} berechnen.

Als Nachteil kann eine Forderung, die im Zeitschlitz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_t} eintrifft, frühestens in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_{t+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)

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.

Datei:Mk df.png

Bei diesem Ansatz gilt die PASTA 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.

Simulation

Diskrete Markow-Ketten mit endlichem Zustandsraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S=\{1, \dots, m\} } können leicht simuliert werden, wenn Standardzufallszahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_t } verfügbar sind. Dazu definiert man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r_i(j)= \begin{cases} 0 & \text{falls }\quad j=0 \\ \sum_{l=1}^j p_{il} & \text{sonst} \end{cases} }

für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i,j \in S } . Ist nun Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_t=i } , dann setze Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_{t+1}=j } genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_t \in [r_i(j-1),r_i(j)] } ist. Dieses Verfahren ist insbesondere dann effizient, wenn wenige Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{ij} } ungleich null sind. Es entspricht der Inversionsmethode mit der Wahrscheinlichkeitsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i(\{j\}):=p_{ij} } . Die Möglichkeit, auch große Markow-Ketten zu simulieren, macht man sich beim MCMC-Verfahren zunutze, um Verteilungen zu simulieren, die nicht durch klassische Verfahren simuliert werden können.

Stetige Zeit und diskreter Zustandsraum

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (X(t))_{t \ge 0}} ein stochastischer Prozess mit kontinuierlicher Zeit und diskretem Zustandsraum. Dann gilt bei einem homogenen Markow-Prozess

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall n \in\N,\ 0 < t_1 < \dotsb < t_n,\ t > 0,\ i_1, \ldots, i_n, j \in S:}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} P(X(t_n + t) = j \mid X(t_n) = i_n, \ldots, X(t_1) = i_1) &= P(X(t_n + t) = j \mid X(t_n) = i_n)\\ &= P(X(t) = j \mid X(0) = i_n)\\ &=: p_{i_n,j}(t) \end{align}}

Auch hier lassen sich Übergangsmatrizen bilden: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(t) := [ p_{i,j} (t) ]} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t > 0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(0) := I} (Hierbei steht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} wie üblich für die Einheitsmatrix).

Es gilt die Chapman-Kolmogorow-Gleichung und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P(t))_{t\geq0}} ist entsprechend eine Halbgruppe, die unter gewissen Voraussetzungen einen infinitesimalen Erzeuger, nämlich die Q-Matrix hat.

Beispiel hierfür ist der homogene Poisson-Prozess, der die Q-Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{ij}=\lambda \mathbf{1}_{\{j=i+1\}} - \lambda \mathbf{1}_{\{j=i\}} } besitzt, oder allgemeiner jeder Geburts- und Todesprozess.

Diskrete Zeit und allgemeiner Zustandsraum

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. Ein klassisches Beispiel für einen Markow-Prozess in stetiger Zeit und stetigem Zustandsraum ist der Wiener-Prozess, die mathematische Modellierung der brownschen Bewegung.

Allgemeine Formulierung

Inhomogene Markow-Prozesse lassen sich mithilfe der elementaren Markow-Eigenschaft definieren, homogene Markow-Prozesse mittels der schwachen Markow-Eigenschaft für Prozesse mit stetiger Zeit und mit Werten in beliebigen Räumen definieren. Meist beschränkt man sich hierbei aber aus Gründen der Handhabbarkeit auf polnische Räume. Eine Verschärfung der schwachen Markow-Eigenschaft ist die starke Markow-Eigenschaft.

Definition

Gegeben sei ein stochastischer Prozess Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X=(X_t)_{t \in T} } , für den gilt:

• Für die Indexmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T } gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T \subset [0,\infty) } sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 \in T } und sie ist abgeschlossen bezüglich Addition.
• Jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_t } nimmt Werte in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (E, \mathcal B(E)) } an, demnach nimmt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X } Werte in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (E^{\times T}, \mathcal B (E)^{ \otimes T}) } an. Dabei ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal B (E) } die Borelsche σ-Algebra.

Der Prozess heißt dann ein Markow-Prozess mit Verteilungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P_x)_{x \in E} } auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\Omega, \mathcal A) } , wenn gilt:

1. Für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in E } ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X } ein stochastischer Prozess auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\Omega, \mathcal A, P_x) } mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_x(X_0=x)=1 }
2. Es existiert ein Markow-Kern Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \kappa } von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (E, \mathcal B(E)) } nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (E^{ \times T}, \mathcal B (E)^{\otimes T}) } mit

   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \kappa(x, B)= P_x(X \in B) } für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B \in \mathcal B (E)^{ \otimes T} } .

3. Es gilt die schwache Markow-Eigenschaft.

Anwendungen

Markow-Ketten werden in unterschiedlichen Bereichen verwendet.

• In den Wirtschaftswissenschaften bei der Warteschlangentheorie. Hier unterstellt man eine homogene Markow-Kette. Dort wird 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 Gesundheitsökonomie zur probabilistischen Modellierung im Zuge einer Kosten-Nutzen-Analyse von Gesundheitstechnologien wie zum Beispiel Medikamenten.
• In der Versicherungsmathematik werden diskrete Markow-Ketten verwendet zur Einrechnung biometrischer Risiken (Invalidisierungswahrscheinlichkeiten, Sterbewahrscheinlichkeiten, …).
• Die Finanzmathematik verwendet auf dem Wiener-Prozess basierende Markow-Prozesse zur Modellierung von Aktienkurs- und Zinsentwicklungen.
• 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
• In der Physik zur Modellierung des Zerfalls eines Compoundkerns und zur Herleitung von Master-Gleichungen in der Markow-Näherung
• Im automatisierten Onlinemarketing zur Generierung von Texten, welche von automatischen Spamfiltern nur schwer von durch Menschen verfasste Texte zu unterscheiden sind.
• Ebenso zum Erkennen von Spam-Mails mittels eines Markow-Spamfilters
• Bestimmte Brettspiele wie Monopoly und das Leiterspiel lassen sich als Markow-Kette auffassen.
• Der PageRank einer Homepage lässt sich als Markow-Kette interpretieren. Insbesondere ist diese Markow-Kette durch die stochastische Google-Matrix beschrieben.
• Zur Simulation von Verteilungen, die ansonsten nur schwer zugänglich sind, mittels der Markow chain Monte Carlo-Methode

Siehe auch

• Markov Random Field
• Endlicher Automat
• Hidden Markov Model
• Semi-Markow-Prozess

Literatur

• Philipp von Hilgers, Wladimir Velminski (Hrsg.): Andrej A. Markov. Berechenbare Künste. diaphanes, Zürich/ Berlin 2007, ISBN 978-3-935300-69-8.
• Andrei A. Markov: An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains. trans. Classical Text in Translation. In: Science in Context. 19.4, 2006, S. 591–600.
• 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.
• Daniel W. Stroock: An introduction to Markov processes. (= Graduate Texts in Mathematics. 230). 2. Auflage. Springer/ Heidelberg 2014, ISBN 978-3-642-40522-8.

Weblinks

• mathematik.uni-ulm.de – Skript Markov-Ketten