Grundbegriffe der Wahrscheinlichkeitsrechnung: Die Axiome von Kolmogorov

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Grundbegriffe der Wahrscheinlichkeitsrechnung: Zufallsexperiment und Wahrscheinlichkeit
    • Grundbegriffe der Wahrscheinlichkeitsrechnung: Die Axiome von Kolmogorov

Einführung

In Grundbegriffe der Wahrscheinlichkeitsrechnung: Zufallsexperiment und Wahrscheinlichkeit wurden bereits die Begriffe eingeführt, die das Fundament der Wahrscheinlichkeitsrechnung bilden. Im Sinne strenger Mathematik wird man sich aber mit der saloppen Formulierung nicht zufrieden geben und eine schärfere Definition der Begriffe und eine klare Formulierung der Axiome der Wahrscheinlichkeitsrechnung fordern. Dies soll in diesem Kapitel nachgeholt werden.

Dabei wird aber die Wahrscheinlichkeitsrechnung nicht in ihrem vollen Umfang entfaltet. Aus allen Bereichen der Mathematik ist bekannt, dass man mit Unendlichkeiten sehr leicht Paradoxien erzeugen kann oder dass Beweise plötzlich sehr schwer werden, die im Endlichen völlig trivial sind. Ebenso ist es in der Wahrscheinlichkeitsrechnung: die Axiome werden hier nur in der eingeschränkten Version formuliert, die diesen Schwierigkeiten aus dem Weg geht. Stattdessen werden einige Beispiele gezeigt, die andeuten, worin die Schwierigkeiten liegen.

Ereignisalgebra, Wahrscheinlichkeitsraum und die Axiome von Kolmogorov

Ereignisalgebra

Die Ereignisalgebra A wurde als ein Mengensystem eingeführt, das aus Teilmengen des Ergebnisraumes Ω besteht und bezüglich der Mengenoperationen Komplement-Bildung und Vereinigung abgeschlossen ist. Die Ereignisalgebra bildet somit das relevante Mengensystem zu einem Zufallsexperiment, wenn man sich auf gewisse Ergebnisse beschränkt und nicht etwa die detaillierte Beschreibung mit Hilfe der Elementarereignisse anstrebt.

Paradebeispiel ist beim Würfeln (mit Ω = {1, 2, 3, 4, 5, 6}) das Mengensystem, das aus der leeren Menge ∅, den ungeraden Zahlen U = {1, 3, 5}, den geraden Zahlen G = {2, 4, 6} und der Menge Ω besteht:

A = { ∅, {2, 4, 6}, {1, 3, 5}, {1, 2, 3, 4, 5, 6} }

Für jemanden, der beim Würfelspiel auf gerade oder ungerade Zahlen setzt, ist lediglich relevant, ob die gewürfelte Zahl in der Menge G oder U liegt, das Elementarereignis ist irrelevant.

Eine Definition für die Ereignisalgebra könnte lauten:

Definition: Sei Ω eine nicht-leere Menge mit endlich vielen Elementen. Eine Menge von Teilmengen A von Ω heißt Ereignisalgebra, wenn gilt:

• Die Menge Ω ist in A enthalten: A ∈ Ω.
• Das Mengensystem A ist bezüglich der Komplement-Bildung in A abgeschlossen: Für A ∈ A gilt A^C ∈ A.
• Das Mengensystem A ist bezüglich der Bildung der Vereinigungsmenge in A abgeschlossen: Für A, B ∈ A gilt A ∪ B ∈ A.

Bemerkung: Da man die Bildung der Durchschnittsmenge auf die Vereinigung und Komplement-Bildung zurückführen kann, ist die Ereignisalgebra auch unter der Durchschnitts-Bildung abgeschlossen.

Aufgabe: Zeigen Sie die Aussage der letzten Bemerkung, also:

Für A, B ∈ A gilt: A ∩ B ∈ A.

Wahrscheinlichkeit und Wahrscheinlichkeitsraum

Die Wahrscheinlichkeit wurde als eine Maßzahl eingeführt, die einem Ereignis, also einem Element der Ereignisalgebra, zugeordnet wird und die bestimmte Eigenschaften hat, die man mit dem Begriff der Wahrscheinlichkeit verbindet:

• sie darf nicht negativ sein,
• sie kann höchstens gleich 1 sein,
• bei disjunkten Ereignissen (wie die geraden und die ungeraden Zahlen beim Würfeln) addieren sich die Wahrscheinlichkeiten.

