Inhaltsverzeichnis

0. Vorwort
1. Wichtige Definitionen
1.1. Stochastischer Prozeß
1.2. Markow-Ketten
2. Anwendung anhand eines Beispiels
2.1. Einführung in das Beispiel
2.2. Bestimmung des Zustandraums
2.3. Übergangswahrscheinlichkeit
2.4. Darstellungsmöglichkeiten
2.4.1. Baumdiagramm
2.4.2. Kreisdiagramm
2.4.3. Tabelle
2.4.4. Übergangsmatrix
2.5. Mehrstufige Übergänge
2.6. Anfangsverteilung
2.7. Spätere Wahrscheinlichkeitsverteilung
2.8. Langfristiges Verhalten
2.8.1. Grenzmatrix
2.8.2. Grenzverteilung
2.8.3. Stationäre Verteilung
3. Klassifikationen
3.1. Besondere Zustände
3.1.1. Absorbierende Zustände
3.1.2. Innere Zustände
3.1.3. Transiente Zustände
3.1.4. Rekurrente Zustände
3.1.5. Periodische Zustände
3.1.6. Aperiodische Zustände
3.2. Wichtige Formen von Markow-Ketten
3.2.1. Endliche Markow-Kette
3.2.2. Homogene Markow-Kette
3.2.3. Irreduzible Markow-Kette
3.2.4. Absorbierende Markow-Kette
3.2.5. Reguläre Markow-Kette
4. Beispiel für eine absorbierende Markow-Kette
4.1. Vorstellung des Beispiels
4.2. Definition der Zustände
4.3. Fundamentalmatrix der absorbierenden Markow-Kette
5. Nachwort
Literaturverzeichnis
Anhang
Gaußverfahren zur Bildung der inversen Matrix

Anmerkung vom 13. März 2003

Download als PDF

0. Vorwort

In der Wahrscheinlichkeitsrechnung versucht man oft mittels stochastischer Modelle Vorhersagen über zukünftige Entwicklungen zu treffen. Dabei kann es vorkommen, daß sich der stochastische Prozeß zyklisch verhält. Eine vergleichsweise einfache Beschreibung solcher Zusammenhänge sind dem russischen Mathematiker Andrei Andrejewitsch Markow (1856 – 1922) gelungen. Mit diesen sogenannten Markow-Ketten können bestimmte stochastische Prozesse ohne größeren Aufwand über einen längeren Zeitraum betrachtet werden, was sie für Berechnungen über zukünftige Entwicklungen sehr interessant macht.

1. Wichtige Definitionen

1.1. Stochastischer Prozeß

Da es sich bei einer Markow-Kette um einen stochastischen Prozeß handelt, muß zuerst dieser Begriff geklärt werden. Ein stochastischer Prozeß bezeichnet eine Folge von Zufallsexperimenten, die durch eine Funktion X(t) mit t Î T beschrieben werden kann. T ist dabei die Menge aller möglichen Zeitpunkte des Systems und wird Parameterraum genannt. Wenn T nur ganzzahlige Elemente enthält, ist das System diskret in Zeit; enthält T reelle Elemente, nennt man das System kontinuierlich in Zeit.
Neben dieser Menge der Zeitpunkte gibt es den Zustandsraum, der meistens mit M oder auch mit Z bezeichnet werden kann. Der Zustandsraum ist die Menge aller Zustände, die das System annehmen kann. Diese Zustände müssen immer unabhängig sein, weil sich das System immer in genau einem Zustand befindet.
Wenn der Zustandsraum eine abzählbare Menge ist, wird das System als diskret in Raum, sonst als kontinuierlich in Raum bezeichnet.

Ein stochastischer Prozeß kann durch eine Funktion X(t), t Î T, beschrieben werden:

X(t)	Zufallsvariable
X(t0)	Wert der Zufallsvariable zum Zeitpunkt t0
T	Parameterraum
M = {X(t) | t ÎT}	Zustandsraum

Man spricht auch von einer stochastischen Kette, wenn das System diskret in Zeit und Raum ist.

1.2. Markow-Ketten

Markow-Ketten sind besondere stochastische Prozesse. Man betrachtet sie nur mit diskreten Zeitparametern und meistens ist auch der Zustandsraum diskret.
Eine Besonderheit der Markow-Ketten ist, daß die Eigenschaften ihres Systems zu einem beliebigen Zeitpunkt t_m nur durch die Werte in den Zeitpunkten t_m und t_m-1 festgelegt und von den früheren Werten unabhängig sind. Der Zusammenhang, daß der zukünftige Zustand nur von dem gegenwärtigen Zustand und nicht von früheren Zuständen abhängt, nennt man Markow-Eigenschaft.

