Irrfahrten und Phanomene des Zufalls

von

Dipl.-math. oec. Bruno Ebner

Inhaltsverzeichnis

1 Einfuhrung 31.1 Zufallsexperiment, Ergebnismenge und Wahrscheinlichkeit . . . . . . . . . . 31.2 Irrfahrten 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 Symmetrische Irrfahrt auf einem Zahlenstrahl . . . . . . . . . . . . . 61.3 Zufallsvariable und Erwartungswert . . . . . . . . . . . . . . . . . . . . . . 9

2 Irrfahrten 2 112.1 Erwartete Anzahl an Schritten bis zur Absorption . . . . . . . . . . . . . . 11

2.1.1 Weitere symmetrische Irrfahrten . . . . . . . . . . . . . . . . . . . . 122.1.2 Der Binomialkoeffizient . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Pfade von Irrfahrten und das Reflektionsprinzip . . . . . . . . . . . . . . . . 13

3 Irrfahrten in Z2 193.1 Harmonische Funktionen in Z2 . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Losung bestimmen uber lineare Gleichungssysteme . . . . . . . . . . . . . . 213.3 Losung approximieren uber Monte-Carlo-Methode . . . . . . . . . . . . . . 223.4 Irrfahrten auf dem Zahlengitter in der Ebene ohne Schranken . . . . . . . . 223.5 Das Banach’sche Streichholzproblem . . . . . . . . . . . . . . . . . . . . . . 233.6 Bernoulli und Tennis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.7 Abschließende Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Literaturverzeichnis 28

1

Abbildungsverzeichnis

1.1 Symmetrische Irrfahrt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.1 Pfad einer symmetrischen Irrfahrt . . . . . . . . . . . . . . . . . . . . . . . 132.6 Joseph L. F. Bertrand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Pfade von Irrfahrten mit n = 50 (links) und n = 100 (rechts) Schritten. . . 172.3 Pfade von Irrfahrten mit n = 500 (links) und n = 1000 (rechts) Schritten. . 172.4 Pfade von Irrfahrten mit n = 10000 (links) und n = 50000 (rechts) Schritten. 172.5 Reflektionsprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1 Zahlengitter S der Irrfahrt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2 Ein Pfad einer Irrfahrt in der Ebene mit n = 10000 Schritten. . . . . . . . . 223.3 Irrfahrt im Zahlengitter S mit eingezeichneter Schranke B . . . . . . . . . . 243.4 Zahlengitter S mit eingezeichneten Schranken B . . . . . . . . . . . . . . . 26

2

Kapitel 1

Einfuhrung

Zu Beginn machen wir uns mit einigen wahrscheinlichkeitstheoretischen Grundlagen ver-traut.

1.1 Zufallsexperiment, Ergebnismenge und Wahrscheinlich-keit

Ein stochastischer Vorgang heißt ideales Zufallsexperiment, wenn folgende Gegebenheitenvorliegen:

• Das Experiment wird unter vorher genau festgelegten Bedingungen (Versuchsbedin-gungen) durchgefuhrt.

• Die Menge der moglichen Ergebnisse ist vor der Durchfuhrung des Experimentsbekannt.

• Das Experiment kann prinzipiell beliebig oft wiederholt werden.

Beispiel 1.1.1 Der einfache Wurfelwurf eines fairen sechsseitigen Wurfels ist ein idealesZufallsexperiment, da er beliebig oft wiederholt werden kann und alle moglichen Ergebnissedurch die erzielten Augenzahlen bekannt sind.

Die Menge der moglichen Ergebnisse eines idealen Zufallsexperiments bezeichnen wir mitΩ und nennen sie Ergebnismenge oder auch Grundraum. Die in der Ergebnismenge auf-gefuhrten Elemente mussen nicht notwendig auch als Resultate eines Zufallsexperimentsauftreten konnen. Wichtig fur das Folgende ist nur, dass die Ergebnismenge Ω alle mogli-chen Ergebnisse enthalt. Die Elemente von Ω werden mit ω, ω1, ω2, . . . oder anderen kleinengriechischen Buchstaben bezeichnet. Sie reprasentieren die moglichen Ergebnisse des Zu-fallsexperiments.

3

Beispiel 1.1.2 Die Ergebnismenge eines einfachen Wurfelwurfs ware konkret

Ω = 1, 2, 3, 4, 5, 6.

Wirft man den Wurfel einmal und es erscheint die 2, so ist ω = 2 ∈ Ω das Ergebnis desidealen Zufallsexperiments.

Ist Ω die Ergebnismenge eines Zufallsexperiments, so nennt man die Teilmengen A ⊂ ΩEreignisse. Beobachtet man bei der Durchfuhrung des Zufallsexperiments das Ergebnisω ∈ Ω, so ist das Ereignis A ⊂ Ω eingetreten, falls ω ∈ A gilt. Falls dagegen ω 6∈ A gilt, soist das Ereignis A bei der Durchfuhrung des Zufallsexperiments nicht eingetreten.

Beispiel 1.1.3 Interessiert in unserem Beispiel des einfachen Wurfelwurfs nur, ob dieAugenzahl gerade ist, so kann man das Ereignis wie folgt modellieren

A = 2, 4, 6.

Das Ereignis A tritt also ein, falls eine gerade Augenzahl gewurfelt wird.

Sind A,B zwei Ereignisse so ist der Durchschnitt

A ∩B := ω ∈ Ω : ω ∈ A und ω ∈ B

und die VereinigungA ∪B := ω ∈ Ω : ω ∈ A oder ω ∈ B

ein neues Ereignis.

Beispiel 1.1.4 Nehmen wir zu dem letzten Beispiel das Ereignis B der Augenzahlen klei-ner gleich drei hinzu, also

B := 1, 2, 3,so ist der Durchschnitt

A ∩B = 2, 4, 6 ∩ 1, 2, 3 = 2und die Vereinigung

A ∪B = 2, 4, 6 ∪ 1, 2, 3 = 1, 2, 3, 4, 6.

Also ist das Ereignis A ∩ B das Ereignis eine 2 zu wurfeln und das Ereignis A ∪ B eineder Augenzahlen ausser der 5 zu wurfeln.

Wir wollen im Folgenden von Wahrscheinlichkeiten reden. Dafur benotigen wir eine kon-krete Definition des Begriffs Wahrscheinlichkeit.

4

Definition 1.1.5

Ein endlicher Wahrscheinlichkeitsraum ist ein Paar (Ω, P ), wobei Ω eine Ergebnismen-ge und P eine auf den Teilmengen von Ω definierte reellwertige Funktion mit folgendenEigenschaften ist:

a) P (A) ≥ 0 fur A ⊂ Ω,

b) P (Ω) = 1,