Mathematisch formuliert ist dann die Wahrscheinlichkeit eine Mengenfunktion P, da sie einer Menge A eine Zahl P(A) zuordnet. Der Wahrscheinlichkeitsraum wird dann vom Ergebnisraum Ω, der Ereignisalgebra A und der Mengenfunktion P gebildet; die Definitionen lauten wie folgt:

Definition: Sei Ω eine nicht-leere Menge mit endlich vielen Elementen und A eine Ereignisalgebra über Ω. Ein Wahrscheinlichkeitsmaß P ist eine Abbildung

P : A → [0; 1]

mit folgenden Eigenschaften:

• P(Ω) = 1.
• Für disjunkte Mengen A, B ∈ A gilt: P(A ∪ B) = P(A) + P(B).

Definition: Ein Wahrscheinlichkeitsraum (Ω, A, P) setzt sich aus einer nicht-leeren, endlichen Menge Ω, einer Ereignisalgebra A über Ω und einem Wahrscheinlichkeitsmaß P auf A zusammen.

Die Axiome von Kolmogorov

Formulierung der Axiome

Die Axiome von Kolmogorov sind eigentlich schon in der Definition eines Wahrscheinlichkeitsmaßes enthalten, sie werden dennoch ausdrücklich formuliert, um ihre besondere Rolle deutlich zu machen: In Definitionen werden Begriffe neu eingeführt und ihre Eigenschaften beschrieben – sie dienen vor allem dazu, eindeutige Aussagen zu machen, welche Eigenschaften einem Objekt (oder Begriff) zugewiesen werden. Der verwendete Begriff kann mit Nebenbedeutungen aus der Umgangssprache überladen sein, die man somit ausschließen möchte. Werden dagegen Axiome formuliert, möchte man damit ausdrücken, dass ein besonders relevanter Begriff definiert wird. Bei der Wahrscheinlichkeit ist dies zweifellos der Fall, da in allen Naturwissenschaften von Zufall und Wahrscheinlichkeit die Rede ist. Mit der axiomatischen Festlegung von Wahrscheinlichkeit soll ein Angebot gemacht werden, wie man den Begriff mathematisch formulieren kann. Ob diese Axiome dann für die anderen Wissenschaften die geeignete Formulierung sind, ist eine andere Frage.

Axiome von Kolmogorov:

Sei (Ω, A, P) ein Wahrscheinlichkeitsraum. Dann ist:

1. P(A) ≥ 0 für alle A ∈ A.
2. P(Ω) = 1.
3. Für disjunkte A, B ∈ A gilt: P(A ∪ B) = P(A) + P(B).

Additivität für unendliche Vereinigungen

Es soll nicht verheimlicht werden, dass es eigentlich eine Anmaßung ist, obige Axiome für einen endlichen Ergebnisraum Ω als Axiome von Kolmogorov zu bezeichnen. Denn der wirklich schwierige Teil der Arbeit Kolmogorovs bestand darin zu zeigen, dass diese Axiome auch dann zu einem konsistenten Wahrscheinlichkeitsbegriff führen, wenn man von endlichen Ergebnisräumen zu kontinuierlichen Ergebnisräumen übergeht, etwa einem Intervall oder einem Rechteck. Im dritten Axiom werden dann nicht nur zwei disjunkte Mengen betrachtet, sondern unendlich viele paarweise disjunkte Mengen; auf der rechten Seite des dritten Axioms steht dann eine unendliche Summe.

Um kurz die Leistung Kolmogorovs anzudeuten: Das Wahrscheinlichkeitsmaß P hat große Ähnlichkeit mit einem Flächenmaß, denn für disjunkte Mengen addieren sich deren Flächen. Die Normierung P(Ω) = 1 hätte dann die Bedeutung, dass man nur Flächenberechnungen innerhalb einer endlich großen Fläche Ω zulässt und deren Fläche gleich 1 setzt. Dennoch besteht das Problem, dass man innerhalb von Ω – sofern es sich um ein Kontinuum handelt – unendlich viele disjunkte Teilmengen bilden kann und nicht klar ist, welches Flächenmaß ihre Vereinigung hat. Für die Flächenberechnung wurde das Problem gelöst –, das Hauptproblem beseht darin, dass es in jedem Kontinuum exotische Mengen gibt, denen man keine Fläche zuordnen kann und man daher erst die Menge der "messbaren Mengen" charakterisieren muss. Kolmogorov hat diese Lösung zum Vorbild genommen, hat sie von allen geometrischen Elementen bereinigt, die speziell für die Flächenberechnung relevant sind, und konnte so ein Axiomensystem für die Wahrscheinlichkeit angeben.