Eine Folge X_n mit n = 0, 1, …, N von diskreten Zufallsvariablen mit dem Zustandsraum M = {e₀, e₁, …,e_N} heißt Markow-Kette, wenn die folgende Bedingung für die Markow-Eigenschaft erfüllt ist:

Eine Markow-Kette ist bestimmt über die Anfangsverteilung, die Übergangswahrscheinlichkeiten und durch ihren Zustandsraum.

Diese Begriffe werden im folgenden anhand von Beispielen erklärt.

2. Anwendung anhand eines Beispiels

2.1. Einführung in das Beispiel

Ein Käfer kriecht durch das in Fig. 1 dargestellte Wegenetz. Er entscheidet sich an jeder Weggabelung zufällig für einen Weg in Pfeilrichtung, stehen bleiben darf er nicht.

Fig. 1

2.2. Bestimmung des Zustandsraums

Man kann dieses Beispiel wie die meisten Markow-Ketten überhaupt auf unterschiedliche Art und Weise darstellen. Zuerst muß aber immer die Frage geklärt werden, welche Zustände es gibt, also welche Elemente der Zustandsraum M enthält. In Fig. 1 kann man vier Knotenpunkte erkennen, die man dann als Zustände definiert, daher ist

Man muß immer dafür sorgen, daß die Zustände unabhängig sind. Dies ist gewährleistet, da der Käfer sich immer nur an einem Punkt befinden kann.
Die Reihenfolge der Zustände kann man selbst festlegen: e₁ sei der linke, e₂ der untere, e₃ der obere und e₄ der rechte Punkt.

2.3. Übergangswahrscheinlichkeit

Als nächstes müssen nun die Übergangswahrscheinlichkeiten gesucht werden. Die Übergangswahrscheinlichkeit

ist die Wahrscheinlichkeit für den Übergang aus dem Zustand e_i in den Zustand e_k, also eine bedingte Wahrscheinlichkeit, weil das System sich zunächst im Zustand e_i befinden muß. Ist ein Übergang von e_i nach e_k nicht möglich, ist p_ik = 0.
In diesem Beispiel können die Übergangswahrscheinlichkeiten leicht bestimmt werden, denn wenn der Käfer sich zufällig entscheidet, sind sie der Kehrwert der möglichen Wege.
Daraus ergibt sich:  

(2.3)

p11 = 0 p12 =  p13 =  p14 = 0

p21 =  p22 = 0 p23 =  p24 =  usw.

Die Summe der Übergangswahrscheinlichkeiten von einem Zustand aus, muß genau eins ergeben, weil irgendein Zustand eintreten muß.
Es gilt also für jedes i:  

(2.4)

2.4. Darstellungsmöglichkeiten

Der Zustandsraum und die Übergangswahrscheinlichkeiten lassen sich auf unterschiedliche Art und Weise übersichtlich darstellen.

2.4.1. Baumdiagramm

Das Baumdiagramm ist keine ideale Darstellungsweise einer Markow-Kette, weil es in den meisten Fällen nicht deutlich macht, daß sich das System aufgrund der Markow-Eigenschaft unabhängig von den vorangegangenen Zuständen verhält und unter Umständen wieder von vorne beginnt. Es ist jedoch bei einigen Beweisen nützlich.

Abbildung 1

Abbildung 1 zeigt das Baumdiagramm für das Beispiel zu einem beliebigen Zeitpunkt, macht aber nicht deutlich, daß in einem bestimmten Zustand immer dieselben Wahrscheinlichkeiten vorliegen.

2.4.2. Kreisdiagramm

Zweckmäßiger ist die Darstellung in Form eines Kreisdiagramms, das auch als Zustandsgraph bezeichnet wird.
Die Zustände werden in kleinen Kreisen mit ihren Namen dargestellt und durch Pfeile, an denen die Übergangswahrscheinlichkeit steht, werden die Übergänge deutlich gemacht. Die Summe der Übergangswahrscheinlichkeiten an den von einem Zustand e_j ausgehenden Pfeilen muß nach der Überlegung in (2.4) genau eins sein.

Abbildung 2

Abbildung 2 zeigt das Kreisdiagramm für das Beispiel. Es gleicht sehr dem Wegenetz, enthält aber Zustandsnamen und Übergangswahrscheinlichkeiten und eignet sich daher gut zur Darstellung von Markow-Ketten.

