Startseite Mathematik-Online        Themenliste

Mathematik-Online

Welche von zehn Sekretärinnen stellt man ein, wenn noch während des Vorstellungsgesprächs die Zusage erfolgen soll. Es geht also darum, unter einer vorgegebenen Anzahl nacheinander ablaufender Gelegenheiten, deren Rangordnung vollkommen unbestimmt ist, die beste Gelegenheit auswählen. Bei der jeweiligen Begutachtung ist eine sofortige Entscheidung erforderlich, sonst ist die Chance für immer vertan.

Sekretärinnenproblem

Anfrage: Florian Jensch, gmx
Eine Woche lang wird täglich in einer Spielshow eine beliebige Zufallszahl gezogen. Der Kandidat soll erraten, welche die größte ist und muss sich sofort entscheiden, ob er auf die soeben ausgeloste Zahl setzen möchte oder nicht. Gibt es eine effektive Strategie, und wenn ja, wie groß sind dann die Gewinnchancen? Wie lautet die allgemeine Strategie, wenn also zum Beispiel vier Wochen oder ein Jahr lang gelost wird?

Antwort:

Bei sieben Tagen (Ziehungen) wartet man die ersten zwei Ziehungen ab. Sobald danach eine größere Zahl gezogen wird, wählt man diese. Die Gewinnchance beträgt dann rund 41%.

Bei einer beliebigen Anzahl von n > 1 Ziehungen liefert die kleinste ganze Zahl j > 0 mit 1/j+1 + 1/j+2 + ... + 1/n-1 ≤ 1 die optimale Wartezeit, wobei j nahe bei 0,37n liegt und die Erfolgsquote mit wachsendem n gegen rund 37% strebt.



Mathematik-Online, Sekretärinnenproblem


Bemerkung:

Wir leiten jetzt die obige Lösungsstrategie her und gehen dabei von einer beliebigen Anzahl n von Tagen aus, wobei man dafür auch allgemeiner die Bezeichnung "Objekte" oder "Gelegenheiten" wählen kann:

Die Wahrscheinlichkeit, die optimale Wahl zu treffen, hängt von der Anzahl j der Tage ab, an denen man nur beobachtet. Für jedes k ∈ {j+1,...,n} sei Ak das Ereignis, dass I) der k-te Tag Tk der beste ist und II) Tk ausgewählt wird. Die Wahrscheinlichkeit von I) beträgt 1/n, und die Wahrscheinlichkeit von II) beträgt j/(k-1), weil Tk genau dann ausgewählt wird, wenn sich der beste der ersten k-1 Tage unter den ersten j Tagen befindet. Das Ereignis Ak tritt also mit der Wahrscheinlichkeit P(Ak) = 1/n·j/(k-1) ein. Die besagte Strategie, exakt j Tage lediglich zu beobachten, ist genau dann erfolgreich, wenn Aj+1∪ Aj+2 ∪ ... ∪ An eintritt. Weil die Ereignisse Aj+1,  Aj+2,  ...  An paarweise disjunkt sind, erhalten wir für alle j mit 1 ≤ j < n die zugehörige Erfolgswahrscheinlichkeit:
Pj : = P(Aj+1) + P(Aj+2) + ... + P(An) = j/n·(1/j + ... + 1/n-1).
Die Differenz Pj - Pj+1 = 1/n ·(1 - 1/j+1 - 1/j+2 - ... - 1/n-1) wächst für alle j streng monoton und ist nichtnegativ für hinreichend große Zahlen j. Folglich ergibt die kleinste Zahl j mit 1/j+1 + 1/j+2 + ... + 1/n-1 ≤ 1 die optimale Wartezeit, die wir mit jo bezeichnen. Gemäß der obigen Ausführungen ist dann Pjo = jo/n·(1/jo + ... + 1/n-1) die maximale Erfolgswahrscheinlichkeit.


Mathematik-Online, Sekretärinnenproblem


Diese Wahrscheinlichkeit und die zugrunde liegende optimale Wartezeit jo kann man auch näherungsweise mit O(n):= 1/j + 1/j+1 + ... + 1/n-1 , U(n):= 1/j+1 + 1/j+2 + ... + 1/n und der Differenz O(n) - U(n) = 1/j - 1/n berechnen: Für den Inhalt A der Fläche, die der Graph von 1/x mit der x-Achse von j bis n einschließt, gilt die Abschätzung
U(n)   <   A = j n ∫dx/x = log n - log j = log n/j   <   O(n).


Untersumme U(n) und Obersumme O(n)

Daraus folgt: O(n) - log n/j < O(n) - U(n), also gilt: j/n·O(n) - j/n·log n/j < 1/n. Damit können wir alle Wahrscheinlichkeiten Pj = j/n·O(n) anhand der Funktion f mit f(x) = x·log(1/x) für hinreichend große Zahlen n recht genau berechnen. Weil f zudem stetig ist, liefert uns der maximale Wert von f also näherungsweise die gesuchte Wahrscheinlichkeit Pjo - und zwar wie folgt: f′′(x) = -1/x ist für alle x > 0 negativ, demnach ist f konkav. Die Nullstelle x = 1/e der ersten Ableitung liefert daher das gesuchte Maximum f(1/e) = 1/e der Funktion f. Im Falle großer Zahlen n ist somit 1/e = 0,3678... eine gute Näherung für unsere maximale Erfolgswahrscheinlichkeit Pjo - und natürlich auch für jo/n.

Wenn eine geeignete Situation mit „vielen Gelegenheiten” vorliegt, sollte man also knapp 37% lediglich prüfen und dann bei der nächsten besseren Gelegenheit zugreifen. Die Erfolgsquote dieser Strategie beträgt fast 37%.
Themenliste Ziegenproblem