c) P (A ∪B) = P (A) + P (B), falls A ∩B = ∅.P heißt Wahrscheinlichkeitsverteilung auf Ω. P (A) heißt die Wahrscheinlichkeit des Er-eignisses A.

Es gibt zahlreiche Zufallsexperimente mit endlich vielen Ausgangen, bei denen wir keinenAusgang vor dem anderen als wahrscheinlicher oder unwahrscheinlicher ansehen. In un-serem Beispiel des Wurfelwurfs wurden wir bei einem exakt gefertigten Wurfel alle dersechs Augenzahlen als gleich wahrscheinlich erachten. Bezeichnen wir mit |A| die Anzahlaller moglichen Ergebnisse des Ereignisses A, so konnen wir durch

P (A) =|A||Ω| fur A ⊂ Ω,

eine Wahrscheinlichkeitsverteilung angeben. In diesem Fall heißt der Wahrscheinlichkeits-raum (Ω, P ) Laplacescher Wahrscheinlichkeitsraum.

Beispiel 1.1.6 Fur unseren einfachen Wurfelwurf gilt dann mit dem oben definiertenEreignis A

P (A) =|A||Ω| =

|2, 4, 6||1, 2, 3, 4, 5, 6| =

36

=12.

Da wir im Folgenden die bedingten Wahrscheinlichkeiten benotigen fuhren wir sie hierkurz ein.

Definition 1.1.7

Es seien (Ω, P ) ein endlicher Wahrscheinlichkeitsraum und A,B ⊂ Ω mit P (B) > 0.Dann heißt

P (A|B) :=P (A ∩B)

P (B)die bedingte Wahrscheinlichkeit von A unter der Bedingung B.

Beispiel 1.1.8 In unserem Beispiel ware also wegen |A ∩B| = 1 und |B| = 3 und

P (A ∩B) =|A ∩B||Ω| =

16

und P (B) =|B||Ω| =

12

5

die bedingte Wahrscheinlichkeit von A unter der Bedingung B gegeben durch

P (A|B) =P (A ∩B)

P (B)=

1612

=13.

1.2 Irrfahrten 1

1.2.1 Symmetrische Irrfahrt auf einem Zahlenstrahl

Ein Teilchen befindet sich zum Zeitpunkt 0 im Punkt x0 = 0 auf der x-Achse. Zu denZeitpunkten t = 1, 2, . . . wandert das Teilchen entweder einen Schritt nach links (x1 = −1)oder einen Schritt nach rechts (x1 = 1) mit derselben Wahrscheinlichkeit 1

2 . Die Irrfahrtendet, falls das Teilchen eine der vorher festgelegten Schranken −a oder b erreicht, a, b ∈ N.Wir sprechen hier auch von der Absorption des Teilchens.

-¾-¾

0-1 1−a b

Abbildung 1.1: Symmetrische Irrfahrt

Ohne Beschrankung der Allgemeinheit setzen wir die linke Schranke auf 0, den Startpunktverschieben wir auf a und die rechte Schranke auf n = b+a. Dann bezeichnen wir mit p(x)fur x = 1, . . . , n die Wahrscheinlichkeit im Punkt n absorbiert zu werden, falls das Teilchensich gerade im Punkt x befindet. Die Funktion p(x) hat die folgenden Eigenschaften:

a) p(0) = 0,

b) p(n) = 1,

c) p(x) = 12p(x− 1) + 1

2p(x + 1) fur x = 1, 2, . . . , n− 1.

Die Eigenschaft a) folgt direkt aus der Definition der Funktion p da das Teilchen in 0absorbiert wurde und nicht mehr nach n kommen kann. Die Wahrscheinlichkeit in n ab-sobiert zu werden falls das Teilchen sich in n befindet ist naturlich 1 und so kommt dieEigenschaft b) zu stande. Die letzte Eigenschaft lasst sich durch folgende Uberlegung er-klaren: Falls das Teilchen sich im Punkt x befindet, x = 1, . . . , n − 1, so befindet es sichnach dem nachsten Schritt mit Wahrscheinlichkeit 1

2 im Punkt x − 1 (oder im Punktx + 1). Die Wahrscheinlichkeit dann in n absorbiert zu werden ist demzufolge p(x − 1)(bzw. p(x + 1)). Um die Regel nun korrekt zu erklaren benotigen wir eine grundlegendeTatsache uber bedingte Wahrscheinlichkeiten.

6

Theorem 1.2.1

Sei A ein Ereignis und B, C sich ausschließende Ereignisse (also falls B eintritt, so nichtC und umgekehrt, also B ∩ C = ∅ und B ∪ C = Ω). Dann gilt

P (A) = P (B)P (A|B) + P (C)P (A|C).

Beweis:Da B und C sich ausschließende Ereignisse sind, gilt

A = (A ∩B) ∪ (A ∩ C) und (A ∩B) ∩ (A ∩ C) = ∅.Damit folgt mit der Definition der bedingten Wahrscheinlichkeit und der Eigenschaft c)der Wahrscheinlichkeitsverteilung P

P (A) = P ((A ∩B) ∪ (A ∩ C)) = P (A ∩B) + P (A ∩ C) = P (B)P (A|B) + P (C)P (A|C).

¤Setzen wir nun die Uberlegung von oben in dieses Theorem ein, so folgt die Eigenschaftc) der Funktion p(x). Aber wie sieht nun die Funktion p(x) aus? Und endet eine solcheIrrfahrt immer, auch wenn wir das n sehr groß wahlen? Um Antworten auf diese Fragenzu geben, betrachten wir harmonische Funktionen.

Harmonische Funktionen

Wir losen uns nun erstmal von den Irrfahrten und betrachten allgemein Funktionen fur diedie Eigenschaft c) gilt. In diesem Sinne bezeichnen wir mit S = 0, 1, . . . , n die Menge dermoglichen Punkte auf dem Zahlenstrahl, mit D = 1, . . . , n− 1 ⊂ S die inneren Punkte,also die Menge S vermindert um die beiden Schranken, und mit B = 0, n die Menge derSchranken. Wir nennen eine Funktion f : S → R, x 7→ f(x) harmonisch, falls sie auf derMenge D der Eigenschaft c) genugt, also gilt

f(x) =12(f(x− 1) + f(x + 1)).

Gelten mit y1, y2 ∈ R die folgenden Bedingungen

f(0) = y1 und f(n) = y2

so nennen wir diese Randbedingungen. Also ist die Funktion p(x) eine harmonische Funk-tion mit den Randbedingungen p(0) = 0 und p(n) = 1. Das Problem eine harmonischeFunktion mit vorgegebenen Randbedingungen zu finden, wird auch das Dirichlet Problemgenannt. Wir werden im Folgenden beweisen, dass das Problem eine eindeutige Losungbesitzt.

Theorem 1.2.2 (Maximumsprinzip)Eine harmonische Funktion f(x) nimmt ihr Maximum M und ihr Minimum m am Randan.