2.4.3. Tabelle

Übersichtlich lassen sich die Übergangswahrscheinlichkeiten auch in einer Tabelle anordnen.
Tabelle mit den Wahrscheinlichkeiten aus (2.3):

	e1	e2	e3	e4
e1	0			0
e2		0
e3		0	0
e4	0

Die Tabelle gibt die Wahrscheinlichkeiten für den Übergang von dem Zustand, der am Anfang der Zeile steht, zu dem Zustand, der am Kopf der Spalte steht, an.

2.4.4. Übergangsmatrix

Von der Darstellung der Übergangswahrscheinlichkeit in Tabellen findet man leicht zur Schreibweise in Matrizen, denn die Darstellung in der Übergangsmatrix ist nicht nur sehr übersichtlich, sondern sie vereinfacht auch die Rechnungen, wie später noch deutlich werden wird.
Man bildet die Übergangsmatrix P, indem man die Elemente aus der Tabelle in eine quadratische Matrix der Form N ´  N überträgt. Weil die Elemente der Tabelle die Übergangswahrscheinlichkeiten p_ik sind und nach Zuständen sortiert angeordnet sind, befindet sich in der Matrix nun in der i-ten Zeile und k-ten Spalte die Wahrscheinlichkeit p_ik für einen Übergang vom Zustand e_i in den Zustand e_k.
Die Übergangsmatrix P ist stochastisch, d.h. die Summe der Elemente einer Zeile sind nach der Überlegung in (2.4) genau eins und die Elemente selbst sind mindestens Null und höchstens eins.

Eine Matrix heißt stochastisch, wenn folgende Bedingungen erfüllt sind:

Man nennt eine Matrix doppelt-stochastisch, wenn auch die Summe der Elemente jeder Spalte genau eins ist.

Für das Beispiel ist

(2.5)

Allgemein hat die Übergangsmatrix die Form

(2.6)

2.5. Mehrstufige Übergänge

Die in 2.3. bestimmten Wahrscheinlichkeiten p_ik sind die Wahrscheinlichkeiten für einen direkten Übergang vom Zustand e_i in den Zustand e_k. Es ist aber auch möglich, daß es einen Übergang von e_i nach e_k nach mehreren Schritten gibt. In diesen Zwischenschritten durchläuft das System dann zuerst andere Zustände.
Der Käfer könnte z. B., wenn er in e₁ ist, nach zwei Schritten nach e₄ (über e₂ oder e₃) gelangen, während dies in einem Schritt nicht möglich ist.
Die Anzahl der Schritte bezeichnet man mit n, die Wahrscheinlichkeit für einen Übergang vom Zustand e_i in den Zustand e_k nach n Schritten nennt man n-stufige Übergangswahrscheinlichkeit, die als p_ik(n) geschrieben wird. Anstatt p_ik(1) schreibt man nur p_ik.
Bei unserem Beispiel ist also p₁₄(2) gesucht. Anhand des Kreisdiagramms stellt man fest, daß es zwei Wege gibt. Nach der Regel der totalen Wahrscheinlichkeit und der Pfadregel ergibt sich daher

(2.7)

Mit n = 3 ergibt sich für diesen Übergang
(e₁ ® e₂ ® e₃ ® e₄ / e₁ ® e₂ ® e₄ ® e₄ / e₁ ® e₃ ® e₄ ® e₄):

(2.8)

Natürlich kann man auch die Wahrscheinlichkeiten für einen 2-stufigen Übergang in einer Matrix P(2), die auch eine stochastische Matrix ist, anordnen.

Allgemein ist

(2.9)

Das Ermitteln der n-stufigen Übergangswahrscheinlichkeit mit der Pfadregel ist besonders bei großem n sehr aufwendig. Mittels der Übergangsmatrix können die n-stufigen Übergangswahrscheinlichkeiten leichter ermittelt werden.

Abbildung 3 zeigt das Baumdiagramm für einen allgemeinen Übergang von e_i nach e_k mit n = 2.

Abbildung 3

Man kann feststellen, daß

(2.10)

Das bedeutet, daß p_ik(2) das Produkt aus der i-ten Zeile von P und der k-ten Spalte von P ist, also das ik-te Element von P². Denn nach den Rechenregeln zur Matrizenmultiplikation errechnen sich die Elemente von P² als Skalarprodukt aus dem i-ten Zeilenvektor von P und dem j-ten Spaltenvektor von P.
Für jedes beliebige n, so sagt Arthur Engel in [2], ergibt sich allgemein hieraus:

