Probabilistische Analyse
Probabilistische Analyse
Dieses Verfahren dient sowohl der Analyse der Laufzeit eines Algorithmus als auch dem Entwurf für effiziente Algorithmen. Dazu ist es nötig, Wissen über die Verteilung der Eingaben zu haben. Legt man diese zufällig fest mittelt man sozusagen die Laufzeit über alle Eingaben. Die Analyse nutzt dabei nur gleichverteilte Zufallszahlen, siehe Zufallszahlen erzeugen. Man verwendet zur Analyse so genannte Indikatorfunktionen, die im folgenden Abschnitt vorgestellt werden.
Indikatorfunktionen
Diese Funktionen beschreiben den Übergang zwischen Erwartungswerten und Wahrscheinlichkeiten. Als Voraussetzung betrachten wir einen gegebenen Wahrscheinlichkeitsraum S und ein Ereignis A. Die Indikatorfunktion I\{ A\}, welche mit dem Ereignis verknüpft ist wird definiert durch \begin{equation} I\{ A\}=\begin{cases} 1 & \text{falls A eintritt}\\ 0 & \text{falls A nicht eintritt} \end{cases} \end{equation} Als Beispiel verwenden wir den Wurf eines Würfels. Der Wahrscheinlichkeitsraum ist S=\{ 1,2,3,4,5,6\} mit Pr\{ 1\} =Pr\{ 2\} =Pr\{ 3\} =Pr\{ 4\} =Pr\{ 5\} =Pr\{ 6\} =\frac{1}{6}. Es soll eine Indikatorfunktion X_1 definiert werden, welche mit dem Ereignis "Eine 1 wird gewürfelt" verknüpft ist. \begin{equation} X_1=I\{ 1\}=\begin{cases} 1 & \text{falls 1 eintritt}\\ 0 & \text{falls 2,3,4,5,6 eintritt} \end{cases} \end{equation}
Die erwartete Anzahl, mit der das Ereignis "Eine 1 wird gewürfelt" eintritt, ist der Erwartungswert der Indikatorfunktion X_1.
\begin{equation} E[X_1]=E[I\{ 1\}] \end{equation} \begin{equation} =1\cdot Pr\{1\} + 0\cdot Pr\{ 2\} + 0\cdot Pr\{ 3\} + 0\cdot Pr\{ 4\} + 0\cdot Pr\{ 5\} + 0\cdot Pr\{ 6\} \end{equation} \begin{equation} =1 \cdot \frac{1}{6} + 5\cdot ( 0 \cdot \frac{5}{6}) \end{equation} \begin{equation} =\frac{1}{6} \end{equation}
Desweiteren ist der Erwartungswert dieser Indikatorfunktion X_1 gleich der Wahrscheinlichkeit für das Eintreten des mit dieser Funktion verknüpften Ereignisses, im Beispiel für "Eine 1 wird gewürfelt". Dies lässt sich allgemein als Lemma formulieren und beweisen.
Für einen gegebenen Wahrscheinlichkeitsraum S und ein Ereignis A \in S mit X_A = I\{A \} gilt: E[X_A]=Pr\{ A\}
\begin{equation} E[X_A]=E[I\{ A\}] \end{equation} \begin{equation} =1 \cdot Pr\{ A\} + 0 \cdot Pr\{ \bar{A}\} \end{equation} \begin{equation} =Pr\{ A\} \end{equation}
\bar{A} ist das Komplement von A, im Beispiel also \{ 2,3,4,5,6\}.
Für dieses Beispiel scheint die Indikatorfunktion ein wenig zuviel des Guten zu sein, doch für wiederholte Zufallsversuche ist sie sehr nützlich. Ein erweitertes Beispiel soll die Motivation für die Indikatorfunktion weiter erhöhen.
Berechnet werden soll die (erwartete) Anzahl der Ereignisse "Kopf" bei n Münzwürfen. Man kann dafür die Möglichkeiten (sprich Formeln) für Binomialverteilungen verwenden, betrachtet dabei die Wahrscheinlichkeit 0-mal Kopf, 1-mal Kopf usw. einzeln und hat einen komplizierten Rechenweg vor sich. Wesentlich einfacher ist dies mit der Indikatorfunktion. \begin{equation} X_i=I\{ \text{das Ergebnis des i-ten Wurfes ist Kopf}\} \end{equation} Außerdem sei die Zufallsvariable X die Gesamtanzahl der Ereignisse "Kopf" bei n Münzwürfen. X muss also gleich der Summe aller X_i von i=1 bis i=n sein: \begin{equation} X=\sum_{i=1}^{n}X_i \end{equation} Berechnet werden soll der Erwartungswert, also \begin{equation} E[X]=E[\sum_{i=1}^{n}X_i] \end{equation}
Den Erwartungswert jedes einzelnen X_i können wir berechnen, siehe obiges Lemma. Stellt sich nur noch die Frage, wie man die Summe von Erwartungswerten berechnet. Hier setzt ein Satz ein, welcher der probabilistischen Analyse mittels der Indikatorfunktion zu ihrer enormen Leistungsfähigkeit verhilft.
E[X+Y]=E[X]+E[Y]Der Erwartungswert einer Summe aus zwei Zufallsvariablen entspricht der Summe der beiden einzelnen Erwartungswerte (Linearität des Erwartungswertes). Damit sind alle Voraussetzungen geschaffen, um die (erwartete) Anzahl der Ereignisse "Kopf" bei n Münzwürfen zu berechnen.
\begin{equation} E[X]=E[\sum_{i=1}^{n}X_i] \end{equation} \begin{equation} =\sum_{i=1}^{n}E[X_i] \end{equation} \begin{equation} =\sum_{i=1}^{n}\frac{1}{2} \end{equation} \begin{equation} =\frac{n}{2} \end{equation}
- Wo stehen wir?
Wir sind in der Lage, Indikatorfunktionen für Ereignisse anzugeben und den Erwartungswert für diese Indikatorfunktion zu berechnen. Außerdem können wir für eine Folge von Zufallsversuchen den Erwartungswert für das mit der Indikatorfunktion verknüpfte Ereignis berechnen. Damit steht uns ein leistungsfähiges Werkzeug zur Verfügung, mit dem auch komplexere Probleme gelöst werden können. Ein solches soll nun betrachtet werden.