Das Palio von Siena Auf der Piazza del Campo, einem der schönsten Plätze Italiens, findet zweimal im Jahr eines der ursprünglichsten und malerischsten

Das Palio von Siena

Auf der Piazza del Campo, einem der schönsten Plätze Italiens, findet zweimal im Jahr eines der ursprünglichsten und malerischsten Volksfeste

statt: das Palio.

Es wird ausgetragen zwischen Reitern aus zehn der siebzehn Stadtbezirke (Contraden)

Sienas.

Wie kann man bestimmen, welcher Stadtteil am Rennen teilnehmen darf ?

Möglichkeit:

Zu jedem Rennen wird gelost.

Die Wahrscheinlichkeit am Rennen teilzunehmen beträgt dann 10/17.

Tatsächlich erfolgt die Auswahl daher nach folgendem Prinzip:

Hat eine Contrade an einem Rennen nicht teilgenommen, darf sie beim Folgerennen

auf jedem Fall teilnehmen.

Problem: Wenn eine Contrade Pech hat, kann sie über Jahre

hinaus nicht am Rennen teilnehmen.

Die verbleibenden drei Plätze werden unter den verbleibenden zehn Contraden verlost.

Die Wahrscheinlichkeit an Rennen teilzunehmen beträgt dann ???

Markoff Ketten

Darstellung Vektorschreibweise

Übergänge zwischen den Rennen

Übergänge: Matrix – Vektor Schreibweise

Beispielaufgabe a)

Darstellung der Übergänge

Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)

Begriffe/ Definitionen

Sätze

Auf zu Derive!!

C:\Programme\DfW5\Dfw.exe

Das Palio von SienaAuswahlprinzip:




Nicht so leicht zu beantworten, denn die Wahrscheinlichkeit für die Teilnahme hängt von den Voraussetzungen beim vorhergehenden

Rennen ab.

Dies ist ein zentrales Merkmal von Markoff – Ketten:

Die Wahrscheinlichkeitsverteilung auf einer Stufe ist abhängig von den Voraussetzungen bei der

vorhergehenden Stufe.

Zurück zum Problem !!!

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!






Hat eine Contrade also beim aktuellen Rennen nicht

teilgenommen, beträgt die Wahrscheinlichkeit beim nächsten

Rennen teilzunehmen 100 %

Hat eine Contrade beim aktuellen Rennen teilgenommen, beträgt die Wahrscheinlichkeit beim nächsten Rennen teilzunehmen 3/10 = 30 %

Die Wahrscheinlichkeiten für die Teilnahme lassen sich als Vektor notieren:

(T: Teilnahmewahrscheinlichkeit; Wahrscheinlichkeit der Nichtteilnahme) :T

Darstellungsmöglichkeit:

T

T

1

0

0

1

0

1

0,7

0,3


Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!






Hat eine Contrade also beim aktuellen Rennen nicht

teilgenommen, beträgt die Wahrscheinlichkeit beim nächsten

Rennen teilzunehmen 100 %

Hat eine Contrade beim aktuellen Rennen teilgenommen, beträgt die Wahrscheinlichkeit beim nächsten Rennen teilzunehmen 3/10 = 30 %

1

0

0

1

0

1

0,7

0,3


Wenn eine Contrade am aktuellen Rennen teilgenommen hat, wie groß ist die Wahrscheinlichkeit, beim überübernächsten (dritten) Rennen teilzunehmen ?

Wie groß ist die Wahrscheinlichkeit der Teilnahme bei diesem Verfahren ‚auf lange Sicht‘ (Beim Auslosen betrug sie ja 10/17!) ?

Fragestellungen:

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


Hierzu zunächst eine formale Vorgehensweise zur Notierung der Übergänge zwischen Teilnahme und Nichtteilnahme:

Auswahlprinzip:




T T

1

0

0,7

0,3

Eine derartige Darstellung nennt man: Gerichteter Graph

Die Übergänge lassen sich jedoch auch als Matrix notieren:

T T

T