(2.11)

Das bedeutet, daß

Daraus folgt schließlich:

Die einzelnen Elemente der Matrix Pⁿ = P(n) setzen sich aus der Summe der Wahrscheinlichkeiten aller möglichen Pfade zusammen, die einen Übergang vom Zustand e_i in den Zustand e_k nach n Schritten machen.
Man kann also die 2-stufigen Übergangswahrscheinlichkeiten über P(2) = P² ausrechnen.
Wenn man P(2) für das Beispiel berechnet, erhält man:

(2.14)

P(2) = P2= P * P

In dieser Matrix P(2) ist p₁₄(2) das Element in der 1. Zeile und 4. Spalte:

(2.15)

Dieser Wert und der in (2.7) berechnete Wert sind natürlich gleich groß.
Man kann natürlich auch P(3) auf diese Art und Weise berechnen:

(2.16)

P(3) = P3= P * P 2

(2.17)

Auch hier stimmt der Wert mit dem Ergebnis der Rechnung in (2.8) überein. Auch alle andere n-stufigen Übergangswahrscheinlichkeiten lassen sich so berechnen.

2.6. Anfangsverteilung

Wie bereits erwähnt, benötigt man neben dem Zustandsraum und der Übergangswahrscheinlichkeit die Anfangsverteilung, um eine Markow-Kette zu betrachten. Es empfiehlt sich die Anfangsverteilung als Zeilenvektor zu schreiben. Dieser Zeilenvektor hat wie die Übergangsmatrix die Spaltenanzahl N, denn er muß eine Anfangswahrscheinlichkeit für jeden Zustand liefern. Der sogenannte Anlaufvektor hat die Form

(2.18)

= ( p1(0), p2(0), …, pN(0) ),

wenn p_j die Wahrscheinlichkeit dafür ist, daß die Markow-Kette im Zustand e_j beginnt. Die Summe der Elemente des Anlaufvektors ist nach der Überlegung in (2.4) genau eins.

Allgemein bezeichnet man bei Markow-Ketten einen Vektor

(2.19)

(p1, p2, …, pN)

mit pi ³  0 und

als Verteilung.

Wenn man bei dem Beispiel mit dem Käfer eine zufällige Anfangsverteilung möchte, ist

(2.20)

= (, , ,  ),

weil die Wahrscheinlichkeit für den Beginn der Markow-Kette in einem Zustand e_j (mit j = 1, …, N) bei einer zufälligen Anfangsverteilung ist.
Möchte man hingegen in einem bestimmten Zustand e_j beginnen, so ist p_j = 1 und alle anderen Anfangswahrscheinlichkeiten sind Null. Wenn der Käfer in e₁ starten sollte, wäre

(2.21)

= ( 1, 0, 0, 0 )

2.7. Spätere Wahrscheinlichkeitsverteilung

Um die Wahrscheinlichkeit p_i(n) zu bestimmen, daß der Prozeß zum Zeitpunkt n im Zustand e_i ist, bildet man den Wahrscheinlichkeitsvektor

(2.22)

= (p1(n), p2(n), …, pN(n))

für n = 0, 1, …, N

Die Elemente des Wahrscheinlichkeitsvektors ergeben in der Summe wegen der Aussage in (2.4) ebenfalls genau eins.

Die Anfangsverteilung muß dem Ablauf des Prozesses vorangestellt werden, deshalb wird die Anfangsverteilung (Zeitpunkt n = 0) auch als 0-Schritt bezeichnet.

Abbildung 4

Im Baumdiagramm für das Beispiel (Abbildung 4) kann man gut erkennen, daß vor den Übergangswahrscheinlichkeiten die Anfangsverteilungen von Bedeutung sind.

Nach der Pfadregel und den Überlegungen in 2.5. ergibt sich daher die Wahrscheinlichkeit für einen bestimmten Zustand e_i zum Zeitpunkt n:

(2.23)

pi(n) =

Für alle Zustände kann man diese Wahrscheinlichkeiten zum Zeitpunkt n in einem Wahrscheinlichkeitsvektor zusammenfassen:

(2.24)

= * Pn

Diese Rekursionsformel ist sehr wichtig, denn sie ermöglicht ein leichtes Berechnen der Wahrscheinlichkeiten.
Wenn man z. B. die Wahrscheinlichkeitsverteilung für den Käfer im Wegenetz zum Zeitpunkt n = 3 bestimmen möchte, benötigt man nur

1. den Anlaufvektor  = 
2. die Übergangsmatrix

