Wir lassen uns heute mit dem Thema

Average Case Analysen, wo wir also wie der Name sagt uns damit befassen werden, wie lange benötigt

ein Algorithmus im Durchschnitt für die Eingaben, die wir ihm so vorwerfen. Ja, das verlangt natürlich

so ein bisschen Wahrscheinlichkeitstheorie. Wenn ich sage Durchschnitt, dann heißt das,

ich rechne damit, dass die Eingaben in irgendeiner Form zufällig ausgewählt werden und rede dann

also in Wirklichkeit über die Erwartungswerte von Größen wie eben Speicherverbrauch und Laufzeit.

Deswegen machen wir den größten Teil der heutigen Sitzung in Wirklichkeit Wiederholung von Wahrscheinlichkeitstheorie.

Beziehungsweise, weil wir uns nicht mit so bösen Dingen wie Maaßen und Sigma-Algebren und Ähnlichem

auseinandersetzen werden, sondern nur mit diskreten Wahrscheinlichkeitsverteilungen wird also der

durchschnittliche Statistiker insistieren, dass ich hier Wahrscheinlichkeitsrechnung sage und nicht

Wahrscheinlichkeitstheorie. Ja, der Grundbegriff der Wahrscheinlichkeitsrechnung ist der der

Wahrscheinlichkeitsverteilung, in diesem Fall eben der diskreten Wahrscheinlichkeitsverteilung.

Diskrete Wahrscheinlichkeitsverteilungen lassen sich sehr einfach definieren.

Und zwar definiere ich eine Wahrscheinlichkeitsverteilung zunächst einmal sehr pauschal als eine Funktion von

einem Ergebnisraum, so nennen wir das Ding Omega in die realen Zahlen, destungsweise genauer gesagt in

das Intervall 0,1. So das Folgendes gilt, wenn ich über alle Omega, Klein-Omega aus Groß-Omega,

also über alle Ergebnisse summiere, eben diese Funktion P von Omega, dann kommt eins raus. So,

ja, noch einen Schritt zurück, dreht ein bisschen Notation, nicht? Was passiert hier? Man ist ja

unendliche Summen gewohnt, ja, und hier summiere ich plötzlich über eine beliebige Menge, von der ich

noch nicht mal gesagt habe, dass sie abzählbar ist. Und ich sage nicht, in welcher Reihenfolge ich

summiere. Und man hat vielleicht so aus Ingmat noch im Kopf, dass das keine ganz irrelevante

Frage ist, in welcher Reihenfolge ich eine unendliche Summe summiere, aber dieses Ding hier,

das hat nur positive Summanden. In dem Fall ist es also tatsächlich egal, in welcher Reihenfolge ich

da summiere. Das heißt, ich kann mir solche Schreibweisen, dass ich also einfach über eine

unsortierte Menge summiere, leisten. Die nächste Frage ist, wie gehe ich damit um, dass diese

Menge im Zweifelsfalle nicht abzählbar ist? Und ich möchte das auch unterwegs tatsächlich benutzen,

also zum Beispiel kann es vorkommen, dass Omega die reellen Zahlen sind. Was meine ich damit?

Was damit gemeint ist, ist ein Supremo. Über alle teilen, endlichen Teilmengen dieser Menge,

über die ich da summiere, dieser Zahl hier, Summe über alle Omega aus dieser endlichen Teilmenge,

über p von Omega. Also mit anderen Worten, ich definiere als eine unendliche Summe,

als das Supremum ihrer endlichen Teilsumme. Das kann ich immer machen. Ich meine, man weiß

natürlich nicht, dass es endlich ist. Das Supremum kann unendlich sein, aber zunächst mal hinschreiben

kann ich das. Die Frage ist jetzt, wie das mit der Abzählbarkeit ist. Und man kann relativ leicht

zeigen, dass hier aus folgt, dass die Menge im Wesentlichen abzählbar ist. Natürlich will ich

gerade den Fall, dass sie nicht abzählbar ist. Was heißt im Wesentlichen? Naja, die Teile der

Menge, auf denen p nicht verschwindet, der ist abzählbar. Das heißt, die Menge aller

kleinen Omega aus Groß Omega, für die p von Omega echt positiv ist, die ist abzählbar.

Das folgt aus Endlichkeit dieser Summe. So, das ist also eine Wahrscheinlichkeitsverteilung.

Das ist nicht ganz das, was man normalerweise als Wahrscheinlichkeitsverteilung ansieht. Eine

Wahrscheinlichkeitsverteilung ist üblicherweise eine Menge, die als Argumente Teilmengen des

Ergebnisraums annimmt und nicht Elemente des Ergebnisraums. Die bekommen wir aber daraus.

Ein Ereignis, das ist der probabilistische Terminus dafür, ein Ereignis ist eine Teilmenge

des Ergebnisraums. Und zwar eben, weil wir eine diskrete Wahrscheinlichkeitsverteilung haben,

eine beliebige Teilmenge üblicher. Also wenn man wirklich stetige Verteilungen hat, dann muss man

sich bei den Ereignissen einschränken auf sogenannte messbare Mengen. Das ist hier nicht nötig. Wir

können also beliebige Teilmengen des Ergebnisraums als Ereignisse nehmen. Und für ein solches Ereignis

können wir jetzt die Wahrscheinlichkeit des Ereignisses definieren, p von a. Und die bekommen

wir, indem wir eben diese Funktion klein p über a summieren. Also die Summe über alle

kleinen Omega aus a der Zahl p von Omega. Gut. Normalerweise würde man Betrachtung über

Wahrscheinlichkeit damit beginnen, dass man ein paar elementare Axiome hinschreibt über