Eine Diskussion, welchen Unterschied es macht, ob im dritten Axiom endlich oder unendlich viele Mengen stehen, soll hier nicht geführt werden – dies geschieht in Büchern über Wahrscheinlichkeitstheorie. Die Beispiele im folgenden Abschnitt sollen ein wenig auf die Unterschiede hindeuten – sind aber noch weit entfernt von den eigentlichen mathematischen Problemen unendlicher Vereinigungen in einem Kontinuum.

Beispiele

Gleichwahrscheinliche Elementarereignisse

Paradebeispiele für Wahrscheinlichkeitsräume mit gleichwahrscheinlichen Elementarereignissen sind der Münzwurf und das Würfeln. Im ersten Fall ist

Ω = {0, 1} und P(0) = 1/2 = P(1)

(statt 0 und 1 könnte man auch Kopf und Zahl als Elementarereignisse nehmen).

Im zweiten Fall ist

Ω = {1, 2, 3, 4, 5, 6} und P(1) = 1/6 = P(2) = P(3) = ... = P(6).

Eine Münze oder ein Würfel mit gleichwahrscheinlichen Elementarereignissen wird als Laplace-Münze oder Laplace-Würfel bezeichnet.

Kennt man diese Beispiele, ist es nicht schwer, sich einen Wahrscheinlichkeitsraum mit n gleichwahrscheinlichen Elementarereignissen vorzustellen:

Ω = {1, 2, ... , n} und P(1) = 1/n = P(2) = P(3) = ... = P(n).

Und kann man dann nicht zum Grenzwert n → ∞ übergehen?

Nein, denn dann gibt es unendlich viele Elementarereignisse und jedes Elementarereignis müsste die Wahrscheinlichkeit 0 haben. Wie soll man dann für beliebige Mengen A eine Wahrscheinlichkeit definieren? Für endliche Mengen muss sich immer 0 ergeben. Aber für unendliche Mengen? Haben sie alle die Wahrscheinlichkeit 1 oder gibt es Mengen mit Wahrscheinlichkeit 1/2 oder 1/3? Welche Wahrscheinlichkeit haben etwa die durch 3 teilbaren Zahlen? Oder deren Quadrate?

Egal, wie man die Wahrscheinlichkeiten definiert, man gerät immer in Widersprüche. Kurz: es gibt keine gleichwahrscheinlichen Elementarereignisse bei unendlichen Mengen Ω.

Zweimaliges Würfeln

Aufgabe:

Ein Laplace-Würfel wird zweimal nacheinander geworfen und die beiden Augenzahlen werden notiert (in der Reihenfolge, in der sie erscheinen).

Geben Sie für dieses Zufallsexperiment die Ereignisalgebra an.

Berechnen Sie die Wahrscheinlichkeiten der Elementarereignisse.

Diskutieren Sie: Lassen sich diese Wahrscheinlichkeiten allein aus der Annahme Laplace-Würfel und den Axiomen von Kolmogorov berechnen oder benötigt man weitere Voraussetzungen?

Lösung:

Die Elementarereignisse besitzen die Form (ω₁, ω₂), wobei ω₁ und ω₂ alle Zahlen von 1 bis 6 annehmen können und daraus alle 36 Kombinationen gebildet werden. Es gibt also 36 Elementarereignisse, die zusammen den Ergebnisraum Ω₂ bilden, den man auch als das Kreuzprodukt der Ergebnisräume für den einfachen Wurf beschreiben kann:

Ω₂ = Ω × Ω = {1, 2, 3, 4, 5, 6} × {1, 2, 3, 4, 5, 6}.

Und die Ereignisalgebra, die dieses Zufallsexperiment beschreibt, ist die Potenzmenge von Ω₂, also die Menge aller Teilmengen von Ω₂. Sie besitzt

2³⁶ = 68 719 476 736

Elemente, die hier nicht alle aufgezählt werden.

Die Frage nach der Wahrscheinlichkeit der Elementarereignisse ist nicht ganz einfach: Zunächst ist vorausgesetzt, dass der Würfel ein Laplace-Würfel ist, dass also beim einmaligen Wurf alle Elementarereignisse gleich wahrscheinlich sind. Folgt daraus, dass auch die Elementarereignisse beim zweimaligen Werfen gleichwahrscheinlich sind?

Aus den Axiomen von Kolmogorov folgt dies sicher nicht, da sie nichts darüber aussagen, wie bei einem zusammengesetzten Zufallsexperiment die Wahrscheinlichkeiten berechnet werden, wenn die Wahrscheinlichkeiten für die Einzel-Experimente bekannt sind.