Jetzt kann man diese Verteilung berechnen:

(2.25)

= *P3 = *  =

Eine Markow-Kette ist also über Anfangsverteilung, Übergangswahrscheinlichkeiten und Zustandsraum vollständig definiert, daher kann sie durch das Tripel

dargestellt werden.

2.8. Langfristiges Verhalten

2.8.1. Grenzmatrix

Wenn man bei dem Beispiel die Übergangswahrscheinlichkeiten für größere n berechnet, kann man feststellen, daß auf drei Dezimale gerundet:

(2.27)

P(18) = P(17) =

Der Käfer befindet sich also nach dem Zeitpunkt n = 17 mit einer Wahrscheinlichkeit von 31% im Zustand e₄, unabhängig von den früheren Zuständen, denn die Zeilen der Matrix sind gleich.
Es liegt offensichtlich ein asymptotisches Verhalten der Markow-Kette vor. Das System strebt also gegen gewisse Grenzwerte der Übergangswahrscheinlichkeiten, die man in einer Grenzmatrix zusammenfassen kann.
Als Grenzmatrix ist definiert:

(2.28)

P¥  :=  =

Das ik-te Element der Grenzmatrix ist

(2.29)

= (pik(1), pik(2),…)

Es muß nicht immer eine Grenzmatrix existieren.

Wenn alle Zeilen der Grenzmatrix gleich sind, handelt es sich um eine ergodische Verteilung, d.h. sie ist unabhängig von der Anfangsverteilung.

2.8.2. Grenzverteilung

Als Grenzverteilung ist definiert

(2.30)

:=  = (p1(n), p2(n), …, pN(n)) = (p1, p2, …, pN)

2.8.3. Stationäre Verteilung

Wie man an dem Beispiel durch Hochrechnen in 2.8.1. feststellt, kann es vorkommen, daß das System sich ab einem gewissen Zeitpunkt in einem Gleichgewichtszustand befindet.

Die Grenzverteilung  heißt stationäre Verteilung, wenn 

(2.31)

* P =

mit

Diese Gleichung kann man umformen zu:

(2.32)

* P -  = 0

oder zu

(2.33)

* (P - E) = 0

E ist die Einheitsmatrix in N ´  N –Form. Ihre Elemente auf der Hauptdiagonalen sind eins, die anderen Elemente sind Null.
Ausführlich bedeutet der Ausdruck in (2.33) nach den Regeln der Matrizenrechnung:

Man erhält also ein lineares Gleichungssystem. Wenn man die ersten N-1 Gleichungen addiert, erhält man:

Wegen (2.4) ist die letzte Gleichung überflüssig, daher kann sie ersetzt werden durch

Durch dieses Vorgehen kann man allerdings auch eine nicht-trivale Lösung erhalten. Dieses neue Gleichungssystem muß man lösen, z. B. durch den Gauß-Algorithmus, um die stationäre Verteilung zu finden. Man kann das lineare Gleichungssystem aber auch durch Matrizenrechnung lösen. Man geht von der Gleichung in (2.33) aus – in ausführlicher Schreibweise:

(2.37)

(1, N) * ( P – E)(N, N) = (1, N)

Entsprechend dem Zusammenhang in (2.35) und (2.36) kann man jedes Element der letzten Spalte der Matrix (P – E) und von durch eine Eins ersetzen. Diese Matrix wird im folgenden mit L bezeichnet.

(2.38)

(1, N) * L (N, N) = (0, 0, …, 1)(1, N)

Weil L * L^–1 = E gilt

(2.39)

(1, N) = (0, 0, …, 1)(1, N) * L–1

Daher ist die letzte Zeile von L^–1.

Wenn man die stationäre Verteilung für das Beispiel sucht, muß man deshalb zuerst (P – E) bestimmen:

(2.40)

(P – E) =

Danach bildet man L:

(2.41)

L =

Danach bildet man schließlich nach den Regeln der Matrizentheorie, z. B. durch den Gauß-Algorithmus, der im Anhang beschrieben wird, die Inverse zu L:

(2.42)

L-1=

Daher ist:

(2.43)

=

Die so berechnete stationäre Verteilung, die man auch Fixvektor nennt, stimmt mit der Grenzverteilung überein.
Es gibt nur dann eine stationäre Verteilung sagt Eberhard Lehmann in [1], wenn es in irgendeiner Potenz der Übergangsmatrix P eine Spalte gibt, in der kein Element Null ist. Wenn diese Bedingung, die man als Spaltenkriterium bezeichnet, erfüllt ist, gibt es die Grenzmatrix und die Grenzverteilung ist eine ergodische Verteilung.

