_____________________________________________________________________________________
Inhalt....: Absorbierende Markoff-Kette II
Kategorie.: Unterrichtsmaterial
Mathematik: Lineare Algebra, Stochastik
MuPAD.....: 3.1.0
Datum.....: 2005-03-08
Autoren...: Günter vom Stein <gvomstein@gmx.net>
Funktionen: matrix, linalg::matlinsolve, linalg::gaussElim
_____________________________________________________________________________________
Absorbierende Markoff-Ketten
Die Beschäftigung mit der Wahrscheinlichkeit vollständiger Serien in der Stochastik
führt unmittelbar zu einer Markoff-Kette mit absorbierendem Zustand. Die Markoff-
Kette verbindet so zwei wichtige Gebiete der Mathematik. Besonders interessant
sind Markoff-Ketten mit mehr als einem absorbierenden Zustand.
Das Arbeitsblatt ist aus dem Unterricht mit dem Lehrbuch von Schroedel, Elemente der Mathematik,
Leistungskurs Stochastik, entstanden und ergänzt die dortige Darstellung.
Ich verweise auf das kurz zuvor erschienene Arbeitsblatt von Frau Monika v. zur Mühlen zum selben
Thema. Den Begriff 'Fundamentalmatrix' habe ich aus diesem Arbeitsblatt übernommen.
Übungsaufgabe:
Ein Käfer krabbelt auf der folgenden Abbildung. In den Zuständen A und B wird er von einem
Vogel gefressen (absorbierende Zustände).
a) Untersuche 
für wachsende n, interpretiere das Ergebnis.
b) Mit welcher Wahrscheinlichkeit erfolgt die Absorption in A , mit welcher in B ?
c) Wie lange dauert es im Mittel bis zur Absorption?
(Quelle unbekannt)
Für die beiden Aufgabenteile b) und c) werden sowohl eine analytisch-algebraische Lösung
als auch eine empirisch-experimentelle Lösung angegeben.
Zum Sprachgebrauch:
Zur Abkürzung wird die Menge aller absorbierenden Zustände Rand (der Markoff-Kette)
genannt, ein einzelner absorbierender Zustand wird auch Randzustand oder Endzustand
genannt. Die Zustände, die nicht zum Rand gehören, heißen innere Zustände.
DIGITS:= 3:
Lösungen
Aufgabe a)
Die Übergangs-Matrix gewinnt man aus dem bekannten Von-Nach-Schema.
Wir sortieren die drei inneren Zustände an den Anfang und die beiden
absorbierenden Zustände ans Ende: Z1, Z2, Z3, A, B:
M:= matrix([
[ 0, 1/4, 1/4, 0, 0],
[1/5, 0, 1/2, 0, 0],
[4/5, 5/8, 0, 0, 0],
[ 0, 1/8, 0, 1, 0],
[ 0, 0, 1/4, 0, 1]
])
Wir wählen steigende Schrittzahlen und geben die Matrix der Übersicht halber
dezimal aus:
float(M^10), float(M^25);
float(M^100)
Man kommt zu dem interessanten Ergebnis, dass zwar offensichtlich eine Grenzmatrix
existiert, diese aber nicht aus gleichen Spalten besteht, wie es bei Markoff-Ketten ohne
absorbierende Zustände bzw. mit nur einem absorbierenden Zustand der Fall ist.
Wie die nächsten Berechnungen zeigen, besitzt die Kette drei verschiedene
stationäre Verteilungen, je nachdem, aus welchem Zustand man startet, und diese
drei Fix-Vektoren entsprechen gerade den ersten drei Spalten der Grenzmatrix, d.h.
genau den Spalten, die zu den inneren Zuständen gehören.
x1:= matrix([1,0,0,0,0]):
x2:= matrix([0,1,0,0,0]):
x3:= matrix([0,0,1,0,0]):
float(M^100*x1), float(M^100*x2), float(M^100*x3)
Die Berechnung einer stationären Verteilung mit dem Ansatz
gelingt hier folglich nicht, weil es keine eindeutige Lösung dieser Gleichung gibt,
obwohl ansonsten jede Gleichung der Art
eine Lösung hat, wie die Überprüfung mit gaussElim ergibt (keine Nullzeile) :
x:= matrix([1,0,0,0,0]):
linalg::matlinsolve(M-1,x);
linalg::gaussElim(M);
Weiter unten wird schließlich noch gezeigt, dass die hier noch näherungsweise
berechneten Fix-Vektoren tatsächlich von der Matrix M nicht verändert werden.
Wir benutzen dann die exakten Werte.
Aufgabe b)
1. Teil: Absorptionswahrscheinlichkeiten für die inneren Zustände - die
empirisch-experimentelle bzw. iterative Lösung:
Mit den letzten Berechnungen in Aufgabe a) hat man den ersten Teil von Aufgabe b)
auch schon bearbeitet. Der erste der drei Fixvektoren wird so interpretiert, dass man
aus Zustand 1 mit der Wahrscheinlichkeit 0,245 zu dem absorbierenden Zustand A
gelangt und mit Wahrscheinlichkeit 0,755 zu dem absorbierenden Zustand B.
Mit den beiden anderen Startvektoren erhält man die Wahrscheinlichkeiten für
die Übergänge aus Zustand 2 und 3 in die absorbierenden Zustände.
Aufgabe b)
2. Teil: Analytisch-algebraische Lösung für die Bestimmung der
Absorptionswahrscheinlichkeiten:
Wir beginnen mit der Beendigung der Kette im absorbierenden Zustand A .
Das Prozess-Schema wird ergänzt um drei Pfeile, die symbolisch für die drei
Wahrscheinlichkeiten stehen, von den inneren Zuständen 1, 2 und 3 zu dem
absorbierenden Zustand A zu gelangen. Dasselbe kann man später für
den absorbierenden Zustand B vornehmen.
Mit diesen drei unbekannten Wahrscheinlichkeiten läßt sich ein LGS
aufstellen, aus dem man sie berechnen kann. Die Idee für den Ansatz lautet:
Die Wahrscheinlichkeit, von einem inneren Zustand Z zu dem absorbierenden
Zustand A zu gelangen, ist gleich der Summe aller gewichteten Wahrschein-
lichkeiten, mit denen man direkt oder über einen unmittelbaren Nachbarn zum
Zustand A gelangt.
Anmerkung: Ein Zustand kann, muss aber nicht sein eigener Nachbar sein.
In der vorliegenden Aufgabe ist dies nicht der Fall, es wäre aber denkbar, dass
der Käfer bei einem Schritt auch mit einer bestimten Wahrscheinlichkeit in einem
Zustand verbleibt (Ringpfeil).
Die drei Wahrscheinlichkeiten werden in der Skizze durch die roten Pfeile symbolisch
dargestellt. Es sind keine Käfer-Wege !!!
Man erhält die drei linearen Gleichungen
in Matrix-Schreibweise:
Vergleicht man die Matrix B dieser Gleichung mit der Übergangsmatrix,
so erkennt man sie wieder, wenn man die Übergangsmatrix transponiert,
was die Vertauschung von Spalten und Zeilen bedeutet:
MT:= linalg::transpose(M)
Wir denken uns die Matrix 
gemäß in Zonen aufgeteilt. Die nachfolgende Skizze
erklärt sich weitgehend selbst im Vergleich mit der obigen MuPAD-Ausgabe von 
.
Man verifiziere, dass die Matrix 
immer von dieser Gestalt ist, wenn im Von-Nach-Schema
die inneren Zustände vor den Randzuständen angeordnet sind, unabhängig von deren
Anzahlen.
Die Vektoren 
enthalten in ihren Komponenten die Wahrscheinlichkeiten,
aus den inneren Zuständen direkt zu einem Randzustand als Nachbarzustand
zu gelangen. Es gibt genausoviele Vektoren dieser Art wie Randzustände und die
Anzahl der Komponenten ungleich null in einem solchen Vektor ist gleich der Anzahl
der inneren Zustände, die Nachbarn des zu dem Vektor gehörenden Randzustands
sind.
Wir ziehen die Matrix B und die Vektoren 
aus der Matrix 
heraus, indem
wir zuerst die beiden letzten Zeilen löschen (Bereiche "0" und "E") und dann zutreffende
Spalten löschen. Zusätzlich definieren wir einen Variablenvektor :
C := linalg::delRow(MT,[4,5]):
B := linalg::delCol(C,[4,5]);
rA:= linalg::delCol(C,[1,2,3,5]);
rB:= linalg::delCol(C,[1,2,3,4]);
a := matrix([a1,a2,a3]):
Die Gleichung 
wird umgeformt zu
Mit MuPAD:
hold(a = B*a+rA);
a = B*a+r1
hold((1-B)*a = rA);
(1-B)*a = rA
Diese Gleichung können wir jetzt mit matlinsolve oder mit
der inversen Matrix lösen:
L:= linalg::matlinsolve(1-B,rA),
(1-B)^-1*rA
Interpretation: Der Lösungsvektor gibt nacheinander für alle drei inneren Zustände
die Übergangswahrscheinlichkeit in den Endzutand A an.
Wir berechnen zusätzlich die Übergangswahrscheinlichkeiten in den Endzustand B
und sehen uns zum Vergleich noch einmal die iterativ bestimmte Grenzmatrix an:
float(M^100);
float((1-B)^-1*rA), float((1-B)^-1*rB)
Wir erkennen die Übereinstimmung nach Drehen der Spalten.
Mit dem exakten Werten der Fix-Vektoren soll nun noch die Fix-Eigenschaft
bestätigt werden:
a:= (1-B)^-1*rA:
b:= (1-B)^-1*rB:
xg1:= matrix([0,0,0,a[1],b[1]]):
xg2:= matrix([0,0,0,a[2],b[2]]):
xg3:= matrix([0,0,0,a[3],b[3]]):
M*xg1 = xg1;
M*xg2 = xg2;
M*xg3 = xg3
Damit ist Aufgabe b) abgeschlossen.
Aufgabe c),
Teil 1: Mittlere Wartezeit (eigentlich: mittlere Schrittanzahl), ermittelt
mit der analytisch-algebraischen Methode:
Das Prozess-Schema wird wieder um drei Pfeile ergänzt. Dieses Mal stehen die
Pfeile aber symbolisch für die drei mittleren Schrittanzahlen, die von den inneren
Zuständen 1, 2 und 3 zu den absorbierenden Zuständen A und B zu gelangen.
Weil es nun keine Rolle spielt, ob ein Weg in A oder B endet, beziehen sich die
drei Variablen (= mittlere Schrittanzahlen) auf beide absorbierende Zustände
zugleich. In der Skizze kann dieser Umstand durch eine kleine Änderung zum
Ausdruck gebracht werden :
Ähnlich wie in Aufgabe b) lässt sich mit Hilfe dieser drei unbekannten mittleren
Schrittanzahlen ein LGS aufstellen. Man beachte noch einmal die völlig andere
Bedeutung der Variablen in Aufgabe b) und c).
Die Idee für den Ansatz lautet diesmal:
Die mittlere Dauer, von einem Zustand aus zum Rand (= irgendein absorbierender
Zustand) zu kommen, erhält man aus der Summe aller Weglängen zum Rand über
unmittelbare Nachbarzustände. Dabei kann wieder ein Zustand sein eigener Nachbar
sein (Ringpfeil). Eine Weglänge setzt sich zusammen aus dem einen Schritt zum Nach-
barzustand und der (noch unbekannte) mittleren Schrittzahl von dort zum Rand.
Die Weglänge wird gewichtet mit der Wahrscheinlichkeit, zu dem jeweiligen Nach-
barzustand überhaupt zu gehen. Ist der Rand selbst ein Nachbarzustand, beträgt
die Weglänge 1 Schritt, der ebenfalls gewichtet wird.
Gleichungen:
und wieder in Matrix-Schreibweise
wobei B genau dieselbe Matrix wie in Aufgabe b) ist !!
Nach Umstellung erhält man nun
Weil die inverse Matrix 
für die Berechnung so wichtig ist,
erhält sie einen eigenen Namen, nämlich Fundamentalmatrix der Markoffkette.
Rechnung:
F:= (1-B)^-1;
Eins:= matrix([1,1,1]):
F*Eins, float(F*Eins)
Interpretation: Vom Zustand 1 aus benötigt man im Mittel 7,22 Schritte, um
zum Rand, d.h. zu einem der beiden absorbierenden Zustände zu gelangen.
Von Zustand 2 aus werden 6,63 und von Zustand 3 aus 6,12 Schritte benötigt.
Zusammenfassung:
1. Die Multiplikation der Fundamentalmatrix mit einem
"Randvektor" ergibt die Übergangswahrscheinlichkeiten von allen
inneren Zuständen zu dem zugehörigen Randzustand.
2. Die Multiplikation der Fundamentalmatrix mit dem Eins-Vektor ergibt die
mittleren Schrittzahlen von allen inneren Zuständen zum Rand.
Aufgabe c),
Teil 2: Experimentelle Bestimmung der mittleren Schrittanzahl von den drei
inneren Zuständen aus.
Mit Hilfe des Zufallsgenerators von MuPAD wird vielfach nacheinander ein Weg
durch das Schema vom gleichen Startzustand bis zum Rand beschritten und
die jeweilige Schrittanzahl aufsummiert. Anschließend wird durch die Anzahl
der Versuche dividiert.
Anmerkung: Hier kommt die integrierte Programmierumgebung von MuPAD schön
zum Einsatz. Es wird evtl. nicht jede Schülerin und jeder Schüler Programmier-
erfahrung haben, die Erstellung eines Flussdiagrammes solte aber in jedem
Fall möglich sein.
MittSchritt:= proc(ZUS,n)
local s,d,Zust,z;
begin
r1:=random(1..5);
r2:=random(1..8);
r3:=random(1..4);
s:=0;
for i from 1 to n do
d:=0;Zust:=ZUS;
while TRUE do
d:=d+1;
if Zust=Z1
then z:=r1();
if z<5
then Zust:=Z3
else Zust:=Z2
end_if
else if Zust=Z2
then z:=r2();
if z<8
then if z<3
then Zust:=Z1
else Zust:=Z3
end_if
else break;
end_if
else z:=r3();
if z<4
then if z<2
then Zust:=Z1
else Zust:=Z2
end_if
else break;
end_if
end_if
end_if
end_while;
s:=s+d;
end_for;
print(float(s/n));
end_proc:
n:=20000:
MittSchritt(Z1,n),
MittSchritt(Z2,n),
MittSchritt(Z3,n);
7.22
6.64
6.17
Wiederholung zum Vergleich:
float(F*Eins)
______________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen finden Sie unter: http://schule.mupad.de bzw. http://studium.mupad.de
______________________________________________________________________________