Dass die Frage nicht so einfach ist, kann folgendes Beispiel demonstrieren: Enthält eine Urne 5 weiße und 5 schwarze Kugeln und werden nacheinander zwei Kugeln gezogen, so ist selbst bei der Laplace-Annahme nicht klar, welche Wahrscheinlichkeiten beim zweiten Zug gelten. Denn es kommt darauf an, ob die Kugel des ersten Zuges wieder zurückgelegt wird oder nicht.

Wird sie zurückgelegt, herrschen beim zweiten Zug dieselben Bedingungen wie beim ersten Zug, wird sie nicht zurückgelegt, hängen die Wahrscheinlichkeiten beim zweiten Zug vom Ergebnis des ersten Zuges ab.

Erst wenn man für das zweimalige Würfeln ausdrücklich voraussetzt, dass die beiden Würfe unabhängig voneinander stattfinden, darf man sagen, dass alle 36 Elementarereignisse gleich wahrscheinlich sind. Allerdings ist bei der Voraussetzung, dass der Würfel "zweimal nacheinander" geworfen wird, schwer vorstellbar, wie der erste Wurf den zweiten beeinflussen soll.

Nimmt man also an, dass die Würfe unabhängig voneinander stattfinden, hat jedes der 36 Elementarereignisse die gleiche Wahrscheinlichkeit 1/36.

Würfeln bis zur ersten 6

Das folgende Beispiel scheint auch mit einem unendlichen Ω zu arbeiten, ist aber mit den Axiomen von Kolmogorov zu bewältigen.

Ein Laplace-Würfel wird so lange geworfen bis zum ersten Mal die 6 erscheint.

Aufgabe:

Kann man aus der Annahme, dass es sich um einen Laplace-Würfel handelt und den Axiomen von Kolmogorov herleiten, welche Wahrscheinlichkeiten Ereignisse der Art haben:

"Nach n Würfen erscheint die erste 6, mit n = 1, 2, 3, ... "?

Berechnen Sie diese Wahrscheinlichkeiten!

Berechnen Sie die Wahrscheinlichkeiten der Art:

"Es erscheint n Würfe lang keine 6".

Lösung:

Wie im letzten Beispiel benötigt man wieder die Annahme der Unabhängigkeit der Würfe. Ist sie gegeben, kann man aus der Laplace-Annahme die Wahrscheinlichkeit eines Ereignisses "erste 6 nach n Würfen" berechnen, da für endliches n kein Problem auftritt.

Wenn beim n-ten Wurf die erste 6 eintritt, müssen die Ergebnisse der n - 1 vorhergehenden Würfe ungleich 6 gewesen sein und es gilt (siehe auch Gleichung (3) in Abbildung 1):

P("erste 6 nach n Würfen") = (5/6)^n-1 · 1/6.

Wie groß ist dannn die Wahrscheinlichkeit dafür, dass nie eine 6 kommt?

Dazu summiert man alle Wahrscheinlichkeiten P("erste 6 nach n Würfen"); das Gegenereignis dazu ist das Ereignis, dass niemals eine 6 gewürfelt wird.

Die Folge der Wahrscheinlichkeiten P("erste 6 nach n Würfen") ist eine geometrische Folge, die gemäß Gleichung (1) in Abbildung 1 aufaddiert werden kann. Der Grenzübergang zur unendlichen Summe ist in Gleichung (2) ausgeführt.

Angewendet auf die Wahrscheinlichkeiten beim Würfeln, erhält man die Berechnung in Gleichung (4): Die Wahrscheinlichkeiten dafür, dass nach n Würfen eine 6 erscheint, addieren sich zu 1 (bei Summation über n); entsprechend geht die Wahrscheinlichkeit dafür, dass niemals eine 6 erscheint, gegen 0.

In Gleichung (5) wird die Wahrscheinlichkeit dafür berechnet, dass bei n Würfen keine 6 erscheint. Man beachte, dass dies nicht das Gegenereignis zu "nach n Würfen erscheint die erste 6" ist.

Abbildung 1: Die geometrische Reihe und die Berechnung der Wahrscheinlichkeit dafür, dass nach endlichen vielen Würfen eine 6 eintritt (geometrische Verteilung).

Die Wahrscheinlichkeiten aus Gleichung (3) sind in Abbildung 2 für n = 1, 2, ..., 20 aufgetragen. Man erkennt, dass sie sehr schnell gegen null gehen.

Abbildung 2: Die geometrische Verteilung: Die Wahrscheinlichkeit dafür, dass beim n-ten Wurf die erste 6 eintritt (in Abhängigkeit von n).

Wegen der Verwandtschaft zur geometrischen Folge werden die Wahrscheinlichkeiten in Abbildung 2 als geometrische Verteilung bezeichnet.

R-Skripte

Berechnung der geometrischen Verteilung