3. Klassifikationen

3.1. Besondere Zustände

3.1.1. Absorbierende Zustände

Ein Zustand e_i heißt absorbierend, wenn er nicht mehr verlassen werden kann, also wenn

Die Menge R aller absorbierenden Zustände wird als Rand von M bezeichnet.

3.1.2. Innere Zustände

Als innere Zustände werden alle nicht-absorbierende Zustände bezeichnet. Die Menge I der inneren Zustände ist daher I = M \ R.

3.1.3. Transiente Zustände

Man nennt einen Zustand e_i transient (vorübergehend, unwesentlich), wenn ein Zustand e_k existiert, der von e_i aus erreichbar ist, aber von dem aus kein Übergang zurück nach e_i möglich ist. Mathematisch bedeutet das:

3.1.4. Rekurrente Zustände

Den Zustand e_i nennt man rekurrent, wenn ein Übergang von jedem Zustand e_k, der von e_i aus erreicht werden kann, zurück nach e_i möglich ist. Ein rekurrenter Zustand erfüllt daher die Bedingung:

3.1.5. Periodische Zustände

Einen Zustand e_i nennt man periodisch, wenn eine Rückkehr nach e_i nicht nach einer beliebigen Schrittzahl möglich ist.
T_i sei die Menge aller n, für die p_ii(n) > 0 gilt, also

Als Periode per(e_i) eines Zustands ist definiert

3.1.6. Aperiodische Zustände

Ein Zustand e_i wird als aperiodisch bezeichnet, wenn seine Periode genau eins oder unendlich ist. Die Bedingung für einen aperiodischen Zustand ist deshalb:

3.2. Wichtige Formen von Markow-Ketten

3.2.1. Endliche Markow-Kette

Eine Markow-Kette heißt endlich, wenn die Wahrscheinlichkeit dafür, daß ein bestimmter Zustand eintritt, nur von dem vorausgegangenen Zustand abhängig ist. Weil das die Markow-Eigenschaft ist, ist normalerweise jede Markow-Kette endlich.

3.2.2. Homogene Markow-Kette

Eine Markow-Kette ist homogen, wenn die Übergangswahrscheinlichkeiten zeitunabhängig, also unabhängig von der Nummer des Versuchs sind.

Sie muß daher die folgende Bedingung erfüllen:

Das ist die Art von Markow-Ketten, die in der Regel benutzt werden, weil sie vergleichsweise einfach zu berechnen sind. Man wird immer versuchen das Modell so zu entwickeln, daß die Markow-Kette endlich und homogen ist.
Auch das Beispiel in 2. ist eine endliche, homogene Markow-Kette, deshalb besitzen die in 2. hergeleiteten Formeln nur Gültigkeit für endliche und homogene Ketten. Bei inhomogenen Ketten ist es wesentlich aufwendiger Beziehungen oder Formeln für n-stufige Übergangswahrscheinlichkeiten oder Grenzverteilungen herzuleiten.

3.2.3. Irreduzible Markow-Kette

Sind alle Zustände einer Markow-Kette gegenseitig erreichbar, dann bezeichnet man einer Markow-Kette als irreduzibel. Dazu muß es ein n geben, für das p_ik(n) > 0 bei allen Übergängen von e_i nach e_k gilt. Ist diese Bedingung nicht erfüllt, bezeichnet man die Kette als reduzibel.
Durch die Irreduzibilität wird allerdings noch keine Aussage getroffen, ob es eine Potenz von P gibt, in der alle Wahrscheinlichkeiten größer als Null sind.

3.2.4. Absorbierende Markow-Kette

Eine Markow-Kette heißt absorbierend, wenn sie mindestens einen absorbierenden Zustand hat.

3.2.5. Reguläre Markow-Kette

Eine Markow-Kette ist regulär, wenn sie irreduzibel ist und alle Zustände aperiodisch sind. Deshalb gibt es bei einer regulären Markow-Kette ein n, so daß Pⁿ nur positive Elemente enthält. Denn aufgrund der Irreduzibilität muß es für jedes ik-te Elemente eine Potenz von P geben, in der dieses Element größer als Null ist, und es muß eine Potenz von P geben, in der alle Übergangswahrscheinlichkeiten größer als Null sind, weil alle Zustände aperiodisch sind. Daher ist bei jeder regulären Markow-Kette das Spaltenkriterium erfüllt und es existiert eine stationäre Verteilung.