T 0,7 0

10,3

Eine derartige Darstellung nennt man: Übergangsmatrix

Damit zunächst zurück zur ersten Fragestellung:

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


Wenn eine Contrade am aktuellen Rennen teilgenommen hat, wie groß ist die Wahrscheinlichkeit, beim überübernächsten (dritten) Rennen

teilzunehmen ?

Zur Erinnerung:

Aktuelles Rennen

1. Folgerennen 2. Folgerennen 3. Folgerennen

0

1

0,7

0,3 0,79

Für das 2. Folgerennen ergibt sich:

Teilnahmewahrscheinlichkeit im 1. Rennen: 0,3 führt zur Teilnahmewahrscheinlichkeit im zweiten Rennen von 0,3·0,3 = 0,09

Wahrscheinlichkeit für die Nichtteilnahme im 1. Rennen: 0,7 führt zur Teilnahmewahrscheinlichkeit im zweiten Rennen von 1·0,7 = 0,7

Insgesamt erhält man: Teilnahmewahrscheinlichkeit im 2. Folgerennen:

0,3·0,3 + 1·0,7 = 0,79

T

T T TT

T

0,3

10,3

0,7

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



teilzunehmen ?

Zur Erinnerung:

Aktuelles Rennen


0

1

0,7

0,3

0,21

0,79

0,7·0,3 + 0·0,7 = 0,21

Automatisch erhält man für die Wahrscheinlichkeit des Gegenereignisses (Nichtteilnahme) den Wert 0,21

Man mache sich klar, dass man ihn auch durch folgende Rechnung erhält:

T

T T TT

T

0,3

00,7

0,7

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



teilzunehmen ?

Zur Erinnerung:

Aktuelles Rennen


0

1

0,7

0,3 0,447

0,21

0,79

Nun zum dritten Folgerennen:

Teilnahmewahrscheinlichkeit im 2. Rennen: 0,79 führt zur Teilnahmewahrscheinlichkeit im dritten Rennen von 0,3·0,79 = 0,237

Wahrscheinlichkeit für die Nichtteilnahme im 2. Rennen: 0,21 führt zur Teilnahmewahrscheinlichkeit im dritten Rennen von 1·0,21 = 0,21

Insgesamt erhält man als Teilnahmewahrscheinlichkeit im 2. Folgerennen:

0,3·0,79 + 1·0,21 = 0,447

T

T T TT

T

0,79

00,7

0,21

10,3

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



teilzunehmen ?

Zur Erinnerung:

Aktuelles Rennen


0

1

0,7

0,3

0,21

0,79

T

T T TT

T

0,79

00,7

0,21

10,3

Wie groß ist die Wahrscheinlichkeit der Nichtteilnahme ?

0,7·0,79

Richtig !!

+ 0·0,21 = 0,553

0,447

0,553

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



teilzunehmen ?

Zur Erinnerung:

Aktuelles Rennen

1. Folgerennen 2. Folgerennen

0

1

0,7

0,3

0,21

0,79

Wie erhält man aus der Verteilung eines Rennens die Verteilung des Folgerennens ?

qn

pn

qn+1

pn+1

pn+1 = 0,3·pn+1·qn

qn+1 = 0,7·pn+0·qn

0,447

0,553

3. Folgerennen

? T

T T TT

T

pn

00,7

qn

10,3

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



teilzunehmen ?

Zur Erinnerung:

Aktuelles Rennen

1. Folgerennen 2. Folgerennen

0

1

0,7

0,3

0,21

0,79

Wie erhält man aus der Verteilung eines Rennens die Verteilung des Folgerennens ?

0,447

0,553

3. Folgerennen

? T

T T TT

T

pn

00,7

qn

10,3

qn+1

pn+1

0,7·pn+0·qn

0,3·pn+1·qn=

qn

pn

qn+1

pn+1

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


qn

qn

Notiert man sich hierzu die eingangs erwähnten Matrix- und Vektorschreibweisen unseres Problems:

Übergangs-matrix