In Abbildung 2 war die geometrische Verteilung dargestellt. Dabei wird ein Zufallsexperiment so lange durchgeführt bis ein bestimmtes Ergebnis eintritt (dieses Ergebnis wird meist als Treffer bezeichnet).

Für die Berechnung der Wahrscheinlichkeiten und deren Darstellung im Histogramm soll ein R-Skript gezeigt werden.

Zuerst wird eine Funktion geom() definiert, die die Wahrscheinlichkeiten berechnet. Sie besitzt zwei Eingabewerte:

• Die Wahrscheinlichkeit prob für das Ergebnis, das als Erfolg gewertet wird (Treffer) und die zum Abbruch des Zufallsexperimentes führt; im Beispiel oben war es die 6 beim Würfeln, die mit Wahrscheinlichkeit prob = 1/6 eintritt.
• Die Maximalzahl number an Versuchen, für die die Wahrscheinlichkeiten der geometrischen Verteilung berechnet werden; da die Versuchsreihe im Prinzip beliebig lange laufen kann, sollte man sich einen geeigneten Abbruch überlegen.

geom <- function(prob = 0.5, number = 10){
  result <- vector(mode = "numeric", length = number)
  result[1] = prob
  for(i in (2:number)){
    result[i] <- result[i - 1] * (1 - prob)
  }
  return(result)
}

Zur Erklärung:

Zeile 1: Die default-Werte für prob und number werden gleich 0.5 und 10 gesetzt (dies entspricht dem Münzwurf mit maximal 10 Versuchen).

Zeile 2: Für die Wahrscheinlichkeiten wird ein Vektor der Länge number vorbereitet.

Zeile 3: Die erste Komponente ist gleich der Treffer-Wahrscheinlichkeit prob.

Zeile 4 bis 6: Die i-te Komponente besteht aus (i - 1)-mal dem Faktor (1 - p) und einmal dem Faktor p; sie werden in der Schleife gesetzt.

Zur Ausgabe in einem Histogramm wird die Funktion plot() verwendet, der die mit geom() berechneten Wahrscheinlichkeiten übergeben werden; zur besseren Darstellung werden weitere Argumente gesetzt:

plot(x = (1:20), y = geom(prob = 1 / 6, number = 20), 
     type = 'h', col = "blue", main = "\"erste 6 nach n Würfen\"", xlab = "n", ylab = "P(n)")

Es werden 20 Wahrscheinlichkeiten berechnet mit der Treffer-Wahrscheinlichkeit prob = 1/6. Als weitere Argumente werden gesetzt:

• Darstellung als Histogramm mit type = 'h' ,
• Farbe blau mit col = "blue" ,
• Titel des Diagramms mit main = "\"erste 6 nach n Würfen\"" ,
• Beschriftung der x- und y-Achse mit xlab = "n", ylab = "P(n)" .

Simulation des Würfelns bis zur ersten 6 durch Zufallszahlen und deren Auswertung

Es werden zwei Algorithmen vorgestellt, mit denen das Würfeln bis zur ersten 6 simuliert werden kann:

• Der erste Algorithmus erzeugt eine große Anzahl N von Zufallsfolgen der Länge trial.length, die einfach daraufhin untersucht werden, wann die erste 6 erscheint; die restlichen Zahlen werden nicht ausgewertet. Es wird die relative Häufigkeit bestimmt, wie oft eine Folge der Länge n in den N Zufallsfolgen vorkommt.
• Weniger Speicherplatz benötigt der zweite Algorithmus, der lediglich eine sehr lange Zufallsfolge erzeugt; sie wird in Teilfolgen zerhackt, nämlich bis zur ersten 6. Für die unterschiedlichen Längen der Teilfolgen werden die relativen Häufigkeiten bestimmt.

Der brute-force Algorithmus

Naheliegend um in einer Simulation die Wahrscheinlichkeiten in Abbildung 2 durch relative Häufigkeiten zu approximieren, ist folgende Vorgehensweise:

• Man erzeugt numberOfTrials Zufallsfolgen zum Würfeln.
• Jede dieser Zufallsfolgen wird untersucht, wann die erste 6 eintritt.
• Für die verschidenen Dauern werden innerhalb der numberOfTrials Zufallsfolgen relative Häufigkeiten bestimmt.

Das folgende Skript zeigt, wie eine Zufallsfolge erzeugt wird und wie man bestimmt, wann die erste 6 eintritt. Man beachte, dass man dazu nicht das Würfeln simulieren muss, sondern es reicht ein Zufallsexperiment mit zwei Ausgängen zu verwenden (wie den Münzwurf), wobei ein Ausgang als Treffer zählt (und die Wahrscheinlichkeit 1/6 besitzt) und der andere Ausgang als Nicht-Treffer (mit Wahrscheinlichkeit 5/6).

