28.01.04 Ariane Wietschke - Markov-Ketten 1

Markov-Ketten

Ariane Wietschke

Proseminar: Das virtuelle Labor

28.01.2004

28.01.04 Ariane Wietschke - Markov-Ketten 2

1. Herleitung der Definition

2. Komponenten von Markov-Ketten

3. Arten von Markov-Ketten

4. Anwendungsgebiete

5. To take home

Übersicht

28.01.04 Ariane Wietschke - Markov-Ketten 3

1. Herleitung der Definition2. Komponenten von Markov-Ketten

3. Arten von Markov-Ketten

4. Anwendungsgebiete

5. To take home

28.01.04 Ariane Wietschke - Markov-Ketten 4

Geschichte

- Beginn des 20. Jh. Andrej Andrejewitsch, Markov(1856 – 1922), Doeblin,Kolmogorov

- praktische Anwendbarkeit fehlte

- Bedeutung erst mit Verbreitung derComputertechnologie

- heute in nahezu allen Anwendungsgebieten derMathematik

28.01.04 Ariane Wietschke - Markov-Ketten 5

- Irrfahrt auf Menge {1,2,…,N} beginntin 2 und bewegt sich entsprechend desErgebnisses eines Münzwurfs nach rechtsoder links (hier: Kopf→rechts, Zahl→links)

- Für Randpositionen 1 und N sei Zusatzregeldefiniert (hier „kehre zurück zur Startposition“)

Beispiel 1

28.01.04 Ariane Wietschke - Markov-Ketten 6

Zustand 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.Kopf/Zahl Kopf Kopf Kopf Kopf Zahl Zahl Kopf Kopf Kopf ZahlPosition 3 4 5 6 5 4 5 6 7 6

23

45

65

45

67

6

0

2

4

6

8

1 2 3 4 5 6 7 8 9 10 11

Zustaende

Pos

ition

en

Beispiel 1

28.01.04 Ariane Wietschke - Markov-Ketten 7

Beispiel 2

- Irrfahrt auf {0,…,999} beginnt bei 0. Bewegung aus Position i zur Position (2i+i’) mod 1000,wobei i’ durch das Werfen eines Würfels (Augenzahl)ermittelt wird.

28.01.04 Ariane Wietschke - Markov-Ketten 8

Beispiel 2

Durchgang 1 2 3 4 5 6 7 8 9 10 11 12 13Augenzahl 2 3 3 5 5 2 1 6 3 4 1 1 5Zustand 2 7 17 39 83 168 337 680 363 730 461 923 851

337

680

363

730

461

923 851

0200400600800

1000

7 8 9 10 11 12 13

Zustaende

Pos

ition

en

28.01.04 Ariane Wietschke - Markov-Ketten 9

Beispiel 3

- Vorbereitung: 4 mal Münze werfen→ Anzahl der Köpfe wird Startposition einerIrrfahrt auf der Menge {0,…,999}

Bewegung entsprechend des Ergebnisses eines Münzwurfsvon Position i zur Position i+1 mod 1000 bzw. zur Position i-1 mod 1000 (hier: Kopf→i+1 mod 1000, Zahl→i-1 mod 1000)

28.01.04 Ariane Wietschke - Markov-Ketten 10

Durchgang 1 2 3 4 5 6 7 8 9Kopf/Zahl Zahl Kopf KopfKopf KopfZahl KopfZahlZahlZustand 0 1 2 3 4 3 4 3 2

1 mal Kopf→Startposition i=1

10

12

34

34

32

012345

1 2 3 4 5 6 7 8 9 10

Zustaende

Po

sitio

nen

Beispiel 3

28.01.04 Ariane Wietschke - Markov-Ketten 11

Beispiele: Irrfahrten

1. Irrfahrt auf Menge {1,...,N}Beginn in 2Bewegung entsprechend Münzwurf-Ergebnis nach rechtsoder links für 1 und N Zusatzregel(z.B. zurück zumStart)

2. Irrfahrt auf {0,...,999} Beginn bei 0Bewegung aus i nach 2i+i‘mod 1000 i‘ wird durch werfen eines Würfels ermittelt

3. 4 mal Münze werfen Kopfanzahl=Startposition einer Irrfahrt auf {0,...,999}Bewegung entsprechend Münzwurfergebnis von i nachi+1mod1000 bzw. i-1mod1000

28.01.04 Ariane Wietschke - Markov-Ketten 12

- vorgegebene endliche Menge möglicher Positionen

- deterministisches oder zufälliges Verfahren zurBestimmung der Startposition

- jeder Position wird zufällig Folgeposition zugeordnet

Gemeinsamkeiten

28.01.04 Ariane Wietschke - Markov-Ketten 13

Definition: endliche Markov-Kette

Stochastischer Prozess bestehend aus:

- nichtleerer endlicher Menge S={1,2,...,N} (Zustandsraum)

- Vektor pi Wahrscheinlichkeit dafür, im Zustand zu starten(Anlaufvektor)

