_____________________________________________________________________________________
Inhalt....: Absorbierende Markoff-Kette
Kategorie.: Unterrichtsmaterial
Mathematik: Lineare Algebra, Stochastik
MuPAD.....: 3.1.0
Datum.....: 2005-01-12
Autoren...: Monika v. zur Mühlen <mvzmuehlen@web.de>
Funktionen: matrix, linalg::transpose
_____________________________________________________________________________________
Markoff-Ketten sind ein interessantes Thema für einen anwendungsorientierten Mathe-
matikunterricht, das Inhalte der Stochastik mit der Linearen Algebra verbindet. Sie bieten
sich an zur Behandlung der Matrizenrechnung, die in Nordrhein-Westfalen zu den inhalt-
lichen Schwerpunkten des künftigen Zentralabiturs gehören wird.
Das Arbeitsblatt ist entwickelt worden auf der Grundlage von:
Lambacher-Schweizer, Stochastik, Stuttgart 2003
Ameise auf Wanderschaft
- absorbierende Markoff-Kette -
Eine Ameise startet in Zelle 4 und wechselt von Minute zu Minute in eine der Nachbarzellen, dabei
hat sie einen „Linksdrall" und geht jeweils mit einer Wahrscheinlichkeit von 0,6 nach links und mit
einer Wahrscheinlichkeit von 0,4 nach rechts. Wenn sie in einer der Randzellen gelandet ist, bleibt
sie dort für immer gefangen.
a)-------Stelle die Übergangsmatrix U auf, die diesen Prozess beschreibt.
b)-------Bestimme die Wahrscheinlichkeiten, mit denen die Ameise in Zelle 1 bzw. in Zelle 6 gefangen
----------wird.
c)-------Wie lange braucht die Ameise bis zu ihrer Gefangennahme? Berechne die mittlere Zeitdauer.
Lösung zu a):
Es gilt z.B. für die Wahrscheinlichkeit, dass die Ameise sich in Zelle 3 aufhält:
z3:= 0.6*z4 + 0.4*z2
oder in Zelle z1:
z1:= 0.6*z2 + 1*z1 (Wenn die Ameise bereits in z1 gefangen ist, bleibt sie auch dort!)
Aus diesen Überlegungen ergibt sich die folgende Übergangsmatrix:
U:= matrix([[1,0.6,0,0,0,0], [0,0,0.6,0,0,0],[0,0.4,0,0.6,0,0],
[0,0,0.4,0,0.6,0],[0,0,0,0.4,0,0],[0,0,0,0,0.4,1]])
Zu Beginn befindet sich die Ameise mit Wahrscheinlichkeit 1 in Zelle 4 und mit Wahrscheinlichkeit 0
in allen anderen Zellen.
v0:= matrix([0,0,0,1,0,0])
Nach einer Minute:
v1:= U*v0
v2:= U*v1
Und nach 10 Minuten:
DIGITS:= 4: v10:= U^10*v0
Lösung zu b):
Mit welchen Wahrscheinlichkeiten landet die Ameise, von einer bestimmten Zelle aus gesehen,
im Endzustand z1?
Für die Übergangswahrscheinlichkeiten in den Zustand z1 gilt:
a1 = 1-------------------------------------------------(Wenn die Ameise in z1 ist, bleibt sie dort.)
a2 = 0,4*a3 + 0,6*a1 = 0,4*a3 + 0,6---------(Von z2 aus kann sie direkt nach z1 gelangen oder den
-----------------------------------------------------------Umweg über z3 nehmen)
a3 = 0,4*a4 + 0,6*a2-----------------------------(Von z3 aus kann sie nur über z2 oder z4 nach z1 gelangen,)
a4 = 0,4*a5 + 0,6*a3
a5 = 0,6*a4
a6 = 0-------------------------------------------------(Von z6 aus kann die Ameise nicht mehr nach z1 gelangen!)
Offenbar lassen sich diese Gleichungen aus der Übergangsmatrix ableiten,
1_____0.6____0_____0_____0_____0
0_____0_____0.6____0_____0_____0
0_____0.4____0_____0.6____0_____0
0_____0_____0.4____0_____0.6____0
0_____0_____0_____0.4____0_____0
0_____0_____0_____0_____0.4____1
......... wenn man die Zeilen weglässt, die sich auf die Endzustände beziehen (das sind hier die
Zeilen 1 und 6), und die Matrix spaltenweise liest.
Durch Transponierung der rot geschriebenen Teilmatrix ergibt sich zunächst die Matrix Q:
Q:= linalg::transpose( matrix(
[[0,0.6,0,0], [0.4,0,0.6,0], [0,0.4,0,0.6], [0,0,0.4,0]]
))
Die Matrix Q wird mit dem Vektor der Wahrscheinlichkeiten multipliziert, die Zeile der Matrix U,
die zu z1 gehört, wird ebenfalls transponiert und hinzuaddiert. Es ergibt sich das oben aufgeführte
Gleichungssystem.
matrix([a2, a3, a4, a5]) =
Q*matrix([a2, a3, a4, a5]) + matrix([0.6, 0, 0, 0])
Die Gleichung wird aufgelöst mit Hilfe der inversen Matrix. Es gilt:
a:= matrix([a2, a3, a4, a5]):
print(Typeset,hold((1 - Q)*a) = matrix([0.6, 0, 0, 0]))
Daraus folgt:
hold(a) = (1-Q)^(-1)*matrix([0.6, 0, 0, 0])
Die Matrix F wird Fundamentalmatrix der Markoff-Kette genannt.
F:= (1-Q)^(-1)
Berechnung der Absorptionswahrscheinlichkeiten mit Hife von F:
a:= F*matrix([[0.6], [0], [0], [0]]) // Absorption in z1
b:= F*matrix([[0], [0], [0], [0.4]]) // Absorption in z6
DIGITS:= 3:
a[3]
b[3]
Die Ameise wird ihre Wanderung mit einer Wahrscheinlichkeit von 64% im ersten Feld beenden und mit
einer Wahrscheinlichkeit von 36% im zweiten Feld..
Lösung zu c):
Mit der Fundamentalmatrix kann auch die mittlere Schrittlänge bestimmt werden:
m:= F*matrix([[1], [1], [1], [1]])
m[3]
Die Ameise benötigt im Mittel 6 Minuten bis zur Gefangennahme, wenn sie in Feld 4 startet.
Variation:
Die Ameise startet in Zelle 3, und es gelten nun die folgenden Übergangswahrscheinlichkeiten:
- mit einer Wahrscheinlichkeit von 0,1 bleibt sie in der jeweiligen Zelle,
- mit einer Wahrscheinlichkeit von 0,5 geht sie nach links,
- mit einer Wahrscheinlichkeit von 0,4 nach rechts.
Wenn sie in einer der Randzellen gelandet ist, bleibt sie dort für immer gefangen.
________________________________________________________________________________
Anmerkungen:
1. Selbstlernmaterial zur Matrizenrechnung unter:
http://www.learnline.nrw.de/angebote/selma/foyer/projekte/hammproj3/index.html
http://www.learnline.nrw.de/angebote/selma/foyer/projekte/dinslakenproj3/index.html
2. Weitere Anregungen finden Sie unter: http://schule.mupad.de bzw. http://studium.mupad.de
_______________________________________________________________________________