4. Beispiel für eine absorbierende Markow-Kette

4.1. Vorstellung des Beispiels

(übernommen aus Eberhard Lehmann "Fallstudien mit dem Computer", S. 180)

Bei der Erprobung einer neuen Gangschaltung ergab sich für das Umschalten der Gänge folgende Statistik:

von Gang...	in Gang...	% der Fälle
L (Leerlauf)	R (Rückwärtsgang)	10
L	1 (1. Gang)	80
L	2 (2.Gang)	10
1	L	15
1	2	85
2	L	20
2	1	80

Der Rückwärtsgang klemmte, war er einmal eingelegt, konnte er ohne Reparatur nicht herausgenommen werden.

4.2. Definition der Zustände

Zuerst werden die absorbierenden Zustände und danach erst die inneren Zustände durchnumeriert. Wenn r die Anzahl der absorbierenden Zustände ist, dann ist

Weil bei diesem Beispiel der Rückwärtsgang R der absorbierende Zustand ist, seien die Zustände folgendermaßen belegt:

e1	R
e2	L
e3	1
e4	2

Daraus ergibt sich

Abbildung 5 zeigt diese Zusammenhänge in einem Kreisdiagramm.

Abbildung 5

Die Übergangsmatrix hat in diesem Fall die Form

(4.5)

P =

Der Zeitparameter ist bei dieser Festlegung gleichzusetzen mit der Anzahl der Schaltvorgänge, deshalb ist er diskret.

4.3. Fundamentalmatrix der absorbierenden Markow-Kette

Aufgrund den Aussagen in 3.1.1. erhält man für die Übergangsmatrix P, wenn man eine Matrix A für die Wahrscheinlichkeiten der Übergänge aus einem inneren in einen absorbierenden Zustand und eine Matrix B für die Übergangswahrscheinlichkeiten zwischen den inneren Zuständen definiert:

(4.6)

P =

A hat die Form (N - r) ´  r, B ist eine Matrix der Form (N – r) ´  (N – r).

Für das Beispiel ist

(4.7)	A =	und
	B =

Weil ein Produkt aus E und einer beliebigen Matrix E und ein Produkt mit 0 wieder 0 ergibt, gilt für die Potenzen der Übergangsmatrix:

(4.8)

Pn =

Es wird deutlich, daß die Matrix B sehr wichtig für die Berechnung von Pⁿ ist. Weil es sich um eine absorbierende Kette handelt ist

(4.9)

Bn = 0

Besonders interessant ist bei absorbierenden Ketten die mittlere Anzahl der Besuch in e_j, wenn die Kette in e_i beginnt. Im folgenden sei diese Zahl t_ij. Weil der Besuch in e_j bei jedem Besuch des Zustand e_k mit der Wahrscheinlichkeit p_kj möglich ist, gilt

(4.10)

Wenn i ¹ j, dann ist tij =  Wenn i = j, dann ist tij = 1 +,

denn i = j bedeutet, daß das System sich bereits in e_j und daß deshalb zu den zukünftigen erwarteten Besuchen eins addiert werden muß.

Der Zusammenhang in (4.10) bedeutet in Matrizenschreibweise:

Diesen Ausdruck kann man umformen:

Aufgrund von (4.9) gilt

Deshalb ist

(4.16)

P¥  =  =

Für das Beispiel erhält man durch die Bildung der Inverse zu (E – B) ungefähr

(4.17)

T =

Als Grenzmatrix erhält man deshalb

(4.18)

P¥  =

Die Grenzmatrix macht deutlich, daß auf einen langfristigen Zeitraum betrachtet das System den absorbierenden Zustand e₁ erreicht und nicht mehr verläßt. Für das Anwendungsbeispiel am Auto bedeutet das, daß irgendwann der Rückwärtsgang eingelegt wird, der erst durch Reparatur wieder zu lösen ist.

Die Matrix T wird als Fundamentalmatrix der absorbierenden Markow-Kette bezeichnet, weil durch sie neben der Grenzmatrix und den erwarteten Besuchen in einem Zustand noch zwei andere wichtige Größen berechnet werden können.
Mit m_i bezeichnet man die erwartete Anzahl an Schritten bis zur Absorption in dem Rand bei einem Start in e_i und mit d_ij wird die Wahrscheinlichkeit für eine Absorption in e_j bei einem Start in e_i bezeichnet.

Engel sagt in [2], daß die Verweilzeit V_i in einem inneren Zustand e_i und die Schrittzahl bis zur Absorption X_i gleich groß sind.