- Matrix Pij Wahrscheinlichkeit dafür, vom Zustand in einemSchritt in Folgezustand überzugehen (stochastischeMatrix

28.01.04 Ariane Wietschke - Markov-Ketten 14

Definition: stochastischer Prozess

- bezeichnet Folge von Zufallsexperimenten, die durchFunktion X(t) mit t ∈ T beschrieben werden kann

- X(t0) Wert der Zufallsvariable zumZeitpunkt t0

T Parameterraum

M = {X(t) | t ∈T} Zustandsraum

28.01.04 Ariane Wietschke - Markov-Ketten 15

Markov-Kette ist stochastischer Prozess, dessen zukünftige Zustände vom momentanen Zustand abhängen (Gedächtnislosigkeit des Prozesses)

Markov-Eigenschaft

Markov-Prozess 1.Ordnung: genau der vorherige Zeitpunkt ist entscheidend

Markov-Prozess 2.Ordnung: mehr Vergangenheit wird berücksichtigt (erweiterteMarkov-Eigenschaft

28.01.04 Ariane Wietschke - Markov-Ketten 16

1. Herleitung der Definition

2. Komponenten von Markov-Ketten3. Arten von Markov-Ketten

4. Anwendungsgebiete

5. To take home

28.01.04 Ariane Wietschke - Markov-Ketten 17

Beispiel

- Käfer kriecht durch Wegenetz→entscheidet sich an jeder Weggabelung zufällig für

einen Weg in Pfeilrichtung→darf nicht stehen bleiben

28.01.04 Ariane Wietschke - Markov-Ketten 18

Bestimmung des Zustandsraums

Welche Elemente enthält der Zustandsraum M?

- Zustände sind die 4Knotenpunkte

→ M = {e1, e2, e3, e4}

Zustände müssen unabhängig sein→Käfer kann sich nur an einem Knotenpunkt befinden

28.01.04 Ariane Wietschke - Markov-Ketten 19

Bestimmung der Übergangsmatrix

- Übergangsmatrix P ist stochastisch

→Elemente der Matrix zwischen null und eins: pik ∈ [0;1] 0≤pik≤1

→Summe der Elemente einer Zeile ist eins:

Allgemein hat Übergangsmatrix die Form:

28.01.04 Ariane Wietschke - Markov-Ketten 20

Bestimmung der Übergangsmatrix

28.01.04 Ariane Wietschke - Markov-Ketten 21

Mehrstufige Übergänge

- Übergang von ei nach ek in n Schritten→n-stufige Übergangswahrscheinlichkeit

Beispiel: Pfadregel: P14(3)=e1*e2*e3*e4+e1*e2*e4*e4+e1*e3*e4*e4):

28.01.04 Ariane Wietschke - Markov-Ketten 22

Bestimmen der Übergangsmatrix

P(n) = Pn

Elemente der Matrix→Summe der Wahrscheinlichkeiten aller Pfade die Übergang von ei nach ek in n Schritten ermöglichen

P(3) = P3= P * P 2

28.01.04 Ariane Wietschke - Markov-Ketten 23

Bestimmung des Anlaufvektors

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

Beispiel: zufällige Anfangsverteilung: =( , , , )

Wenn der Käfer in e1 starten soll: =(1,0,0,0)

28.01.04 Ariane Wietschke - Markov-Ketten 24

Wahrscheinlichkeitsverteilung zum Zeitpunkt n

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

= * Pn

= *P3

= * =

28.01.04 Ariane Wietschke - Markov-Ketten 25

1. Herleitung der Definition

2. Komponenten von Markov-Ketten

3. Arten von Markov-Ketten4. Anwendungsgebiete

5. To take home

28.01.04 Ariane Wietschke - Markov-Ketten 26

Arten von Markov-Ketten

Homogene Markov-Kette: Übergangswahrscheinlichkeiten zeitunabhängigpik =P(ek(n) | ei(n-1))

Absorbierende Markov-Kette: ∃ Zustand, der nicht mehr verlassen werden kannpii = 1

Irreduzible Markov-Kette: alle Zustände gegenseitig erreichbarpik(n) > 0

28.01.04 Ariane Wietschke - Markov-Ketten 27

1. Herleitung der Definition

2. Komponenten von Markov-Ketten

3. Arten von Markov-Ketten

4. Anwendungsgebiete5. To take home

28.01.04 Ariane Wietschke - Markov-Ketten 28

Anwendung

Biologie:- Ausbreitung von Arten und Wechselwirkungen.- Sequenzberechnung in DNS-Molekülen - Wettervorhersage

Physik:- Bewegung von Staubteilchen in der Luft(Brownsche Bewegung).

Informatik:- Analyse von Computer-Netzwerken Spracherkennung

28.01.04 Ariane Wietschke - Markov-Ketten 29

Qualitäts- und Sicherheitstechnik: Verfügbarkeit undSicherheit vontechnischen Systemen

Soziologie:- Beschreibung von sozialen Netzwerken und- sozialem Verhalten- Umzugsbewegungen

Wirtschaft:- Dynamik von Börsenkursen undBranchenindizes

Anwendung

28.01.04 Ariane Wietschke - Markov-Ketten 30

Logistik:- Analyse von Warteschlangen und- Verkehrsnetzwerken - Personalplanung

Anwendung

28.01.04 Ariane Wietschke - Markov-Ketten 31

1. Herleitung der Definition

2. Komponenten von Markov-Ketten

3. Arten von Markov-Ketten

4. Anwendungsgebiete

5. To take home

28.01.04 Ariane Wietschke - Markov-Ketten 32

- Stochastischer Prozess bestehend aus: Zustandsraum,Anlaufvektor,Übergangsmatrix

- Markov-Eigenschaft: zukünftige Zustände vom momentanen Zustand abhängig

- vielseitige Anwendung in Biologie, Informatik, Wirtschaft etc.

To take home