7

Beweis:Sei M der großte Wert der Funktion f . Falls nun f(x) = M fur ein x ∈ D gilt, so gilt auchf(x− 1) = M = f(x + 1), da f(x) der Mittelwert dieser beiden Werte ist. Falls dies nunaber fur f(x− 1) gilt, so gilt auch nach demselben Argument f(x− 2) = M . Fuhrt mandies so fort, kommt man auf f(0) = M . Die gleiche Argumentation funktioniert auch furdas Minimum m. ¤

Theorem 1.2.3 (Eindeutigkeitsprinzip)Seien f(x) und g(x) harmonische Funktionen auf S mit f(0) = g(0) und f(n) = g(n).Dann gilt

f(x) = g(x), fur alle x ∈ S.

Beweis:Sei h(x) = f(x)− g(x). Dann gilt fur x ∈ D

12(h(x− 1) + h(x + 1)) =

12(f(x− 1)− g(x− 1) + f(x + 1)− g(x + 1))

=12(f(x− 1) + f(x + 1))− 1

2(g(x− 1) + g(x + 1))

= f(x)− g(x) = h(x),

da die Funktionen f(x) und g(x) nach Voraussetzung harmonisch sind. Also ist auch dieFunktion h(x) harmonisch und es gilt h(0) = 0 und h(n) = 0. Wegen dem Maximums-prinzip ist dann sowohl das Maximum als auch das Minimum der Funktion h(x) gleich 0.Also muss fur alle x ∈ S gelten h(x) = 0. Und somit stimmen die Funktionen f(x) undg(x) auf S uberein. ¤Mit Hilfe des Eindeutigkeitsprinzips konnen wir uns nun Gedanken um die Funktion p(x)aus dem vorherigen Abschnitt machen. Wir sehen, dass falls wir eine harmonische Funkti-on mit den in a) und b) vorgeschriebenen Randbedingungen finden, diese auch eindeutigist. Die einfachste Art unser Problem zu losen, ist einfach mal zu raten: Eine lineare Funk-tion, die unsere Randbedingung erfullt ist f(x) = x

n , da f(0) = 0 und f(n) = 1 gilt. Bleibtnoch die Eigenschaft c) zu prufen. Es gilt

12(f(x− 1) + f(x + 1)) =

x− 1 + x + 12n

=x

n= f(x).

Also haben wir eine harmonische Funktion mit den geforderten Randbedingungen gefun-den und wegen dem Eindeutigkeitsprinzip gibt es auch keine weitere.

Auch die zweite gestellte Frage, also die Frage nach der Endlichkeit einer solchen Irrfahrt,lasst sich mit Hilfe der harmonischen Funktionen leicht beantworten: Wir bezeichnen mitq(x) die Wahrscheinlichkeit, dass die Irrfahrt nie endet, falls das Teilchen sich am Punktx befindet, also die Schranken B nie erreicht werden. Dann folgt mit den gleichen Uber-legungen wie bei p(x), dass

q(x) =12q(x− 1) +

12q(x + 1)

8

gilt. Also ist q(x) eine harmonische Funktion und es gilt q(0) = q(n) = 0. Nun ist aberwegen dem Maximumsprinzip q(x) = 0 fur alle x ∈ S.

Interpretation als ”Penny Matching Game“

Man stelle sich folgende Situation vor: Peter hat a und Paul b faire Munzen mit den Sym-bolen Zahl (z) und Wappen (w). Sie schnippen jeweils eine ihrer Munzen auf den Boden, sodass sie flach aufliegen. Ist bei beiden Munzen das gleiche Symbol zu sehen, so gewinnt Pe-ter beide Munzen, sind unterschiedliche Symbole zu sehen, so gewinnt Paul beide Munzen.Das Spiel wird so lange gespielt bis einer von beiden keine Munze mehr hat (Absorption).Auch hier handelt es sich um eine symmetrische Irrfahrt. Die Wahrscheinlichkeit, dassPeter oder Paul eine Runde gewinnt, ist jeweils 1

2 , da folgende Kombinationen pro Wurfauftreten konnen:

(w, w), (z, z), (w, z), (z, w).Wenden wir das oben gezeigte auf unser Spiel an, so ist die Wahrscheinlichkeit, dass Peteralle Munzen von Paul gewinnt durch p(a) = a

n = aa+b gegeben. Respektive gewinnt Paul

alle Munzen mit der Wahrscheinlichkeit 1− p(a) = bb+a .

Beispiel 1.2.4 Peter hat a = 1 Munze und Paul b = 99 Munzen. Die Wahrscheinlichkeit,dass Peter das Spiel gewinnt, liegt bei p(1) = 0.01 = 1%.

1.3 Zufallsvariable und Erwartungswert

Zufallige Ereignisse werden meist mit Hilfe von Zufallsvariablen beschrieben. Darunterversteht man eine Variable, deren Wert vom Ergebnis eines Zufallsexperiments abhangt.

Definition 1.3.1

Ist Ω eine Ergebnismenge, so heißt jede Abbildung

X : Ω → R

von Ω in die Menge der reellen Zahlen eine Zufallsvariable (auf Ω).

Wir konnen eine Zufallsvariable X als eine Vorschrift ansehen, die jedem Ergebnis ω ∈ Ωdes idealen Zufallsexperimentes eine reelle Zahl X(ω) zuordnet. Der Wert X(ω) heißt auchRealisierung der Zufallsvariablen zum Ausgang ω.

Beispiel 1.3.2 Wir interessieren uns beim einfachen Wurfelwurf fur das Quadrat dergeworfenen Augenzahl, also setzen wir als Zufallsvariable

X(ω) = ω2, ω ∈ Ω.

Die Zufallsvariable nimmt also die Werte 1, 4, 9, 16, 25 und 36 an.

9

Ist Ω eine Ergebnismenge eines Zufallsexperiments und ist

X : Ω → R, ω 7→ X(ω),

eine Zufallsvariable, so interessiert man sich in der Praxis fur Ereignisse der Form

A = ω ∈ Ω : X(ω) = x ⊂ Ω, x ∈ R,

also fur das Ereignis, dass bei Durchfuhrung des Zufallsexperiments die Zufallsvariable Xeinen fest vorgegebenen Wert x ∈ R annimmt.

Beispiel 1.3.3 Interessieren wir uns zum Beispiel fur das Ereignis A so konnen wir diesesmit Hilfe der Zufallsvariablen X schreiben als

A = 2, 4, 6 = ω ∈ Ω : X(ω) = 4 ∪ ω ∈ Ω : X(ω) = 16 ∪ ω ∈ Ω : X(ω) = 36.