trial.length <- 36
# 1 = Treffer, 2 = kein Treffer
rs <- sample(x = 2, size = trial.length, replace = TRUE, prob = c(1/6, 5/6))

idx <- which(rs == 1)

# Ausgaben:
rs
# [1] 2 2 1 2 2 2 2 2 2 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 1 2 2 2 2
idx
# [1]  3 10 12 28 32
min(idx)
# [1] 3

Zur Erklärung:

Zeile 1: Die Variable trial.length gibt später an, wie lange eine Zufallsfolge ist.

Zeile 3: Die Funktion sample() erzeugt die Zufallsfolge. Das Ergebnis wird in rs (steht für random sequence) abgespeichert.

Mit dem Eingabewert x wird eigentlich die Ergebnismenge festgelegt, da man nur zwischen Treffer und Nicht-Treffer unterscheiden muss, wird x = 2 gesetzt. Dadurch entstehen Zufallsfolgen, dir nur die 1 und die 2 enthalten. An den Wahrscheinlichkeiten prob = c(1/6, 5/6) erkennt man, dass 1 für den Treffer steht und 2 für Nicht-Treffer.

Zeile 5: Mit Hilfe der Funktion which() wird festgestellt, an welchen Stellen in der Zufallsfolge rs eine 1 vorkommt. Der kleinste derartige Index ist dann die gesuchte Zahl, die angibt, wann beim Würfeln die erste 6 eintritt. Man beachte, dass idx alle Werte von 1 bis einschließlich trial.length annehmen kann, aber auch unbestimmt sein kann (wenn nämlich keine 6 in der Folge enthalten ist).

An den Ausgaben erkennt man, dass der erste Treffer (die erste 6) beim dritten Wurf eintritt und wie diese Zahl aus der Zufallsfolge gewonnen wird.

Dieser Algorithmus kann jetzt leicht erweitert werden:

• Es wird ein Zähler vorbereitet, der mitzählt, wie oft an der j-ten Stelle der Zufallsfolge die erste 6 erscheint.
• In einer Schleife werden numberOfTrials Zufallsfolgen erzeugt.
• Innerhalb der Schleife wird jeweils der richtige Zähler hochgezählt.
• Die Ergebnisse werden für die Ausgabe in einem Diagramm vorbereitet.
• Ein Diagramm wird erstellt, in dem die relativen Häufigkeiten der Simulation und die theoretischen Wahrscheinlichkeiten zu sehen sind.

Es kann natürlich vorkommen, dass auf der gesamten Länge der Zufallsfolge keine 6 erscheint: in diesem Fall wird der letzte Zähler hochgezählt; man könnte auch eine eigenen Zähler hierfür einbauen, da aber die Wahrscheinlichkeiten laut Abbildung 2 exponentiell gegen null gehen, sind die relativen Häufigkeiten bei großen Längen sowieso nicht genau zu bestimmen.

Das folgende Skript zeigt eine mögliche Realisierung dieser Aufgaben:

numberOfTrials <- 10000
trial.length <- 36

counter <- vector(mode = "numeric", length = trial.length)

for(i in seq_len(numberOfTrials)){
  # 1 = Treffer, 2 = kein Treffer
  rs <- sample(x = 2, size = trial.length, replace = TRUE, prob = c(1/6, 5/6))
  idx <- which(rs == 1)
  
  if(length(idx) == 0){
    # falls kein Treffer erscheint, wird der letzte counter hochgezählt
    j <- trial.length
  }
  else{
    j <- min(idx)
  }
  # hochzählen
  counter[j] <- counter[j] + 1
}    # Ende for-Schleife

# Normierung der Zähler
s <- sum(counter)
counter <- counter / s

# Kontrolle (s == numberOfTrials!?):
cat("Gesamtzahl der ausgewerteten Folgen: ", s)

x <- seq_len(trial.length)

# Ausgabe als Diagramm:
plot(x = x, y = counter, type = 'p', col = "red",
     main = "\"erste 6 nach n Würfen\"", xlab = "n", ylab = "P(n)")
# theoretische Werte
points(x = x, geom(prob = 1/6, number = trial.length), type = 'h', col = "blue")
# Nulllinie
lines(x = c(0, trial.length), y = c(0, 0), col = "green")

Zur Erklärung:

Zeile 1: Die Anzahl numberOfTrials der später zu erzeugenden Zufallsfolgen.

Zeile 2: Die Länge trial.length einer Zufallsfolge.

