🎯 Secretary Problem Simulation

Optimale Stopping-Strategie bei sequenzieller Auswahl

📋 Das Secretary Problem

Szenario: Sie mĂŒssen aus n Bewerbern den besten auswĂ€hlen. Die Bewerber erscheinen nacheinander in zufĂ€lliger Reihenfolge. Nach jedem GesprĂ€ch mĂŒssen Sie sofort entscheiden: annehmen oder ablehnen (keine RĂŒckkehr zu frĂŒheren Kandidaten).

Ziel: Finden Sie eine Strategie, die die Wahrscheinlichkeit maximiert, den besten Kandidaten auszuwÀhlen!

100
9
0%

đŸ§Ș Didaktische Aufgaben

Aufgabe 1: Die naive Strategie verstehen

Schwierigkeit: ⭐

Setze k=0 und fĂŒhre mehrere Einzelsimulationen durch.

  • Was passiert bei k=0? Welcher Kandidat wird gewĂ€hlt?
  • FĂŒhre eine Monte-Carlo-Simulation mit 10.000 DurchlĂ€ufen durch. Welche Erfolgsrate erreichst du?
  • ErklĂ€re mathematisch, warum diese Erfolgsrate genau 1/n entspricht.

Aufgabe 2: Zu viel Exploration

Schwierigkeit: ⭐

Setze n=10 und k=9.

  • Was ist das Problem dieser Strategie?
  • Welcher Kandidat wird zwangslĂ€ufig gewĂ€hlt?
  • Vergleiche die Erfolgsrate mit k=0. Was fĂ€llt auf?

Aufgabe 3: Empirische Optimumssuche

Schwierigkeit: ⭐⭐

Finde fĂŒr n=10 das beste k durch systematisches Ausprobieren.

  • Teste verschiedene Werte von k (z.B. 1, 2, 3, 4, 5) mit je 10.000 Simulationen
  • Notiere die Erfolgsraten und erstelle eine Tabelle
  • Bei welchem k ist die Erfolgsrate am höchsten?
  • Vergleiche mit der theoretischen Vorhersage k=n/e≈3,68. Stimmt es?

Aufgabe 4: Skalierungsverhalten

Schwierigkeit: ⭐⭐

Untersuche, wie sich die Strategie mit wachsendem n verhÀlt.

  • FĂŒhre Monte-Carlo-Simulationen fĂŒr n=5, 10, 20, 30 durch (jeweils mit optimalem k)
  • Konvergiert die Erfolgsrate gegen einen festen Wert? Welchen?
  • Schaue dir den "Erfolgsrate nach k"-Graphen an. Was passiert mit der Form der Kurve?

Aufgabe 5: RMSE vs. Erfolgsrate

Schwierigkeit: ⭐⭐⭐

Vergleiche die beiden Optimierungsziele.

  • FĂŒr n=20: Finde das optimale k fĂŒr (a) maximale Erfolgsrate und (b) minimalen RMSE
  • Sind die beiden Optima gleich? Falls nicht, warum?
  • Welche Strategie wĂŒrdest du wĂ€hlen, wenn du "gut genug" wichtiger findest als "perfekt"?
  • Berechne fĂŒr beide Optima die Top-3-Rate. Was fĂ€llt auf?

Aufgabe 6: Verteilungsanalyse

Schwierigkeit: ⭐⭐

Analysiere die Rangverteilung bei n=10, k=4.

  • FĂŒhre 50.000 Simulationen durch
  • Welche RĂ€nge kommen am hĂ€ufigsten vor?
  • Schaue dir die kumulierte Verteilung an: Mit welcher Wahrscheinlichkeit erhĂ€ltst du mindestens einen Top-5-Kandidaten?
  • Ist die Verteilung symmetrisch oder schief?

Aufgabe 7: Worst-Case-Analyse

Schwierigkeit: ⭐⭐

Untersuche, wie oft man die schlechtesten Kandidaten erwischt.

  • Bei n=10, k=4: Wie oft wird Rang 10 (der schlechteste) gewĂ€hlt?
  • Wie oft einer der drei schlechtesten (Rang 8-10)?
  • Vergleiche mit k=0 und k=9. Wann ist das Worst-Case-Risiko am höchsten?