Wir betrachten allgemein fur ein s ∈ N die endliche Ergebnismenge Ω = ω1, . . . , ωs miteiner durch P (ωj) fur j = 1, . . . , s gegebenen Wahrscheinlichkeitsverteilung sowie X alsZufallsvariable auf Ω. Dann konnen wir den Erwartungswert einer Zufallsvariablen wiefolgt definieren.

Definition 1.3.4

Fur eine Zufallsvariable X : Ω → R auf einem endlichen Wahrscheinlichkeitsraum (Ω, P )heißt die Zahl

E(X) := X(ω1)P (ω1) + X(ω2)P (ω2) + · · ·+ X(ωs)P (ωs)der Erwartungswert von X.

Wir konnen E(X) als durschnittliche Auszahlung pro Spiel auf lange Sicht ansehen, wennwiederholt ein Gluckspiel mit den moglichen Ergebnissen ω ∈ Ω und einer durch dieZufallsvariable X festgelegten Auszahlungsfunktion gespielt wird.

Beispiel 1.3.5 Der Erwartungswert der Zufallsvariablen X aus Beispiel 1.3.2 ist wegenP (ω) = 1

6 fur alle ω ∈ Ω gegeben durch

E(X) = X(1)P (1) + X(2)P (2) + · · ·+ X(6)P (6)= 1P (1) + 4P (2) + · · ·+ 36P (6)=

16(1 + 4 + 9 + 16 + 25 + 36) =

916≈ 15.17.

Sind X, Y Zufallsvariablen auf Ω und a ∈ R, so hat der Erwartungswert folgende Eigen-schaften:

a) E(X + Y ) = E(X) + E(Y ),

b) E(aX) = aE(X).

10

Kapitel 2

Irrfahrten 2

2.1 Erwartete Anzahl an Schritten bis zur Absorption

Bei der in Abschnitt 1.2.1 eingefuhrten symmetrischen Irrfahrt auf dem Zahlenstrahl ha-ben wir gesehen, dass das Teilchen fruher oder spater immer absorbiert wird. Eine weiterenaturliche Frage stellt sich dann: Wie oft wird das Teilchen im Durchschnitt hin und herspringen bis es absorbiert wird? Dieser Frage wollen wir uns im Folgenden widmen.

Hierzu benotigen wir die gerade eingefuhrten Begriffe der Zufallsvariable und des Erwar-tungswertes. Wir bezeichnen mit

Nx := Anzahl der benotigten Schritte bis das Partikel absorbiert wird,

dabei steht der Index x = 0, . . . , n fur die Position des Teilchens. Von vornherein kennenwir zwei sichere Werte der Zufallsvariablen Nx

N0 = 0 und Nn = 0,

da in diesen Positionen das Teilchen bereits absorbiert wurde. Befindet sich das Teilchenin der Position x = 1, . . . , n − 1 so lauft es einen Schritt (nach links oder rechts, jeweilsmit Wahrscheinlichkeit 1

2) und kommt in den Positionen x−1 oder x+1 an. Von dort ausbraucht es aber noch Nx−1 bzw. Nx+1 Schritte bis es absorbiert wird. Also konnen wir dieZufallsvariable Nx schreiben als

Nx =

1 + Nx−1, mit Wahrscheinlichkeit 12 ,

1 + Nx+1, mit Wahrscheinlichkeit 12 .

Fur den Erwartungswert E(Nx) halt demzufolge fur x = 1, . . . , n − 1 die folgende Diffe-renzengleichung

E(Nx) = 1 +12E (Nx−1) +

12E (Nx+1) .

Die allgemeine Losung der Differenzengleichung1 ist gegeben durch

E(Nx) = −x2 + c1x + c2, c1, c2 ∈ R.

1Das Losen von Differenzengleichungen ist nicht Bestandteil des Schnupperkurses, weswegen in diesemFalle die Losung angegeben wird. Es handelt sich hier um eine lineare Differenzengleichung 2. Ordnung,welche mit Standardmethoden gelost werden kann.

11

Mit den beiden sicheren Werten N0 = Nn = 0 ergeben sich die Erwartungswerte E(N0) =E(Nn) = 0 und damit die Gleichungen

c2 = 0−n2 + c1n + c2 = 0.

Setzt man c2 = 0 in die zweite Gleichung ein, so folgt wegen n 6= 0

−n2 + c1n = 0 ⇐⇒ n(c1 − n) = 0 =⇒ c1 = n.

Eingesetzt ergibt dies den gesuchten Erwartungswert

E(Nx) = −x2 + nx.

Falls wir also in x = a starten ergibt sich mit n = a + b als erwartete Anzahl an Schrittenfur eine symmetrische Irrfahrt auf dem Zahlenstrahl mit absorbierenden Schranken in 0und b + a

E(Na) = −a2 + (a + b)a = ab.

Erwartete Anzahl an Munzwurfen bis zum Ruin

Wenden wir das eben berechnete auf die Situation des ”Penny Matching Games“an, soerhalten wir die verbluffende Antwort, dass selbst wenn Peter nur 1 Munze hat, das Spiel imMittel 99-mal gespielt wird, bis einer der Spieler ruiniert ist, obwohl die Wahrscheinlichkeit,dass es nach einem Spiel schon endet, bei 50% liegt.

2.1.1 Weitere symmetrische Irrfahrten

In der Situation von Abschnitt 1.2.1 setzen wir a = ∞ und b ∈ N so sprechen wir voneiner Irrfahrt mit nur einer absorbierenden Schranke. Auch hier stellt sich die Frage nachder Wahrscheinlichkeit der Absorption des Teilchens, da es ja prinzipiell in eine Richtungabdriften konnte (Ubungsaufgabe). Setzen wir auch b = ∞ so sprechen wir von einersymmetrischen Irrfahrt ohne Schranken, da das Teilchen nie absorbiert wird.

2.1.2 Der Binomialkoeffizient

In Kapitel 1 haben wir den Laplaceschen Wahrscheinlichkeitsraum eingefuhrt. Um diemoglichen Ergebnisse eines Ereignisses angeben zu konnen, sollten wir uns mit einigenzentralen Begriffen der Kombinatorik, der Lehre des Abzahlens, vertraut machen. Unterder Fakultat einer Zahl n ∈ N verstehen wir die Zahl

n! := n · (n− 1) · (n− 2) · · · 3 · 2 · 1.

Beispiel 2.1.1 Die Fakultat ist eine sehr schnell wachsende Vorschrift:

1! = 1, 2! = 2·1 = 2, 3! = 3·2·1 = 6, 4! = 4·3! = 24, 6! = 6·5·4! = 720 und 15! = 1307674368000.

12

Der Binomialkoeffizient ist fur n, k ∈ N mit k ≤ n definiert durch(

n

k

):=

n!k!(n− k)!

.

Eine direkte Interpretation des Binomialkoeffizienten ist die Anzahl aller moglichen Er-gebnisse, die man als zufallige Auswahl von genau k Elementen einer n elementigen Mengeohne Berucksichtigung der Reihenfolge treffen kann.