Vertei-lungs-vektor

pn

qn

so lässt sich erkennen, dass man den Übergang vom einen zum nächsten Jahr durch die Multiplikation des ‚Verteilungsvektors‘ mit der Übergangsmatrix erhalten kann.

. =0,3. pn+ 1 .

0,7. pn+ 0 .0,7 0

10,3

T

T

T

T

Betrachten wir vor diesem Hintergrund Verteilungsvektoren für die verschiedenen Jahre...

qn+1

pn+1

0,7·pn+0·qn

0,3·pn+1·qn=

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


Aktuelles Rennen


0

1

0,7

0,3

0,553

0,447

0,21

0,79

...und nutzen ‚Derive‘ als Hilfsmittel zur Bestimmung der Vektoren:

Auf zu Derive !!

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



Durch das Herumexperimentieren mit Derive kann man verschiedene Dinge entdecken, die mathematisch

interessant sind:

Die Verteilung scheint sich mit fortschreitender Stufenzahl einer Grenzverteilung anzunähern.

Potenzierung der Matrix ändert die Koeffizienten so, dass in jeder Spalte das Gleiche, nämlich der Grenzvektor steht.

Die Grenzverteilung ist stationär, d.h. Multiplikation mit der Übergangsmatrix verändert sie nicht mehr

Die Grenzverteilung stellt sich unabhängig vom Startvektor ein.

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


Gesucht ist die Grenzverteilung !!

Nach obigen Aussagen könnte sie mit der stationären Verteilung übereinstimmen.

b

a


interessant sind:



Nutzen wir die ersten beiden Erkenntnisse, um den zweiten Teil der Fragestellung anzugehen:

Wie groß ist die Wahrscheinlichkeit der Teilnahme beim Rennen auf lange Sicht ?

Es muss also gelten:

0,7 0

10,3

=a

b

a

b

mit a+b=1,also

b = 1-a

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



interessant sind:



Es muss also gelten:

0,7 0

10,3

=a a

Auf zu Derive!!

Diese(s) Gleichung(ssystem) lösen wir mit Derive

1-a 1-a

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



In einer Fußgängerzone gibt es zwei Eisdielen, die sich um die Gunst der Kunden streiten. Durch die Auswahl neuer Rezepturen kommt es zu folgenden

Kundenwanderungen:

80 % der Kunden, die heute bei A kaufen, kaufen auch am nächsten Tag bei A, während 70 % der Kunden von B am nächsten Tag bei A einkaufen.

Wir vertiefen die bisherigen Erkenntnisse anhand einer ‚typischen‘ Aufgabe:

a) Zeichne einen gerichteten Graphen und gibt die Übergangsmatrix für einen Wechsel an. 0,7

0,3

0,2

0,8 A B

0,2 0,3

0,70,8

A B

A

B

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


0,2 0,3

0,70,8


Kundenwanderungen:


b) Bestimme den Anteil der Kunden für die beiden Verkaufsstellen A und B nach einem Tag bzw. nach drei Tagen, wenn man davon ausgehen kann, dass die Übergangswahrscheinlichkeiten konstant bleiben und am Anfang bei A 60 %, bei B 40 % ihr Eis kauften.

Übergangs- matrix

Ausgangs-verteilung

0,6

0,4=

Anteile nach einem Tag:

3

Anteile nach drei Tagen:

Auf zu Derive!!

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!




Kundenwanderungen:


c) Wie wird die durchschnittliche Verteilung der Kunden nach sehr vielen Tagen sein, wenn man von der Konstanz der Übergangswahrscheinlichkeiten ausgeht ?

Idee: Test mit Derive für großes n !!

Gesucht ist also :

nlim

n

0,2 0,3

0,70,8 0,6

0,4

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



Kundenwanderungen:


c) Wie wird die durchschnittliche Verteilung der Kunden nach sehr vielen Tagen sein, wenn man von der Konstanz der Übergangswahrscheinlichkeiten ausgeht ?