Zeile 4: Die Zähler werden vorbereitet. Ihre Anzahl stimmt mit trial.length überein; der Modus ist numeric und nicht integer, da sie später in relative Häufigkeiten umgerechnet werden.

Zeile 6 bis 20: Schleife, in der die Zufallsfolgen erzeugt und die Zähler hochgezählt werden.

Zeile 8 und 9: Wurden in der Vorbereitung beschrieben.

Zeile 11 bis 14: Falls die Zufallsfolge keinen Treffer enthält, wird der Index des letzten Zählers gesetzt.

Zeile 16: Andernfalls wird der "richtige" Zähler ausgewählt.

Zeile 19: Hochzählen des Zählers.

Zeile 23 und 24: Die absoluten Häufigkeiten werden in relative Häufigkeiten umgerechnet.

Zeile 27: Zur Kontrolle wird ausgegeben, wie viele Zufallsfolgen verarbeitet wurden.

Zeile 29 bis 37: Ausgabe der Ergebnisse im Diagramm.

Zeile 29: Vorbereitung der x-Achse.

Zeile 32 und 33: Auf der y-Achse werden die relativen Häufigkeiten aufgetragen, die im Vektor counter gespeichert sind. Die weiteren Konfigurationen des Plots sind ähnlich wie es für Abbildung 2 beschrieben wurde.

Zeile 35: Mit Hilfe der Funktion points() werden dem Plot weitere Punkte hinzugefügt, nämlich die mit geom() berechneten Wahrscheinlichkeiten.

Zeile 37: Mit lines() wird zuletzt die Nulllinie eingezeichnet

Die folgende Abbildung 3 zeigt die Ergebnisse:

Abbildung 3: Diagramm zum obigen Skript: Blau ist das Histogramm mit den theoretischen Wahrscheinlichkeiten (geometrische Verteilung), rot die relativen Häufigkeiten, die aus den Zufallsfolgen gewonnen wurden, grün die Nulllinie.

Der Vorteil dieses brute-force-Algorithmus liegt natürlich darin, dass man die Kontrolle darüber hat, wie viele Zufallsfolgen erzeugt werden. Dafür werden sie aber alle abgeschnitten und diese aufwendig erzeugten Teile der Zufallsfolgen gehen nicht in die Auswertung ein. Der folgende Algorithmus wird alle erzeugten Zufallszahlen auswerten, man kann aber weniger gut kontrollieren, wie viele Zufallsfolgen ausgewertet werden.

Verbesserter Algorithmus

Die Arbeitsweise des Algorithmus soll an einem einfachen Beispiel gezeigt werden:

trial.length <- 60

# 1 = Treffer, 2 = kein Treffer
rs <- sample(x = 2, size = trial.length, replace = TRUE, prob = c(1/6, 5/6))

idx <- which(rs == 1)

cat("Zufallsfolge: ", rs, "\n")
cat("Indizes der Treffer: ", idx, "\n")
# Zufallsfolge:  2 2 2 2 2 1 1 1 2 2 2 2 2 2 2 2 1 2 1 2 2 2 2 2 1 2 2 2 2 
# 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 1 2 2 1 2 2 2 2 2 2 
# Indizes der Treffer:  6 7 8 17 19 25 30 31 32 49 51 54  

diff <- diff(x = idx)
diff
# [1]  1  1  9  2  6  5  1  1 17  2  3

max.seq <- max(diff)
max.seq
# [1] 17

Zur Erklärung:

Zeile 1: Zur Demonstration wird nur eine kurze Zufallsfolge erzeugt.

Zeile 4: Erzeugen der Zufallsfolge mit sample() wie im letzten Algorithmus.

Zeile 6: Die Indizes der Treffer (1) werden bestimmt und abgespeichert.

Zeile 8 bis 12: Zur Veranschaulichung werden die Zufallsfolge rs un die Indizes der Treffer idx ausgegeben; später wird diese Ausgabe abgeschaltet.

Zeile 14: Mit Hilfe der Funktion diff() werden die Differenzen der aufeinanderfolgenden Komponenten von idx berechnet: Man erhält so die Längen der Teilfolgen von einem Treffer bis zum nächsten Treffer. Allerdings geht dabei die erste Teilfolge verloren; man könnte sie auch gesondert behandeln. Ebenso gehen die Zufallszahlen nach dem letzten Treffer verloren – aber wie sollte man sie auch verwenden?

Zeile 18: Mit der größten dieser Differenzen (die in der Variable max.seq gespeichert wird) ist festgelegt, wie viele Zähler benötigt werden.

Man beachte den Unterschied zwischen max.seq und der Länge von diff:

