Zufallsexperimente und Wahrscheinlichkeitsanalyse: Ein Leitfaden zu CS 6140 Aufgaben 1–6

Einleitung: Warum Zufallsexperimente in der Datenwissenschaft unverzichtbar sind

Zufallsexperimente begegnen uns überall: von der Generierung kryptografischer Schlüssel über die Simulation von Wartezeiten in Warteschlangen bis hin zur Analyse von Hash-Kollisionen in großen Datenbanken. In diesem Tutorial tauchen wir tief in die Welt der diskreten Wahrscheinlichkeitsrechnung ein, wie sie in den Aufgaben 1 bis 6 des Kurses CS 6140 behandelt wird. Du wirst lernen, wie du mit randomisierten Algorithmen umgehst, empirische Ergebnisse mit analytischen Formeln vergleichst und deine Implementierungen effizient gestaltest. Egal, ob du gerade für deine Hausaufgaben in Stochastik lernst oder dich auf eine Karriere als Data Scientist vorbereitest – diese Konzepte sind fundamental.

Geburtstagsparadoxon und Kollisionsexperimente

Das Geburtstagsparadoxon besagt, dass in einer Gruppe von nur 23 Personen die Wahrscheinlichkeit, dass zwei am selben Tag Geburtstag haben, bereits über 50 % liegt. In der Informatik nutzen wir dieses Prinzip, um die Wahrscheinlichkeit von Kollisionen in Hashfunktionen zu verstehen. Stell dir vor, du generierst Zufallszahlen aus einem Bereich n = 3000 (z. B. User-IDs in einer App). Die Frage ist: Wie viele Zufallszahlen musst du ziehen, bis zwei identisch sind? Diese Anzahl nennen wir k. In der Praxis wird dies relevant, wenn du etwa eindeutige Tokens für eine Login-Sitzung erstellst oder Deduplizierung in großen Datensätzen durchführst.

Empirische Bestimmung von k

Führe das Experiment m = 300 Mal durch und notiere jedes Mal die Anzahl der Versuche k. Ein Python-Skript könnte so aussehen:

import random
import matplotlib.pyplot as plt

n = 3000
m = 300
k_values = []
for _ in range(m):
    seen = set()
    k = 0
    while True:
        num = random.randint(1, n)
        k += 1
        if num in seen:
            k_values.append(k)
            break
        seen.add(num)

Die kumulative Dichtefunktion (CDF) zeigt den Anteil der Experimente, die nach k Versuchen eine Kollision hatten. Der Erwartungswert E[k] wird empirisch als Mittelwert aller k berechnet. Für n=3000 liegt dieser typischerweise bei etwa 68–70, was der theoretischen Erwartung von ≈ sqrt(πn/2) ≈ 68,4 nahekommt.

Sammelbildproblem: Alle Werte sammeln

Das Sammelbildproblem (Coupon Collector Problem) ist dir vielleicht von Panini-Stickern zur EM 2024 oder von Ingame-Loot-Boxen in Fortnite bekannt. Wie viele zufällige Ziehungen brauchst du, um alle n verschiedenen Objekte mindestens einmal zu erhalten? Für n=100 – etwa 100 verschiedene Pokémon-Karten – ist die erwartete Anzahl k etwa n * H_n ≈ 100 * 5,187 ≈ 519.

Empirische Simulation und CDF

Simuliere das Sammeln für n=100, m=300 Wiederholungen:

n = 100
m = 300
k_values = []
for _ in range(m):
    collected = set()
    k = 0
    while len(collected) < n:
        num = random.randint(1, n)
        k += 1
        collected.add(num)
    k_values.append(k)

Die CDF zeigt, dass nach etwa 1000 Versuchen fast alle Experimente erfolgreich sind. Der empirische Erwartungswert sollte nahe an 519 liegen. Ein Vergleich mit der analytischen Formel hilft, Fehler in der Implementierung zu erkennen – ein wichtiger Schritt beim Debugging von Simulationen.

Analytische Berechnungen: Formeln und Herleitungen

Die Theorie liefert uns mächtige Werkzeuge, um Erwartungswerte ohne Simulation zu berechnen. Für das Geburtstagsparadoxon gilt: Die Wahrscheinlichkeit für eine Kollision nach k Versuchen ist P(Kollision) ≈ 1 - exp(-k(k-1)/(2n)). Setzt man diese gleich 0,5 und löst nach k auf, erhält man k ≈ sqrt(2n * ln(2)) ≈ sqrt(2*3000*0,693) ≈ 64,5. Dein empirischer Wert aus Aufgabe 1.C sollte in dieser Größenordnung liegen – Abweichungen deuten auf Implementierungsfehler hin.

