Startseite Mathematik-Online        Themenliste

Mathematik-Online

Wie erkennt man bei chaotischen Kursverläufen den besten Zeitpunkt, um entsprechende Aktien zu verkaufen? Mit welcher Strategie findet eine Frau den (im Rahmen ihrer Möglichkeiten) attraktivsten Mann? Welche von zehn Sekretärinnen stellt man ein, wenn die definitive Zusage noch während des Vorstellungsgespräches erfolgen soll? Oft ist es schwierig, für derartige Probleme wirkungsvolle Strategien zu entwickeln. Falls die Situation jedoch folgendermaßen klar strukturiert ist, bietet sich sofort ein optimales und einfaches Lösungsverfahren an:

Unter einer gegebenen Anzahl nacheinander ablaufender Gelegenheiten, deren Rangordnung vollkommen unbestimmt ist, will man einzig und allein die beste Gelegenheit auswählen. Bei der jeweiligen Begutachtung ist eine sofortige Entscheidung erforderlich - sonst ist die Chance für immer vertan. Diese universelle Problemstellung ist übrigens nach den bereits erwähnten Sekretärinnen benannt.

Sekretärinnenproblem

Anfrage: Florian Jensch, gmx
Eine Woche lang wird täglich eine Zufallszahl gezogen. Wer errät, welche der 7 Zahlen die größte ist, gewinnt eine Trekking-Tour zum Yukon. Der Spieler darf nur eine Zahl wählen 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 gehe ich vor, wenn zum Beispiel vier Wochen oder ein Jahr lang gelost wird?

Antwort:

Im Falle von 7 Tagen 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 wollen jetzt die oben beschriebene Lösungsstrategie exakt begründen und gehen dabei von einer beliebig großen aber festgewählten Anzahl n von Tagen, Objekten, Gelegenheiten etc. aus. Der Anschaulichkeit halber wählen wir die Notation „Tage”.

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 bequem näherungsweise berechnen. Das werden wir nun ausführlich darlegen und betrachten hierzu die beiden Summen O(n):= 1/j + 1/j+1 + ... + 1/n-1  und  U(n):= 1/j+1 + 1/j+2 + ... + 1/n. Wir erhalten die Gleichung: O(n) - U(n) = 1/j - 1/n. Ferner gilt für den Inhalt A der Fläche, die der Graph von 1/x mit der x-Achse von j bis n einschließt, 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