Beispiel 2.1.2 Beim Lotto 6 aus 49 wird aus einer Urne mit 49 Kugeln genau 6 heraus-genommen. Der Binomialkoeffizient liefert hierfur die Anzahl an moglichen verschiedenenZiehungen mit n = 49 und k = 6

(496

)=

49!6!(49− 6)!

=49 · 48 · · · 3 · 2 · 1

6! · 43 · 42 · · · 3 · 2 · 1=

49 · 48 · 47 · 46 · 45 · 446!

=10068347520

720= 13983816.

2.2 Pfade von Irrfahrten und das Reflektionsprinzip

Wir betrachten zunachst die Irrfahrt aus Abschnitt 1.2.1 und drehen diese um 90 Grad.Hinzu zeichnen wir eine Zeitachse beginnend im Ursprung (siehe Abbildung 2.1). Wirzeichnen den sogenannten Pfad einer Irrfahrt wie folgt ab: Wandert das Teilchen zumZeitpunkt t1 = 1 nach 1 so markieren wir dies mit einem Pfeil vom Punkt (0, 0) zum Punkt(1, 1). Wandert das Teilchen nach −1 so markieren wir dies mit einem Pfeil vom Punkt(0, 0) zum Punkt (1,−1). Dies wiederholen wir zu den Zeitpunkten t2, t3, . . . vom jeweiligenerreichten Punkt bis zur Absorption des Teilchens. Im Folgenden betrachten wir allgemein

-

6

0

−1

1

b

t1 2 3

µ

R

µ

µ

R

R

µ

µ

µ

Abbildung 2.1: Pfad einer symmetrischen Irrfahrt

Pfade von Irrfahrten und geben hierzu wie in Abschnitt 2.1.1 die Restriktion der Schrankenauf. Mathematisch gesehen kann man solch einen Pfad einer Irrfahrt als Realisierung von

13

n ∈ N Zufallsvariablen X1, . . . , Xn betrachten: Geht der Pfad zum Zeitpunkt t einenSchritt nach oben, so erhalt die Variable Xt den Wert 1, geht er einen Schritt nach unten,so erhalt die Variable den Wert −1. Bei einer symmetrischen Irrfahrt gilt also

P (Xk = 1) = P (Xk = −1) =12, fur k = 1, . . . , n.

Definieren wirSk := X1 + X2 + · · ·+ Xk

als Partialsummen der ersten k Zufallsvariablen, so konnen wir Sk als Gewinn (oder Ver-lust) zum Zeitpunkt k interpretieren. Es gilt

Sk − Sk−1 = Xk = ±1, S0 := 0, k = 1, . . . , n. (2.1)

Mit dieser Schreibweise kommen wir zur Definition eines Pfades einer Irrfahrt.

Definition 2.2.1

Seien n ∈ N und m ∈ Z. Ein Pfad S1, S2, . . . , Sn vom Punkt (0, 0) zum Punkt (n,m) isteine Linie (Polygonzug), die durch die Punkte (i, Si) fur i = 0, . . . , n geht und fur die dieBeziehung (2.1) mit Sn = m gilt.

Falls nun p der Zufallsvariablen X1, . . . , Xn positiv und q negativ sind, so ist

n = p + q und m = p− q.

Da nichts uber die genaue Zuordnung der Zufallsvariablen mit Wert 1 und mit Wert -1vorausgesetzt wurde, konnen diese laut Abschnitt 2.1.2 in

Nn,m =(

p + q

p

)=

(p + q

q

)

verschiedenen Kombinationen ausgewahlt werden.

Beispiel 2.2.2 Betrachten wir eine symmetrische Irrfahrt ohne Schranken und fragen unsnach der Anzahl der Pfade der Irrfahrt von (0, 0) nach (14, 4). Dann muss also

n = 14 = p + q und m = 4 = p− q

sein. Daraus folgt also p = 4 + q damit q = 5 und p = 9. Damit ergibt sich die Anzahl anmoglichen Pfaden

N14,4 =(

149

)=

14!9!(14− 9)!

= 14 · 13 · 11 = 2002.

14

In den folgenden Bildern werden einige konkrete Pfade von symmetrischen Irrfahrten ohneabsorbierende Schranken gezeigt. Die Bilder wurden mit dem Computer erzeugt und eswurden n = 50, 100, 500, 1000, 10000, 50000 Zufallsexperimente simuliert (siehe Abbildun-gen 2.2-2.4).Betrachten wir nun die Punkte A = (a, α) und B = (b, β) mit a, b, α, β ∈ N und b > a.Unter der Spiegelung des Punktes A an der Zeitachse verstehen wir den Punkt A′ =(a,−α). Unter einem Pfad von A nach B verstehen wir die Definition 2.2.1 mit A alsUrsprung (0, 0) (siehe Abbildung 2.5).

Theorem 2.2.3 (Reflektionsprinzip)Die Anzahl an Pfaden von A nach B, welche die Zeitachse beruhren oder uberquerenentspricht der Anzahl an Pfaden von A′ nach B.

Beweis:Wir betrachten einen Pfad von A nach B der die Zeitachse mindestens einmal beruhrtund spiegeln den Punkt A an der Zeitachse auf den Punkt A′. Nennen wir den erstenBeruhrungspunkt mit der Zeitachse T = (t, 0). Da der Pfad von A nach B die Zeitachsevor dem Punkt T nicht beruhrt, gibt es genauso viele Pfade von A nach T , welche dieZeitachse erst in T beruhren, wie von A′ nach T (Spiegelung). Und da danach die beidenPfade identisch nach B laufen, ist das Theorem bewiesen. ¤

Das Reflektionsprinzip lasst sich sehr vielfaltig in der Theorie

Abbildung 2.6: JosephL. F. Bertrand

der Irrfahrten einsetzen. Eine Anwendung findet sich in der vondem franzosischen Mathematiker Joseph Louis Francois Bert-rand 1887 vorgestellten Abstimmungsproblem: In einer Stich-wahl erhalt Kandidat P insgesamt p Stimmen und Kandidat Qerhalt q Stimmen mit p > q (also Kandidat P hat die Wahlgewonnen). Wie groß ist die Wahrscheinlichkeit, dass wahrendder Auszahlung der Stimmen Kandidat P immer mehr Stim-men hatte als Kandidat Q?

Wir gehen davon aus, dass die Stimmzettel nacheinander einergut gemsichten Wahlurne entnommen werden. Den entscheiden-den Hinweis fur die Antwort auf diese Frage liefert das folgendeTheorem.

Theorem 2.2.4

Seien n,m ∈ N mit n, m > 0 und m ≤ n. Die Anzahl der Pfade S1, S2, . . . , Sn mit Sn =m, also der Pfade vom Punkt (0, 0) zum Punkt (n,m), so dass S1 > 0, S2 > 0, . . . , Sn > 0gilt, ist genau m