Aber: Geht es auch rechnerisch ??Die Grenzverteilung stimmt einem Satz zufolge mit der

stationären Verteilung überein !!

Ansatz daher: Gesucht ist ein Vektor , für den gilt:

b

a

0,2 0,3

0,70,8

=a

b

a

b

Auf zu Derive!!

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



a

A B

A

B

?

0,2

0,8


Kundenwanderungen:


d) Wie groß müsste die Übergangswahrscheinlichkeit p' = P(B A) für die Wechsler von B nach A nach einem Tag sein, wenn auch auf lange Sicht 40 % der Kunden bei A einkaufen sollen und das Wechselverhalten der Kunden von A gleich bleibt.

0,4

0,6

Überlegung:

Folgende Verteilung soll stationär sein.

Gesucht: Wechselwahrscheinlich-

keit von B zu A

1-a

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



Kundenwanderungen:


d) Wie groß müsste die Übergangswahrscheinlichkeit p' = P(B A) für die Wechsler von B nach A nach einem Tag sein, wenn auch auf lange Sicht 40 % der Kunden bei A einkaufen sollen und das Wechselverhalten der Kunden von A gleich bleibt.

Demnach muss gelten:

a 0,4

0,60,2 1-a

0,8=

0,4

0,6

Auf zu Derive!!

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!



Lösungen:

a) s.o.

b) 0,76

0,24

0,7776

0,2224

c) a= 7/9; b= 2/9

d) a= 2/15; b= 13/15

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


Begriffe/ Definitionen:

Definition: Stochastischer Vektor/ Stochastische Matrix

Definition: Markoff - Kette

Gegeben sei ein stochastischer Prozess (bei uns z.B. die Teilnahmewahrscheinlichkeit für alle zukünftigen Rennen) X = Xn (n aus IN) wobei Xn

jeweils eine Zufallsvariable über einem endlichen Zustandsraum Z = {x1,....xk} ist. Dieser stochastische Prozess heißt Markoff – Kette, wenn die Wahrscheinlichkeiten

P(Xn+1=xj) für alle j = 1,...,k und alle n aus IN nur vom Zustand zum Zeitpunkt n abhängt.

Anmerkung: Bernoullie – Versuch: Hier ist jede Stufe eines mehrstufigen Zufallsversuches unabhängig von einer anderen (z.B. bei fünfmaligem

Münzwurf), während bei Markoffketten die Wahrscheinlichkeit vom unmittelbar vorhergegangenen Zustand abhängt (jedoch nicht von weiter

zurückliegenden).

Eine Matrix/ ein Vektor heißt stochastisch, wenn die Spaltensumme jeweils 1 beträgt.

Grenzmatrix: Existiert die Matrix G = einer Matrix A, so nennt man sie Grenzmatrix (Anm.: Die Grenzmatrix existiert, wenn die Elemente der Übergangsmatrix positiv sind).

n

nAlim

Grenzvektor: Den Vektor nennt man Grenzvektor 0

n

ng v·Alimv

Stationäre Verteilung: Eine Verteilung (ein Vektor) heißt stationär, wenn gilt v

vv·A

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


Sätze

Wenn eine Grenzmatrix existiert, konvergiert die Folge der Zustandsvektoren zu einem eindeutig bestimmten Grenzvektor unabhängig von der Anfangsverteilung

Die Grenzmatrix besteht aus identischen Spaltenvektoren, bzw. alle Zeilen bestehen aus den jeweils gleichen Zahlen.

Existiert eine Grenzmatrix, so gibt es genau eine stationäre Verteilung (Fixvektor) und diese ist gleich der Grenzverteilung

Markoff Ketten




Beispielaufgabe a)


Das Palio von Siena

Beispielaufgabe b)

Beispielaufgabe c)

Beispielaufgabe d)


Sätze

Auf zu Derive!!


Documents

Das Palio von Siena Auf der Piazza del Campo, einem der schönsten Plätze Italiens, findet zweimal im Jahr eines der ursprünglichsten und malerischsten