Aufgabe 8: Strategievergleich

Schwierigkeit: ⭐⭐⭐

Vergleiche drei Strategien systematisch bei n=20:

  • Strategie A: k=0 (naive Strategie)
  • Strategie B: k=7 (optimal fĂŒr Erfolgsrate)
  • Strategie C: k=5 (konservativ)

Erstelle eine Vergleichstabelle mit: Erfolgsrate, RMSE, Top-3-Rate, Durchschnittsrang, Medianrang

Welche Strategie wĂŒrdest du in der Praxis empfehlen? BegrĂŒnde!

Aufgabe 9: Kleines n - große Abweichungen

Schwierigkeit: ⭐⭐⭐

Die 37%-Regel ist asymptotisch (fĂŒr n→∞). Was passiert bei kleinem n?

  • FĂŒr n=3: Was ist k=n/e? Runde auf die nĂ€chste ganze Zahl. Teste alle k∈{0,1,2}.
  • Ist das gerundete k=n/e wirklich optimal?
  • Wiederhole fĂŒr n=5, 7, 10, 15, 20, 30
  • Ab welchem n wird die 37%-Regel zuverlĂ€ssig?

Aufgabe 10: Anwendung - Wohnungssuche

Schwierigkeit: ⭐⭐⭐

Szenario: Du suchst eine Wohnung und kannst 20 Besichtigungen machen. Du musst dich nach jeder Besichtigung sofort entscheiden (ja/nein), kannst nicht zurĂŒck zu frĂŒheren Wohnungen.

  • Wie viele Wohnungen solltest du "nur anschauen" (Exploration)?
  • Mit welcher Wahrscheinlichkeit findest du die beste Wohnung?
  • Angenommen, du wĂŒrdest auch mit einer der Top-3-Wohnungen zufrieden sein - wie hoch ist diese Wahrscheinlichkeit?
  • Welche EinschrĂ€nkungen hat das Modell in der RealitĂ€t? (z.B. keine perfekte Vergleichbarkeit, emotionale Faktoren, Zeitdruck)

💡 Tipps zur Bedienung

  • Einzelsimulation: Visualisiert einen einzelnen Durchlauf. Gelb = Exploration, Rot = abgelehnt, GrĂŒn = gewĂ€hlt, Hellblau = tatsĂ€chlich Bester
  • Monte-Carlo: FĂŒhrt viele Simulationen durch und zeigt statistische Auswertungen
  • Tooltips: Fahre mit der Maus ĂŒber die Balken im Histogramm, um genaue Prozentwerte zu sehen
  • Graphen nebeneinander: Auf großen Bildschirmen werden die Graphen nebeneinander angezeigt
  • Mobile: Die Simulation ist vollstĂ€ndig touchfĂ€hig und optimiert fĂŒr Smartphones

📚 Mathematische Konzepte & Lehrplanbezug

đŸŽČ Gesetz der großen Zahlen

Beobachtung: FĂŒhre dieselbe Simulation mehrmals durch:

  • Mit 100 DurchlĂ€ufen: Die Erfolgsrate schwankt stark (z.B. zwischen 35% und 43%)
  • Mit 10.000 DurchlĂ€ufen: Die Erfolgsrate stabilisiert sich (z.B. um 40%)
  • Mit 100.000 DurchlĂ€ufen: Die Erfolgsrate konvergiert gegen den theoretischen Wert

Konzept: Die empirische Wahrscheinlichkeit (relative HÀufigkeit) nÀhert sich bei wachsender Anzahl von Versuchen der theoretischen Wahrscheinlichkeit an.

Didaktischer Wert: Visualisierung des abstrakten Konzepts durch direkte Erfahrung. Das Konfidenzintervall zeigt die Unsicherheit bei endlichen Stichproben.

📊 Verschiedene OptimierungsansĂ€tze

Problem: Was bedeutet "optimal"? Das hÀngt vom Ziel ab!

1. Maximierung der Erfolgsrate

  • Ziel: P(Rang = 1) maximieren
  • Optimal: k ≈ n/e
  • Charakteristik: "Alles oder nichts" - entweder der Beste oder oft mittelmĂ€ĂŸig
  • Anwendung: Wenn nur das Optimum zĂ€hlt (z.B. Sportwettbewerbe)