n Nn,m.

15

Beweis:Da nach dem ersten Schritt S1 = ±1 ist, gilt nach der Voraussetzung S1 = 1. Alsosind die wirklich in Frage kommenden Pfade alle diejenigen, die vom Punkt (1, 1) zumPunkt (n,m) laufen, dabei aber die Zeitachse weder beruhren noch schneiden. Nach demReflektionsprinzip ist die Anzahl dieser Pfade gegeben durch

Nn−1,m−1 −Nn−1,m+1 =(

p + q − 1p− 1

)−

(p + q − 1

q − 1

)

=p− q

p + q

(p + q

p

)

=m

nNn,m

und damit ist das Theorem bewiesen. ¤Nun konnen wir mit Hilfe des eben bewiesenen Theorems die Frage von Herrn Bertrand be-antworten: Wir wissen, dass die Anzahl der Pfade von (0, 0) bis (n,m) welche die Zeitachsenie beruhren gleich m

n Nn,m ist. Also ist die gesuchte Wahrscheinlichkeit P gegeben durchdie Anzahl der Pfade welche die Zeitachse nie beruhren geteilt durch die anzahl aller Pfadevon (0, 0) bis (n,m):

P :=mn Nn,m

Nn,m=

m

n=

p− q

p + q.

Beachte: Alle Pfade sind gleich wahrscheinlich (Laplacescher Wahrscheinlichkeitsraum).

16

0 10 20 30 40 50

−3

−2

−1

01

23

4

0 20 40 60 80 100

−2

02

46

Abbildung 2.2: Pfade von Irrfahrten mit n = 50 (links) und n = 100 (rechts) Schritten.

0 100 200 300 400 500

010

2030

40

0 200 400 600 800 1000

−20

−10

010

20

Abbildung 2.3: Pfade von Irrfahrten mit n = 500 (links) und n = 1000 (rechts) Schritten.

0 2000 4000 6000 8000 10000

−60

−40

−20

020

4060

0 10000 20000 30000 40000 50000

−10

0−

500

5010

0

Abbildung 2.4: Pfade von Irrfahrten mit n = 10000 (links) und n = 50000 (rechts) Schrit-ten.

17

-

6

?

0

−1

1

t1 2 3

µ

R

µ

R

R

R

µ

µ

µ

Abbildung 2.5: Reflektionsprinzip

18

Kapitel 3

Irrfahrten in Z2

Wir betrachten in diesem Abschnitt Zahlengitter in Z2 := Z × Z = (x, y) : x, y ∈Z, also insbesondere eine Menge von Punkten (x, y) mit ganzzahligen Koordinaten x ∈. . . ,−2,−1, 0, 1, 2, . . . und y ∈ . . . ,−2,−1, 0, 1, 2, . . .. Wir bezeichnen mit S = D∪B ⊂Z2 eine Menge von Punkten, welche die folgenden Bedingungen erfullt:

a) Die Mengen D und B sind disjunkt, es gilt also B ∩D = ∅.b) Jeder Punkt in D hat alle vier Nachbarpunkte in S.

c) Jeder Punkt von B hat mindestens einen Nachbarpunkt in D.

d) Fur alle Punkte E, F ∈ S gilt: Es gibt eine Folge von Punkten P1, . . . , Pn ∈ D, sodass sie einen Weg von E nach F bilden (bzw. S ist zusammenhangend).

Wir nennen die Punkte aus der Menge D die inneren Punkte von S und die Punkte aus derMenge B die Randpunkte von S (vergleiche Abschnitt 1.2.1). Eine symmetrische Irrfahrtauf einem Zahlengitter S mit Schranken in B fuhren wir wie folgt ein: Befindet ein Teilchensich in einem Punkt (x, y) ∈ D so springt es jeweils mit Wahrscheinlichkeit 1

4 zu einemseiner Nachbarpunkte, in diesem Fall also (x + 1, y), (x − 1, y), (x, y + 1) oder (x, y − 1).Kommt es in einem Punkt (a, b) ∈ B an, so wird es absorbiert und die Irrfahrt endet.

Beispiel 3.0.5 Wir betrachten die Punktmengen

D = (0, 0), (1, 0), (2, 0), (1, 1), (2, 1)

undB = (−1, 0), (0,−1), (0, 1), (1, 2), (2, 2), (3, 0), (3, 1), (1,−1), (2,−1).

Graphisch kann man das Zahlengitter S = D∪B darstellen wie in Abbildung 3.1, wobei dieausgefullten Punkte aus der Menge der Randpunkte B und die nichtausgefullten Punkteaus der Menge der inneren Punkte D stammen.

19

-

6

¾0−1

−1

1

y

x1 2 3

Abbildung 3.1: Zahlengitter S der Irrfahrt

In der Situation von Beispiel 3.0.5 bezeichnen wir im Folgenden mit p(x) die Wahrschein-lichkeit in den Schranken

B1 := (−1, 0), (0,−1), (1, 0), (1, 2), (2, 2), (3, 1)

absorbiert zu werden. Weiter seien die inneren Punkte aus D lexikographisch durchnum-meriert, also

a = (0, 0), b = (1, 0), c = (2, 0), d = (1, 1), und e = (2, 1).

Damit gelten die folgenden Eigenschaften der Funktion p(x):

a) p(x) = 1 fur alle x ∈ B1 und p(x) = 0 fur alle x ∈ B \B1,

b) p(a) = 14p(b) + 3

4 ,

c) p(b) = 14p(a) + 1

4p(c) + 14p(d),

d) p(c) = 14p(b) + 1

4p(e),

e) p(d) = 14p(b) + 1

4p(e) + 12 , und

f) p(e) = 14p(c) + 1

4p(d) + 12 .

Es stellt sich wie schon in Abschnitt 1.2.1 die Frage, wie man die gesuchte Funktion p(x)bestimmen kann und ob diese, so wie wir sie definiert haben, eindeutig ist. Die Frage nachder Eindeutigkeit konnen wir wie auf dem Zahlenstrahl behandeln und fuhren hierfurharmonische Funktionen ein.

20

3.1 Harmonische Funktionen in Z2

Wie schon in Kapitel 1 nennen wir eine auf S definierte Funktion f : S → R, (x, y) 7→f(x, y) harmonisch, falls fur Punkte (x, y) ∈ D die Eigenschaft

f(x, y) =14(f(x + 1, y) + f(x− 1, y) + f(x, y + 1) + f(x, y − 1))

gilt. Auch hier gibt es ein Maximums- und ein Eindeutigkeitsprinzip.

Theorem 3.1.1 (Maximumsprinzip)Eine harmonische Funktion f(x, y) nimmt ihr Maximum M und ihr Minimum m am Randan.