Deshalb gilt:

Die erwartete Verweilzeit in einem inneren Zustand ist gleich der mittleren Anzahl der Besuche in diesem Zustand beim Start in einem beliebigen inneren Zustand ist, also

(4.20)

E (Vi)  =

Weil E (X_i) = m_i ist gilt daher

(4.21)

mi =

Dieser Ausdruck bedeutet, daß die m_i gleich der Summe der i-ten Zeile der Fundamentalmatrix T sind.

Für das Beispiel erhält man so die folgenden Werte

Man stellt dabei fest, daß die erwartete Anzahl der Schaltvorgänge bis zum Einlegen des Rückwärtsgangs am kleinsten ist, wenn am Anfang der Leerlauf eingelegt ist.

Ebenso einfach lassen sich die d_ij berechnen. Parallel zu den Überlegungen in (4.10) kann man hier nämlich die Aussage treffen

(4.23)

dij = pij +

mit i Î  I, j Î  R,

denn die Wahrscheinlichkeit von e_i aus in e_j absorbiert zu werden setzt sich aus der Wahrscheinlichkeit für die direkte Absorption in einem Schritt und der Summe der Absorptionswahrscheinlichkeiten der Nachbarzustände zusammen.

Wenn man die d_ij in einer neuen Matrix D zusammenfaßt, läßt sich der Ausdruck in (4.23) in Matrizenschreibweise darstellen als

Durch weitere Umformungen erhält man:

Durch Einsetzen von T = (E – B)^-1 erhält man schließlich

Dieser Ausdruck wird in (4.16) bereits verwendet, man kann daher jetzt auch diese Aussage umformen und erhält so für die Grenzmatrix

(4.29)

P¥  =

An dem konkreten Beispiel erhält man für die Absorptionswahrscheinlichkeiten

(4.30)

D =

Diese Werte decken sich mit den Werten aus (4.18) und bedeuten, daß mit einer Wahrscheinlichkeiten von 100% irgendwann der Rückwärtsgang eingelegt wird.
Durch die Ermittlung in (4.22) der mittleren Anzahl der Schaltvorgänge vor dem Einlegen des Rückwärtsgangs ist jedoch das Einlegen des Rückwärtsgangs, wenn man im Leerlauf beginnt, früher zu erwarten.

5. Nachwort

In dieser Facharbeit konnte ich aufgrund der vielen Einsatzmöglichkeiten nur einen kleinen Einblick in die Theorie und Anwendung der Markow-Ketten geben. Deshalb habe ich mich auf einfache Problemstellungen beschränkt und mehr die mathematischen Grundlagen untersucht. Markow-Ketten spielen nämlich eine sehr große Rolle bei komplexen Berechnungen der Populationsdynamik, der Produktionsplanung und in vielen anderen Bereichen der Statistik, die ich in dieser Arbeit nur andeuteten konnte.

Literaturverzeichnis

[1]	Eberhard Lehmann: "Fallstudien mit dem Computer; Markow-Ketten und weitere Beispiele aus der linearen Algebra und Wahrscheinlichkeitsrechnung", B. G. Teubner, Stuttgart 1986
[2]	Arthur Engel: "Wahrscheinlichkeitsrechnung und Statistik Band 2", Klett Studienbücher, Stuttgart 1976
[3]	Alfréd Rényi: "Wahrscheinlichkeitsrechnung", VEB Deutscher Verlag der Wissenschaften, Berlin 1973
[4]	Hermann Athen: "Wahrscheinlichkeitsrechnung und Statistik", Schroedel Verlag, Hannover, und Verlag Schoeningh, Paderborn 1968
[5]	"Lehr- und Übungsbuch Mathematik Band IV", Verlag Harri Deutsch, Thun und Frankfurt/Main 1987

Anhang

Gaußverfahren zur Bildung der inversen Matrix

Die zu Inverse zu einer N ´  N-Matrix A wird gebildet durch den Austausch von y_i gegen x_i. Wichtig sind für dieses Verfahren das Pivotelment g (Hauptelement, Kreuzungspunkt i-te Zeile und i-te Spalte), die Schlüsselzeile z_i (i-te Zeile) und die Schlüsselspalte (i-te Spalte) s_i.

Die Elemente errechnen sich wie folgt für i = 1, …, N

1. g ' = 
2. z_i' = 
3. s_i' = 
4. alle anderen Elemente a_ij' = a_ij + s_i * z_i'

Anmerkung vom 13. März 2003

Download als PDF

markow-ketten.pdf