• Die Variable max.seq ist der größte Wert, der im Vektor diff vorkommt, und somit die längste Teilfolge (bis zum Eintreten der ersten 6).
• Die Länge von diff gibt an, wie viele Teilfolgen es gibt, da jede Komponente von diff für eine Teilfolge steht.

Man kann nach diesen Vorbereitungen leicht ersehen, wie der komplette Algorithmus aufgebaut wird:

• Für die Zähler counter wird ein Vektor der Länge max.seq angelegt, die mit den Anzahlen der Teilfolgen einer bestimmten Länge gefüllt werden; der Index von counter steht für die Länge der Teilfolge.
• Zu einer gegebenen Länge einer Teilfolge muss deren Anzahl in rs bestimmt werden; mit dieser Anzahl wird der entsprechende Zähler belegt.
• Die absoluten Häufigkeiten in den Zählern werden in relative Häufigkeiten umgerechnet.
• Wie im letzten Algorithmus wird ein geeignetes Diagramm erzeugt.

Das folgende Skript zeigt den gesamten Algorithmus:

length.trial <- 60000

# 1 = Treffer, 2 = kein Treffer
rs <- sample(x = 2, size = length.trial, replace = TRUE, prob = c(1/6, 5/6))

idx <- which(rs == 1)
# cat("Zufallsfolge: ", rs, "\n")
# cat("Indizes der Treffer: ", idx, "\n")

diff <- diff(x = idx)
# diff
max.seq <- max(diff)

counter <- vector(mode = "numeric", length = max.seq)

for(i in (1:length(diff))){
  lgth <- diff[i]
  counter[lgth] <- counter[lgth] + 1
}

# Normierung der Zähler
s <- sum(counter)
counter <- counter / s
cat("Anzahl der ausgewerteten Folgen: ", s)
# Anzahl der ausgewerteten Folgen:  10021

# Diagramm
x <- (1:max.seq)
plot(x = x, y = counter, type = 'p', col = "red",
     main = "\"erste 6 nach n Würfen\"", xlab = "n", ylab = "P(n)")
# theoretische Werte
points(x = x, geom(prob = 1/6, number = max.seq), type = 'h', col = "blue")
# Nulllinie
lines(x = c(0, max.seq), y = c(0, 0), col = "green")

max.seq
# [1] 54

which(counter == 0)
# [1] 42 45 46 47 48 49 51 52

Zur Erklärung:

Zeile 1: Beim brute-force-Algorithmus wurden 10 000 Zufallsfolgen untersucht. Wenn im Durchschnitt alle 6 Würfe eine 6 erscheint, werden 60 000 Würfe etwa in 10 000 Teilfolgen zerhackt.

Zeile 3 bis 12: Sollten nach den vorbereitenden Erläuterungen klar sein.

Zeile 14: Die längste Teilfolge bestimmt, wie viele Zähler nötig sind. Die Komponenten von diff geben gerade die Länge der Teilfolgen an.

Zeile 16 bis 19: Der Schleife durchläuft alle Komponenten des Vektors diff; und jede dieser Komponente steht für eine Teilfolge. Der Wert einer Komponente von diff ist die Länge der Teilfolge (sie wird im Skript mit lgth bezeichnet). Der zugehörige Zähler, also counter[lgth] muss um 1 hochgezählt werden.

Zeile 21 bis 34: Die Zähler werden wieder so normiert, dass sie relative Häufigkeiten angeben. Das Diagramm wird wie im brute-force-Algorithmus erstellt (siehe Abbildung 4).

Zeile 24: Die Ausgabe zeigt, dass in diesem Beispiel 10 021 Teilfolgen untersucht wurden.

Zeile 36: Die längste Teilfolge hatte eine Länge 54.

Zeile 39: Hier wird ausgegeben, welche Zähler noch bei 0 stehen (im Diagramm ist dies nicht eindeutig erkennbar).

Abbildung 4: Diagramm zum verbesserten Algorithmus aus obigem Skript: Blau ist das Histogramm mit den theoretischen Wahrscheinlichkeiten (geometrische Verteilung), rot die relativen Häufigkeiten, die aus der Zufallsfolge gewonnen wurden, grün die Nulllinie.

Aufgaben:

1. Führen Sie den brute-force-Algorithmus und den verbesserten Algorithmus aus und entscheiden Sie, ob die gezeigten Resultate typisch sind oder – in irgendeinem Sinne – spezielle Ergebnisse zeigen.
2. Schreiben Sie den verbesserten Algorithmus zu einer Funktion um mit zwei Eingabewerten:

• die Treffer-Wahrscheinlichkeit p,
• die Länge der Zufallsfolge length.trial.