Beweis: Ubung!

Theorem 3.1.2 (Eindeutigkeitsprinzip)Seien f(x, y) und g(x, y) harmonische Funktionen auf S mit f(a, b) = g(a, b) fur (a, b) ∈ B.Dann gilt

f(x, y) = g(x, y), fur alle (x, y) ∈ S.

Beweis: Ubung!

Die betrachtete Funktion p(x) ist eine harmonische Funktion mit gegebenen Randwerten,also ist diese nach dem Eindeutigkeitsprinzip, falls wir sie explizit angeben konnen, aucheindeutig bestimmt. Wie konnen wir in diesem Fall die Funktion p(x) bestimmen?

3.2 Losung bestimmen uber lineare Gleichungssysteme

Die Eigenschaften e)-f) bilden ein lineares Gleichungssystem mit 5 Unbekannten (hierp(a), p(b), p(c), p(d) und p(e)) und 5 Gleichungen. Losen wir dieses lineare Gleichungssy-stem (Ubung!), so kommen wir auf die eindeutige Losung

p(a)p(b)p(c)p(d)p(e)

≈

0.87640450.50561800.32303370.82303370.7865169

.

21

3.3 Losung approximieren uber Monte-Carlo-Methode

In der Stochastik werden zufallige Phanomene oft uber die sogenannte Monte Carlo Metho-de1 simuliert. Dabei wird ein zufalliger Vorgang n-mal wiederholt (n ∈ N moglichst groß)und sich die relative Haufigkeit eines eintretenden Ereignisses angeschaut. Diese relativeHaufigkeit wird als Schatzung der fur dieses Ereignis zu erwartenden wahren Wahrschein-lichkeit genommen. In unserem Beispiel 3.0.5 implementieren wir die angegebene Irrfahrtauf dem Computer und fuhren sie ausgehend von den Punkten a bis e jeweils 10000 maldurch. Die sich dadurch ergebene Schatzung lautet

p(a)p(b)p(c)p(d)p(e)

=

0.87850.49750.31650.82750.7825

.

Die Approximation an die Losung ist offensichtlich ganz gut. Mochte man eine genaue-re Naherung bekommen, so muss man einfach die Anzahl der durchlaufenen Irrfahrtenerhohen.

3.4 Irrfahrten auf dem Zahlengitter in der Ebene ohne Schran-ken

Betrachten wir die symmetrische Irrfahrt auf S = Z2 mit B = ∅ so erhalten wir ei-ne Irrfahrt ohne Schranken. Hier stellt sich schon wie in Kapitel 1 die Frage nach der

−60 −40 −20 0 20 40

−80

−60

−40

−20

020

Abbildung 3.2: Ein Pfad einer Irrfahrt in der Ebene mit n = 10000 Schritten.1Begriffsbildung: Die Methode ist nach den beruhmten Spielcasinos in Monte Carlo benannt

22

Wahrscheinlichkeit einen beliebigen Punkt (x, y) ∈ Z2 fruher oder spater zu besuchen.Aquivalent hierzu ist die Frage, ob ein Teilchen bei einer symmetrischen Irrfahrt in derEbene immer an seinen Ausgangspunkt zuruck kommt. Dieses Problem lost der Satz vonPolya.

Theorem 3.4.1 (Satz von Polya)Eine symmetrische Irrfahrt auf einem Zahlengitter in der Ebene ohne Schranken kommtimmer zu ihrem Startwert zuruck.

Dieses Theorem wollen wir nicht beweisen. Es sei aber noch gesagt, dass dies in hoherenDimensionen (≥ 3) nicht mehr zutrifft. Im folgenden wollen wir auf diese sehr interessanteKlasse von Irrfahrten aber nicht weiter eingehen.

3.5 Das Banach’sche Streichholzproblem

Der polnische Mathematiker Stefan Banach (geb. 1892, gest. 1945) stellte folgendes Pro-blem: Eine Person hat in jeder seiner beiden Hosentaschen eine Streichholzschachtel mitn Streichholzern. Wenn ein Streichholz gebraucht wird, zieht er mit gleicher Wahrschein-lichkeit eine Schachtel aus seinen Taschen und entnimmt eines. Dies macht er so lange biser eine Schachtel zieht die leer ist. Wieviele Streichholzer verbleiben im Durchschnitt nochin der nichtleeren Schachtel?

Wir ubertragen das Problem auf eine Irrfahrt in der Ebene. Dabei starten wir die Irrfahrtim Punkt (0, 0) und laufen mit Wahrscheinlichkeit 1

2 nach rechts bzw. nach oben. Die Irr-fahrt endet falls die Geraden x = n + 1 bzw. y = n + 1 erreicht werden (die Irrfahrt endetfalls n + 1-mal eine der beiden Streichholzschachteln gezogen wird), siehe fur eine Visua-lisierung der Irrfahrt mit inneren Punkten und Schranken Abbildung 3.3. Wir bezeichnenmit R die Anzahl an verbleibenden Streichholzern in der nichtleeren Schachtel und mit Ndie Anzahl der Ziehungen bis eine der beiden Schachteln leer ist. Es gibt einen funktio-nalen Zusammenhang zwischen den beiden Zufallsvariablen R und N , da die Anzahl derbenotigten Ziehungen gegeben ist durch n + 1 Ziehungen der am Ende leeren Schachtelund n−R Ziehungen der nichtleeren Schachtel. Es gilt also

N = 2n + 1−R.

Um E(R) zu berechnen brauchen wir also E(N). Wir versuchen die Wahrscheinlich-keitsverteilung von N zu bestimmen. Dazu betrachten wir das Ereignis N = k furk = n + 1, . . . , 2n + 1. Weiter bezeichnen wir mit pk := P (N = k). Falls also N = k gilt,so muss gelten

1. n der ersten k − 1 Ziehungen fallt auf die linke Streichholzschachtel und auch diek-te Ziehung.

2. n der ersten k − 1 Ziehungen fallt auf die rechte Streichholzschachtel und auch diek-te Ziehung.

23

-

6

¾0−1

−1

1

n + 1

y

x1 n + 1

B

-

6- -

6- -

Abbildung 3.3: Irrfahrt im Zahlengitter S mit eingezeichneter Schranke B

Wegen der Symmetrie dieser beiden Ereignisse sind sie gleichwahrscheinlich. Nun gibt es(k−1n

)Moglichkeiten (vgl. Abschnitt 2.1.2) in den ersten k − 1 Ziehungen n-mal die linke

(rechte) Streichholzschachtel zu ziehen. Also ist die Wahrscheinlichkeit pk gegeben durch

pk = P (N = k) = 2(

k − 1n

)(12

)k−1 12

=(

k − 1n

)(12

)k−1

.

Fur k = n + 1, . . . , 2n gilt fur den Quotienten

pk