Für das Sammelbildproblem ist der Erwartungswert E[k] = n * H_n, wobei H_n die harmonische Zahl ist. Für n=100 ergibt sich 100 * (1 + 1/2 + ... + 1/100) ≈ 518,7. Vergleiche dies mit deinem empirischen Mittelwert aus Aufgabe 2.C – eine Diskrepanz von mehr als 5 % sollte dich stutzig machen.

Erzeugung von Zufallszahlen aus Bits

Oft hast du nur eine Funktion rand-bit(), die 0 oder 1 mit gleicher Wahrscheinlichkeit liefert. Wie erzeugst du daraus eine gleichverteilte Zufallszahl zwischen 1 und n? Für n=1024 (eine Zweierpotenz) ist es einfach: Generiere 10 Bits und interpretiere sie als Binärzahl (0–1023), addiere 1. Für n=1000 benötigst du einen Las-Vegas-Algorithmus: Generiere 10 Bits (ergibt 0–1023), verwerfe Werte über 999 und wiederhole, bis ein gültiger Wert erscheint. Die erwartete Anzahl Aufrufe von rand-bit() ist 10 / (1000/1024) ≈ 10,24. Allgemein: Für beliebiges n wähle die kleinste Zweierpotenz 2^b ≥ n und verwende das Rejection-Sampling. Die erwarteten Bit-Aufrufe sind b / (n/2^b) – ein wichtiger Aspekt, wenn Zufallsbits teuer sind, z. B. in Hardware-Sicherheitsmodulen.

Gleichmäßigkeit der Verteilung: Das Maximum der relativen Häufigkeiten

Angenommen, du ziehst k Zufallszahlen aus [n] und betrachtest die relativen Häufigkeiten f_i/k. Sei µ = max_i f_i/k. Wie groß muss k sein, damit |µ - 1/n| < 0,01 mit Wahrscheinlichkeit 1-δ? Mit der Chernoff-Schranke erhält man k ≥ (3/ε^2) * ln(2n/δ). Für ε=0,01 und δ=0,05 ergibt sich k ≈ 30000 * ln(120000) ≈ 30000 * 11,7 ≈ 351.000. Für ε=0,001 steigt k auf etwa 35 Millionen. Dies zeigt, wie schnell die Anforderungen an die Stichprobengröße wachsen, wenn du eine hohe Genauigkeit benötigst – relevant für A/B-Tests in der App-Entwicklung oder Qualitätskontrollen in der Fertigung.

Ähnlichkeit von Dokumenten mit k-Grammen und Min-Hashing

Ein weiteres spannendes Thema ist die Ähnlichkeitsanalyse von Texten, wie sie in Aufgabe 6 behandelt wird. Du zerlegst Dokumente in k-Gramme (z. B. 2-Gramme auf Zeichenebene: „ab“, „bc“, …) und berechnest die Jaccard-Ähnlichkeit zwischen zwei Dokumenten als |A ∩ B| / |A ∪ B|. Für große Dokumente ist dies aufwändig, daher verwendet man Min-Hashing: Mit t Hashfunktionen erstellst du Signaturen und schätzt die Ähnlichkeit als Anteil gleicher Signaturkomponenten. Ein guter Wert für t ist 100–200, da dies einen guten Kompromiss zwischen Genauigkeit und Rechenzeit bietet – ähnlich wie bei Empfehlungssystemen für Netflix oder Plagiatserkennung in Unis.

Laufzeitanalyse und Optimierung

Wenn du n und m erhöhst, wächst die Laufzeit deiner Simulationen. Für n=1.000.000 und m=10.000 kann eine naive Implementierung Minuten dauern. Verwende daher effiziente Datenstrukturen wie Sets (O(1) für Einfügen und Testen) und vermeide teure Operationen. Ein Plot der Laufzeit in Abhängigkeit von n für verschiedene m zeigt, dass die Komplexität etwa O(m * sqrt(n)) für das Kollisionsexperiment ist. Solche Laufzeitanalysen sind entscheidend, wenn du Big-Data-Simulationen in der Cloud durchführst oder Echtzeit-Algorithmen für KI-Anwendungen entwickelst.

Fazit

Die Kombination aus empirischen Experimenten und analytischen Formeln ist ein mächtiges Werkzeug, um Zufallsprozesse zu verstehen und Fehler in Implementierungen zu finden. Ob du nun das Geburtstagsparadoxon für sichere Passwörter nutzt, Sammelbildprobleme in Gamification-Apps löst oder Dokumentähnlichkeit mit Min-Hashing bestimmst – die Prinzipien bleiben gleich. Übe diese Konzepte, indem du eigene Simulationen schreibst und die Ergebnisse mit den theoretischen Werten vergleichst. Viel Erfolg bei deinen Aufgaben!