2. Minimierung des RMSE

  • Ziel: √(E[(Rang-1)ÂČ]) minimieren
  • Optimal: Oft kleineres k als bei Erfolgsrate
  • Charakteristik: Bestraft große Fehler ĂŒberproportional
  • Anwendung: Wenn Katastrophen vermieden werden sollen

3. Maximierung der Top-X-Rate

  • Ziel: Wahrscheinlichkeit fĂŒr Rang ≀ X maximieren
  • Optimal: AbhĂ€ngig von X
  • Charakteristik: "Gut genug" statt "perfekt"
  • Anwendung: Realistische Szenarien mit Zufriedenheitsschwelle

Didaktischer Wert: Zeigt, dass Optimierung kontextabhĂ€ngig ist. Verschiedene Zielfunktionen fĂŒhren zu verschiedenen optimalen Strategien. Wichtig fĂŒr Modellierungskompetenz!

📏 Streuungsmaße: Von der Spannweite zur Standardabweichung

Motivation ĂŒber das Secretary Problem:

Schritt 1: Spannweite (intuitiv, aber unzureichend)

Bei n=10 und verschiedenen k sehen wir: Die RÀnge streuen zwischen 1 und 10. Aber die Spannweite ist immer gleich (9) - wenig aussagekrÀftig!

Schritt 2: Mittlere absolute Abweichung (MAD)

Besser: Wie weit sind die RĂ€nge im Durchschnitt vom optimalen Rang (1) entfernt?

MAD = E[|Rang - 1|] = Durchschnittsrang - 1

Hinweis: Diese Metrik zeigt die Simulation bereits an als "Durchschn. Rang"! MAD ist einfach dieser Wert minus 1.

Problem: Behandelt kleine und große Fehler gleich. Ist Rang 2 wirklich so schlimm wie der Unterschied zwischen Rang 9 und 10?

Schritt 3: RMSE / Standardabweichung (besser!)

Die quadratische Abweichung bestraft große Fehler stĂ€rker:

RMSE = √(E[(Rang-1)ÂČ])

Beispiel bei n=10:

Rang Abweichung Quadr. Abw.
1 (optimal) 0 0
2 (gut) 1 1
5 (mittelmĂ€ĂŸig) 4 16 ← 4× so schwer!
10 (katastrophal) 9 81 ← 81× so schwer!

Didaktischer Wert:

  • Motiviert die Notwendigkeit von Streuungsmaßen durch konkretes Problem
  • Zeigt Grenzen einfacher Maße (Spannweite, MAD)
  • Macht die Idee der "Fehlerquadrate" intuitiv: Große Fehler sind viel schlimmer!
  • Verbindung zu MSE/Varianz in der Statistik und zu kleinsten Quadraten in der Analysis
  • Die Standardabweichung ist nicht nur Formel, sondern hat praktische Bedeutung

🎯 Weitere LehrplanbezĂŒge

  • Stochastik: Erwartungswert, Varianz, Verteilungen, Konfidenzintervalle
  • Analysis: Grenzwerte (n→∞), Optimierung, Eulersche Zahl e
  • Algorithmik: Sequenzielle Entscheidungen, Greedy-Algorithmen
  • Modellierung: Vereinfachung realer Probleme, Annahmen kritisch hinterfragen
  • Numerik: Monte-Carlo-Methoden zur Approximation theoretischer Werte

🎯 Die optimale Strategie

Zweiphasen-Strategie:

  1. Explorationsphase (erste k Kandidaten):
    • Beobachte die ersten k Kandidaten
    • Merke dir den besten Wert aus dieser Phase
    • Lehne alle ab (keine Entscheidung treffen)
  2. Selektionsphase (Kandidaten k+1 bis n):
    • WĂ€hle den ersten Kandidaten, der besser ist als alle in der Explorationsphase
    • Falls keiner besser ist: Nimm den letzten Kandidaten

📐 Die mathematische Lösung:

Optimales k: k ≈ n/e ≈ 0,368 · n

Erfolgswahrscheinlichkeit: P(Erfolg) ≈ 1/e ≈ 37%

FĂŒr n→∞ konvergiert die optimale Strategie zur 37%-Regel