pk+1=

(k−1n

) (12

)k−1

(kn

) (12

)k=

2(k − n)k

(3.1)

und insbesondere gilt

pn+1 =(

12

)n

und p2n+1 =(

2n

n

)(12

)2n

Wir nutzen die Formel (3.1) aus, um den Erwartungswert

E(N) = (n + 1)pn+1 + (n + 2)pn+2 + · · ·+ (2n)p2n + (2n + 1)p2n+1

zu bestimmen. Zunachst schreiben wir (3.1) um zu

2(k + 1)pk+1 = kpk + 2(n + 1)pk+1.

24

Summieren wir beiderseits uber k = n + 1, n + 2, . . . , 2n auf, so erhalten

2E(N)− 2(n + 1)pn+1 = E(N)− (2n + 1)p2n+1 + 2(n + 1)(1− pn+1).

Auflosen nach E(N) liefert

E(N) = 2(n + 1)− (2n + 1)(

2n

n

)(12

)2n

.

Wegen E(R) = 2n + 1 − E(N) ist also die gesuchte durchschnittliche Anzahl an in einerSchachtel verbleibenden Streichholzern gegeben durch

E(R) = (2n + 1)(

2n

n

)(12

)2n

− 1.

Falls wir also mit n = 50 Streichholzern in einer Schachtel starten, so gilt

E(R) ≈ 7.0385.

Also werden im Mittel ungefahr 7 Streichholzer in einer der beiden Schachteln ubrig blei-ben. Einen Link zu einer Simulation des Banach’schen Streichholzproblems findet sich aufder Homepage des Schnupperkurses.

3.6 Bernoulli und Tennis

Jakob Bernoulli (geb. 1654, gest. 1705) beschreibt in Letter to a Friend on the Sets inCourt Tennis mit Hilfe von Irrfahrten die Gewinnwahrscheinlichkeit eines Spielers furein Spiel im Tennis in Abhangigkeit seiner Spielstarke in Relation zur Spielstarke seinesGegners. Betrachten wir ein Spiel im Tennis mit den ublichen Regeln. Anstatt der normalenZahlweise 0, 15, 30, 40, Spiel, notieren wir Punkte 0, 1, 2, . . .. Das Spiel endet also bei denSpielstanden 4 − 0, 4 − 1, 4 − 2, 5 − 3, 6 − 4, . . . oder 0 − 4, 1 − 4, . . .. Wir betrachten dasfolgende Modell (siehe Abbildung 3.4): Die schwarzen Punkte gehoren zur Menge dermoglichen Spielstande S und die eingezeichneten Schranken B. Wir nehmen im Folgendenan, dass Spieler 1 mit Wahrscheinlichkeit p und Spieler 2 mit Wahrscheinlichkeit q = 1−peinen Punkt macht und der Quotient p

q = m ∈ N eine naturliche Zahl darstellt. Ein Spielist also eine Irrfahrt, die im Punkt (0, 0) startet, mit Wahrscheinlichkeit p einen Schrittnach rechts und mit Wahrscheinlichkeit q einen Schritt nach oben lauft. Sie endet, fallssie die Schranke B erreicht. Gesucht ist die Wahrscheinlichkeit P (i, j), dass Spieler 1 beimSpielstand (i, j) ∈ N2

0 das Spiel fur sich entscheidet, also gewinnt.Wir stellen die Losung zu diesem Problem von Bernoulli von vor uber 300 Jahren dar:Wir betrachten die Beziehung

P (i, j) = pP (i + 1, j) + qP (i, j + 1).

Nach zweimaligem Anwenden dieser Beziehung und einsetzen des Punktes (3, 3) erhaltenwir

P (3, 3) = p2P (5, 3) + 2pqP (4, 4) + q2P (3, 5).

25

-

6

¾0−1

−1

1

2

3

4

y

x1 2 3 4

B

B

Abbildung 3.4: Zahlengitter S mit eingezeichneten Schranken B

Wir wissen, dass Spieler 1 beim Stand von (5, 3) gewonnen hat, also P (5, 3) = 1 gilt,und er beim Stand von (3, 5) verloren hat, also P (3, 5) = 0 ist. Weiter gilt offensichtlichP (4, 4) = P (3, 3), da dann wieder Gleichstand ist und beide Spieler noch 2 Punkte inFolge benotigen um zu gewinnen. Daraus erhalten wir

P (3, 3) = p21 + 2pqP (3, 3)

also

P (3, 3) =p2

1− 2pq=

p2

p2 + q2=

m2

m2 + 1.

Nun konnen wir einfach mit P (2, 4) = 0

P (2, 3) = pP (3, 3) + qP (2, 4) =p3

p2 + q2

und mit P (4, 2) = 1

P (3, 2) = pP (4, 2) + qP (3, 3) = p +qp2

p2 + q2.

Fuhrt man dies nach gleichem Schema fort, so erhalt man in Abhangigkeit von m dieAusgangswahrscheinlichkeit fur den Gewinn eines Punktes

P (0, 0) =m7 + 5m6 + 11m5 + 15m4

m7 + 5m6 + 11m5 + 15m4 + 15m3 + 11m2 + 5m + 1.

Fur einige konkrete Werte von m ∈ N ergibt die Auswertung der angegebenen Formel diefolgende Tabelle:

26

m 1 2 3 4

P (0, 0) 12

208243

243256

5196853125

Man kann nun leicht alle Werte P (i, j) fur (i, j) ∈ S angeben. Als Ubung kann man zeigen,dass falls der Spieler 1 doppelt so stark ist wie sein Gegner, also insbesondere m = 2 gilt,Spieler 1 dem Gegner zwei Punkte Vorsprung geben kann und das Spiel ist annaherndfair. In diesem Fall gilt P (0, 2) ≈ 0.5136.

3.7 Abschließende Bemerkungen

Fur diesen Schnupperkurs wurden die Bucher von Doyle und Snell [2], von Blom, Holstund Sandell [1] und von Feller [3] verwendet. Die Grundlagen entstammen dem Lehrbuchvon Herrn Henze [4], welches eine gute Einfuhrung in die Stochastik liefert und anhanddessen die Vorlesung Einfuhrung in Stochastik (Stochastik 1) im Bachelor aufgebaut wird.

27

Literaturverzeichnis

[1] Holst L. Blom, G. and D. Sandell. Problems and Snapshots from the World of Proba-bility. Springer, 1994.

[2] P. G. Doyle and J. L. Snell. Random Walks and Electric Networks. The MathematicalAssociation of America, 1984.

[3] W. Feller. An Introduction to Probability - Theory and Applications, Volume I. Wiley,2te edition, 1960.

[4] N. Henze. Stochastik fur Einsteiger - Eine Einfuhrung in die faszinierende Welt desZufalls. Vieweg+Teubner, 8te edition, 2010.

28