Diese Seite ist die Rechenseite zur 37-Prozent-Regel. Wer nur die Idee sucht, ist dort besser aufgehoben. Hier geht es um die Frage, woher die Zahl kommt, und um die genauen Werte für kleine Kandidatenzahlen, die man in populären Texten meistens nur gerundet oder gar nicht findet.
Die Spielregeln
Die klassische Fassung des Problems hat fünf Bedingungen, und jede davon wird gebraucht.
Es gibt genau n Kandidaten, und n ist vorher bekannt. Die Kandidaten erscheinen einzeln in zufälliger Reihenfolge, jede der n! Reihenfolgen ist gleich wahrscheinlich. Nach jedem Gespräch kennt man nur die relative Rangfolge unter den bisher gesehenen, also ob der aktuelle Kandidat besser ist als alle vorherigen oder nicht. Absolute Noten gibt es nicht. Nach jedem Gespräch muss man sofort entscheiden: annehmen, dann ist das Verfahren beendet, oder ablehnen, dann ist dieser Kandidat für immer weg. Gewonnen hat man nur, wenn man den insgesamt besten erwischt.
Unter diesen Bedingungen kommt nur eine bestimmte Sorte Strategie infrage. Einen Kandidaten anzunehmen, der nicht besser ist als alle vorherigen, ist sinnlos, denn er kann dann nicht der Beste sein. Man nimmt also immer einen „relativ Besten“. Man kann zeigen, dass es optimal ist, eine Schwelle festzulegen: Die ersten r − 1 Kandidaten werden grundsätzlich abgelehnt, danach nimmt man den ersten relativ Besten. Die Begründung in einem Satz: Ist der i-te Kandidat relativ Bester, dann ist er mit Wahrscheinlichkeit i/n auch absolut Bester, und diese Zahl wächst mit i, während die Aussichten beim Weitermachen mit i schrumpfen. Irgendwo kreuzen sich die beiden, und ab dort lohnt das Zugreifen.
Die Formel
Sei r die erste Position, an der man überhaupt zugreifen darf. Wir zerlegen das Ereignis „Erfolg“ danach, an welcher Stelle i der absolut Beste steht.
Steht er unter den ersten r − 1, hat man ihn abgelehnt, und es kommt keiner mehr, der ihn übertrifft. Kein Erfolg.
Steht er an Stelle i mit i ≥ r, dann nimmt man ihn genau dann, wenn man vorher niemanden genommen hat. Das ist genau dann der Fall, wenn der Beste unter den ersten i − 1 Kandidaten in der Beobachtungsgruppe sitzt, also unter den ersten r − 1. Hätte zwischen r und i − 1 jemand gestanden, der besser war als alle vor ihm, hätte man den bereits genommen. Da die Reihenfolge zufällig ist, liegt der Beste der ersten i − 1 mit Wahrscheinlichkeit (r − 1)/(i − 1) in dieser Gruppe.
Die Wahrscheinlichkeit, dass der absolut Beste an Stelle i steht, ist 1/n. Zusammen ergibt das
P(r) = Σ (i von r bis n) 1/n · (r − 1)/(i − 1) = (r − 1)/n · Σ (i von r bis n) 1/(i − 1),
für r ≥ 2. Für r = 1 nimmt man einfach den ersten und hat P(1) = 1/n.
Ein Beispiel mit n = 5 und r = 3, also zwei Kandidaten zum Anschauen: P(3) = 2/5 · (1/2 + 1/3 + 1/4) = 2/5 · 13/12 = 13/30 ≈ 0,433. Das ist das Optimum für fünf Kandidaten. Mit r = 2 kommt man auf 1/5 · (1 + 1/2 + 1/3 + 1/4) = 25/60 ≈ 0,417, mit r = 4 auf 3/5 · (1/3 + 1/4) = 0,35.
Der Grenzwert 1/e
Für große n setzt man x = (r − 1)/n, also den Anteil der Kandidaten, die man nur anschaut. Die Summe Σ 1/(i − 1) von i = r bis n ist eine Riemann-Summe und verhält sich wie das Integral von dt/t zwischen x und 1, also wie −ln x. Damit wird
P ≈ −x · ln x.
Ableiten und null setzen: −ln x − 1 = 0, also ln x = −1 und x = 1/e. Eingesetzt ergibt sich P = −(1/e) · (−1) = 1/e ≈ 0,3679. Beide Größen, der optimale Anteil und die Erfolgswahrscheinlichkeit, landen auf demselben Wert. Das ist kein Zufall, sondern folgt direkt aus der Form −x ln x, deren Maximum bei x = 1/e den Wert 1/e annimmt.
Nebenbei fällt eine unangenehme Größe ab. Die Wahrscheinlichkeit, am Ende gar niemanden zu nehmen, ist genau die Wahrscheinlichkeit, dass der Beste in der Beobachtungsgruppe war, also (r − 1)/n, für große n ebenfalls etwa 37 Prozent.
Nachgerechnet: die exakten Werte
Die folgende Tabelle habe ich nicht aus einem Buch abgeschrieben, sondern mit einem kleinen Programm aus der Formel oben ausgerechnet, für jedes r einzeln, und dann das beste r herausgesucht. Als Aktuar traut man keiner Tabelle, die man nicht selbst erzeugt hat, das ist eine Berufskrankheit.
| n | beste Schwelle r | davon nur ansehen (r − 1) | Anteil (r − 1)/n | Erfolgswahrscheinlichkeit P(r) |
|---|---|---|---|---|
| 5 | 3 | 2 | 0,40 | 0,4333 |
| 10 | 4 | 3 | 0,30 | 0,3987 |
| 20 | 8 | 7 | 0,35 | 0,3842 |
| 100 | 38 | 37 | 0,37 | 0,3710 |
Zwei Dinge fallen auf. Bei kleinen n ist die Erfolgschance deutlich besser als 1/e, sie sinkt mit wachsendem n langsam gegen 0,3679. Und das Optimum ist flach. Bei n = 10 liefert r = 5 immer noch 0,3983, also praktisch dasselbe wie r = 4. Bei n = 100 unterscheiden sich r = 37, 38 und 39 erst in der vierten Nachkommastelle. Wer sich um ein oder zwei Kandidaten verzählt, verliert fast nichts. Für Keplers elf Kandidatinnen, von denen auf der Seite zur 37-Prozent-Regel die Rede ist, ergibt die Rechnung übrigens r = 5 und P ≈ 0,398.
Woher das Problem stammt
Die Geschichte ist verworren, und ich verlasse mich hier auf den Aufsatz von Thomas S. Ferguson, „Who Solved the Secretary Problem?“, erschienen 1989 in Statistical Science (Band 4, Heft 3, S. 282 bis 289). Einem großen Publikum bekannt wurde die Aufgabe durch Martin Gardners Kolumne im Scientific American vom Februar 1960, damals als Spiel „Googol“ mit beschrifteten Zetteln. Nach der heute üblichen Darstellung hatte Merrill Flood das Problem schon um 1949 unter dem Namen „fiancée problem“ in Umlauf gebracht. Eine der ersten veröffentlichten Lösungen mit der Rückwärtsinduktion der dynamischen Programmierung stammt von Dennis Lindley (1961, Applied Statistics), eine elegante Behandlung als Markov-Stoppproblem von Eugene Dynkin (1963). Noch älter ist eine verwandte Lotterieaufgabe, die Arthur Cayley (Porträt oben) 1875 gestellt hat. Der deutsche Name „Sekretärinnenproblem“ ist eine Übersetzung des englischen „secretary problem“ und verrät vor allem etwas über das Arbeitsleben der sechziger Jahre.
Varianten, die das Ergebnis verändern
Kaum lockert man eine der fünf Bedingungen, ändert sich die Antwort, manchmal erheblich.
Volle Information. Sieht man statt der Rangfolge echte Zahlenwerte aus einer bekannten Verteilung, kann man besser planen. John Gilbert und Frederick Mosteller haben 1966 im Journal of the American Statistical Association gezeigt, dass die Erfolgswahrscheinlichkeit dann für große n gegen etwa 0,58 geht.
Erwarteter Rang statt Bestem. Chow, Moriguti, Robbins und Samuels (1964, Israel Journal of Mathematics) haben die Strategie gesucht, die den erwarteten Rang des Gewählten möglichst klein macht. Die optimale Regel senkt die Ansprüche schrittweise, und der erwartete Rang bleibt selbst für beliebig viele Kandidaten unter 3,87. Wer mit „sehr gut“ zufrieden ist, kommt also viel sicherer ans Ziel als jemand, der nur den Besten will.
Unbekanntes n. Kommen die Kandidaten zu zufälligen Zeitpunkten, gleichmäßig verteilt über einen festen Zeitraum, hilft die 1/e-Regel von F. Thomas Bruss (1984): Man lässt den Anteil 1/e der Zeit verstreichen und nimmt danach den ersten relativ Besten. Die Erfolgschance liegt dann bei mindestens 1/e, ganz gleich wie viele Kandidaten es werden.
Die Odds-Regel. Bruss hat im Jahr 2000 in den Annals of Probability ein allgemeines Verfahren veröffentlicht, das das klassische Problem als Spezialfall enthält. Man summiert von hinten die Chancen p/(1 − p), dass Kandidat i relativ Bester ist, und beginnt dort zuzugreifen, wo die Summe 1 erreicht. Für Position i ist p = 1/i, die Chance also 1/(i − 1). Bei n = 10 ergibt 1/9 + 1/8 + … + 1/4 knapp 0,996, erst mit 1/3 wird 1 überschritten, und so landet man wieder bei r = 4, wie in der Tabelle.
Ablehnung durch den Kandidaten. Nimmt jeder Kandidat das Angebot nur mit einer gewissen Wahrscheinlichkeit an, lohnt es sich, früher anzufangen. Für die Partnersuche ist das die wichtigste Variante, und sie führt direkt zu Modellen, in denen beide Seiten wählen. Das ist das Gebiet der stabilen Paare, das ich auf einer eigenen Seite beschreibe.
Die Originalaufsätze sind in der Quellenliste aufgeführt. Fergusons Aufsatz ist über Project Euclid abrufbar und für jeden lesenswert, der ein Semester Wahrscheinlichkeitsrechnung hinter sich hat.