Die 37-%-Regel

Die Kandidaten erscheinen nacheinander in zufälliger Reihenfolge. Du kannst jede Person nur mit den bereits gesehenen vergleichen, musst dich sofort entscheiden und darfst niemanden zurückholen. Bestimme, wie viele du zu Beginn grundsätzlich ablehnst; die Regel nimmt anschließend die erste Person, die alle vorherigen übertrifft.

Chance auf das Optimum bei k Abgelehnten	$P(k)=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Optimale Schwelle für großes n	$k^*\approx\frac{n}{e}$
Zugehörige Wahrscheinlichkeit	$P(k^*)\to\frac{1}{e}\approx0.3679$

Rechenbeispiel — Die 37-%-Regel

Optimale Schwelle k*	4
Wahrscheinlichkeit für das Optimum bei k*	39,84%
n/e, zum Vergleich	4,05
Erfolgschance bei rein zufälliger Wahl	9,09%
Niedrigster erreichbarer Erwartungsrang	2,6136
Simuliert, 2.000 Zufallsreihenfolgen	803 von 2.000 trafen die beste Wahl (40,2%)

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Die 37-%-Regel

Beim Sekretärinnenproblem erscheinen n Kandidaten in zufälliger Reihenfolge. Jeder wird ausschließlich mit den bereits gesehenen verglichen und sofort endgültig angenommen oder abgelehnt. Die Schwellenwertregel verwirft die ersten k Personen und nimmt danach die erste, die besser ist als alle bisherigen.

Woher die Formel kommt

Nach der Position des Optimums zerlegen. Sei B die Position des besten Kandidaten und W das Ereignis, diesen zu wählen. B nimmt jeden Wert von 1 bis n mit gleicher Wahrscheinlichkeit an.
$P(B=i)=\frac{1}{n},\qquad i=1,\dots,n$
Liegt das Optimum unter den ersten k, ist es verloren. Die Regel blickt nie zurück; diese Positionen tragen also nichts bei.
$B\le k:\quad P(W\mid B)=0$
Ein Optimum an Position i > k wird nur erreicht, wenn niemand zwischen k + 1 und i − 1 gewählt wurde. Das geschieht genau dann, wenn die beste Person der ersten i − 1 schon unter den ersten k war – nur dann übertrifft niemand dazwischen den gesetzten Maßstab. Jeder der ersten i − 1 kommt dafür mit gleicher Wahrscheinlichkeit infrage.
$B=i>k:\quad P(W\mid B=i)=\frac{k}{i-1}$
Über alle Positionen aufsummieren.
$P(k)=\sum_{i=k+1}^{n}\frac{1}{n}\cdot\frac{k}{i-1}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Den Grenzwert für n bilden. Mit x = k/n geht die Summe in ein Integral über und die Wahrscheinlichkeit wird zu −x ln x. Ihre Ableitung, −ln x − 1, verschwindet bei x = 1/e, wo die Wahrscheinlichkeit 1/e ≈ 36,79 % beträgt.
$P\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x,\qquad\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\iff x=\frac{1}{e}$

Setzt voraus: Sichtbar sind nur Ränge, keine Punktwerte; die Reihenfolge ist rein zufällig; abgelehnte Personen lassen sich nicht zurückholen und angenommene sagen stets zu; alles außer der Bestbesetzung gilt als Misserfolg.

Aufgaben vollständig gelöst

Drei Kandidaten, alle Reihenfolgen 3 Schritte
Drei Kandidaten erscheinen in zufälliger Reihenfolge. Notiere jede Reihenfolge als Ränge in Ankunftsfolge (1 = bester). Du verwirfst den ersten und nimmst den ersten, der alle vorherigen schlägt: In wie vielen der sechs Reihenfolgen wählst du das Optimum? Prüfe das Ergebnis mit der Formel.

Öffne diese Aufgabe im Tool
1. Die sechs Reihenfolgen:
  
  $123,\quad 132,\quad 213,\quad 231,\quad 312,\quad 321$
2. Die erste Person setzt den Maßstab. In 213 und 231 übertrifft die 1 die 2; in 312 kommt die 1 an zweiter Stelle und wird genommen. In 123 und 132 übertrifft niemand die verworfene 1, sodass die letzte Person bleibt; in 321 schlägt die 2 die 3 und wird gewählt, bevor die 1 erscheint:
  
  $213\to1,\quad 231\to1,\quad 312\to1;\qquad 123\to3,\quad 132\to2,\quad 321\to2$
3. Die Formel mit n = 3 und k = 1:
  
  $P(1)=\frac{1}{3}\left(\frac{1}{1}+\frac{1}{2}\right)=\frac{1}{3}\cdot\frac{3}{2}=\frac{1}{2}$
Antwort

In 3 von 6 Reihenfolgen, eine Chance von 1/2 gegenüber 1/3 bei sofortiger Wahl der ersten Person.

$P(1)=\frac{3}{6}=\frac{1}{2}>\frac{1}{3}=P(0)$
Vier Kandidaten, jede Schwelle 2 Schritte
Finde für vier Kandidaten die Wahrscheinlichkeit, das Optimum zu wählen, für jeden Schwellenwert k = 0, 1, 2, 3 sowie die beste Schwelle.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. k = 0 wählt die erste Person, die mit Wahrscheinlichkeit 1/4 die beste ist. Für k ≥ 1 verwende die Formel:
  
  $P(1)=\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{3}\right)=\frac{11}{24},\quad P(2)=\frac{2}{4}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12},\quad P(3)=\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{4}$
2. Vergleich der vier Fälle:
  
  $P(0)=\frac{6}{24},\quad P(1)=\frac{11}{24},\quad P(2)=\frac{10}{24},\quad P(3)=\frac{6}{24}$
Antwort

Einen ablehnen, dann den ersten nehmen, der ihn übertrifft: 11/24 ≈ 45,83 %.

$k^*=1,\qquad P(1)=\frac{11}{24}\approx0.4583$
Keplers elf 3 Schritte
Im Jahr 1611 suchte Johannes Kepler eine zweite Ehefrau und prüfte über fast zwei Jahre hinweg elf Kandidatinnen. Welcher Schwellenwert ist bei der Regel mit n = 11 optimal, welche Chance bietet er, und welche Kandidatin kann die Regel frühestens wählen?

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Berechne die Formel um n/e = 11/e ≈ 4,05:
  
  $P(4)=\frac{4}{11}\left(\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{10}\right)=\frac{4}{11}\times1.0956=0.3984$
2. k = 4 liefert den größten Wert; k = 3 und k = 5 liegen beide darunter:
  
  $P(3)=\frac{3}{11}\left(\frac{1}{3}+\dots+\frac{1}{10}\right)=0.3897,\qquad P(5)=\frac{5}{11}\left(\frac{1}{5}+\dots+\frac{1}{10}\right)=0.3844$
3. Werden vier abgelehnt, ist die fünfte Kandidatin die früheste, die die Regel annehmen kann. Kepler heiratete tatsächlich die fünfte, allerdings nicht nach dieser Regel: Nach Fergusons Schilderung von Keplers Brief ließ er sich nach dem Treffen mit der fünften überreden, der vierten einen Antrag zu machen. Erst nach deren Absage kehrte er um. Die Regel aber verbietet jedes Zurückkehren.
Antwort

Vier ablehnen, Chance 39,84 %; die fünfte ist die früheste Kandidatin, die die Regel annehmen kann.

$k^*=4,\qquad P(4)\approx0.3984$
Viele Kandidaten: Woher 1/e stammt 3 Schritte
Drücke für großes n den verworfenen Anteil als x = k/n aus und bestimme das optimale x sowie die daraus folgende Chance. Vergleiche dies mit n = 100.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Die Summe ist eine Riemann-Summe für 1/t auf [x, 1]:
  
  $\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}=x\sum_{j=k}^{n-1}\frac{1}{n}\cdot\frac{1}{j/n}\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x$
2. Setze die Ableitung gleich null:
  
  $\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\ \Rightarrow\ x=\frac{1}{e},\qquad -\frac{1}{e}\ln\frac{1}{e}=\frac{1}{e}\approx0.3679$
3. Für n = 100 ist n/e ≈ 36,79, und die exakt beste Schwelle lautet 37:
  
  $P(36)=0.37101,\qquad P(37)=0.37104,\qquad P(38)=0.37080$
Antwort

Einen Anteil von 1/e ≈ 36,79 % ablehnen; die Chance strebt gegen 1/e. Bei n = 100 ist die beste Schwelle 37 mit einer Chance von 37,1 %.

$x^*=\frac{1}{e},\qquad P\to\frac{1}{e}\approx0.3679;\qquad n=100:\ k^*=37,\ P(37)\approx0.3710$
Am Ende bleibt nur die letzte Person 3 Schritte
Hundert Kandidaten, die ersten 37 abgelehnt. Bestimme die Wahrscheinlichkeit, dass die beste Person unter den Abgelehnten ist, die Wahrscheinlichkeit, dass die Suche bis zur letzten Person vordringt, und die Wahrscheinlichkeit, dass die letzte Person dann die beste ist.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Die beste Person kann mit gleicher Wahrscheinlichkeit überall stehen; unter den ersten 37 ist sie daher mit der Wahrscheinlichkeit:
  
  $\frac{k}{n}=\frac{37}{100}=0.37$
2. Die Suche erreicht Kandidat 100 genau dann, wenn niemand von 38 bis 99 gewählt wird – also wenn die beste der ersten 99 Personen unter den ersten 37 war:
  
  $\frac{k}{n-1}=\frac{37}{99}\approx0.3737$
3. Die Differenz ist der Fall, dass die Suche bis zum Ende vordringt und die letzte Person zugleich die beste ist:
  
  $\frac{37}{99}-\frac{37}{100}=\frac{37}{9900}\approx0.0037$
Antwort

37 %, 37,37 % und 0,37 %: Mehr als jede dritte Suche endet bei der letzten Person, und fast nie, weil sie wirklich die beste ist.

$0.37,\qquad 0.3737,\qquad 0.0037$
Niedrigster Erwartungsrang bei drei Kandidaten 3 Schritte
Drei Kandidaten, und das Ziel ist nun der niedrigste mittlere Rang (1 = bester), nicht zwingend das Optimum. Finde die optimale Regel durch Rückwärtsinduktion und ihren Erwartungsrang.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Erscheint ein Kandidat an i-ter Stelle und belegt unter den bisherigen Rang j, beträgt sein erwarteter Gesamtrang j(n + 1)/(i + 1). Der dritte Kandidat muss genommen werden und hat den Erwartungsrang (n + 1)/2:
  
  $\frac{j(n+1)}{i+1}=\frac{4j}{i+1},\qquad c_2=\frac{3+1}{2}=2$
2. Nimm den zweiten Kandidaten, wenn sein Erwartungsrang höchstens 2 ist, sonst gehe weiter:
  
  $i=2:\ \ j=1:\ \tfrac{4}{3}<2,\quad j=2:\ \tfrac{8}{3}>2;\qquad c_1=\frac{1}{2}\left(\frac{4}{3}+2\right)=\frac{5}{3}$
3. Beim ersten brächte die Annahme den Erwartungsrang 2, also mehr als 5/3; gehe daher weiter:
  
  $i=1:\ \ \frac{4}{2}=2>\frac{5}{3}\ \Rightarrow\ c_0=c_1=\frac{5}{3}$
Antwort

Den ersten übergehen, den zweiten nehmen, falls er besser als der erste ist, andernfalls den dritten: Erwartungsrang 5/3 ≈ 1,67. Bei drei Kandidaten ist das genau die Schwellenwertregel mit k = 1.

$c_0=\frac{5}{3}\approx1.6667$
Zwei Kandidaten bei sichtbaren Punktwerten 2 Schritte
Zwei Kandidaten erhalten unabhängig voneinander gleichverteilte Punktwerte zwischen 0 und 1, und du siehst jeden Wert sofort bei Ankunft. Finde die Regel, die am häufigsten den höheren Wert wählt, und ihre Erfolgschance. Vergleiche sie mit reinen Rängen.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Übergehst du den ersten Kandidaten mit Punktwert x, musst du den zweiten nehmen; dieser gewinnt, wenn er höher liegt: Wahrscheinlichkeit 1 − x. Nimmst du den ersten, gewinnt er, wenn der zweite niedriger liegt: Wahrscheinlichkeit x.
  
  $S(x)=x,\qquad C(x)=1-x;\qquad S(x)\ge C(x)\iff x\ge\tfrac{1}{2}$
2. Nimm den ersten also genau dann, wenn x ≥ 1/2 ist. Gemittelt über x:
  
  $\int_{0}^{1/2}(1-x)\,dx+\int_{1/2}^{1}x\,dx=\frac{3}{8}+\frac{3}{8}=\frac{3}{4}$
Antwort

Nimm den ersten, wenn sein Wert mindestens 1/2 beträgt: Chance 3/4. Bei bloßen Rängen liefern zwei Kandidaten immer 1/2, was auch immer du tust.

$P=\frac{3}{4}>\frac{1}{2}$

Weitere Aufgaben, nur mit Lösungen

Bestimme bei fünf Kandidaten die beste Schwelle und ihre Chance.

Ergebnis anzeigen

Zwei ablehnen: 13/30 ≈ 43,33 %.

$k^*=2,\qquad P(2)=\frac{2}{5}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{13}{30}\approx0.4333$
Zeige für zwei Kandidaten und reine Ränge, dass jede Regel in der Hälfte der Fälle die beste Wahl trifft.

Ergebnis anzeigen

Die erste Person zu nehmen gewinnt mit 1/2; sie zu übergehen führt zur zweiten, ebenfalls 1/2.

$P(0)=\frac{1}{2},\qquad P(1)=\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{2}$
Bestimme bei zehn Kandidaten und optimaler Schwelle die Wahrscheinlichkeit, dass die beste Person unter den Abgelehnten ist, und die Wahrscheinlichkeit, dass die Suche bis zur letzten Person läuft.

Ergebnis anzeigen

k = 3: 30 % und 3/9 ≈ 33,33 %.

$k^*=3:\quad\frac{3}{10}=0.3,\qquad\frac{3}{9}\approx0.3333$
Bestimme im Grenzwert für großes n die Chance auf das Optimum, wenn ein Fünftel der Kandidaten abgelehnt wird und wenn es drei Fünftel sind.

Ergebnis anzeigen

−0,2 ln 0,2 ≈ 32,19 % und −0,6 ln 0,6 ≈ 30,65 %.

$-0.2\ln0.2\approx0.3219,\qquad-0.6\ln0.6\approx0.3065$
Finde für vier Kandidaten den kleinsten Erwartungsrang, den eine Regel überhaupt erreichen kann.

Ergebnis anzeigen

15/8 = 1,875.

$c_0=\frac{15}{8}=1.875$

Ein Viertel oder die Hälfte verwerfen: die gleiche Chance

Die Kurve verläuft an ihrer Spitze bemerkenswert flach, was die Regel enorm alltagstauglich macht. Klick auf Ein Viertel abgelehnt: 35,04 %. Klick auf Die Hälfte abgelehnt: 34,91 %. Die beste Schwelle bei hundert Fällen, 37, bringt 37,1 %; ob du nun ein Viertel oder die Hälfte verwirfst, kostet dich also höchstens 2,2 Prozentpunkte. Wächst n, nähert sich die Kurve −x ln x an, wobei x den verworfenen Anteil bezeichnet. Bei einem Viertel und bei der Hälfte nimmt sie exakt denselben Wert an, denn ¼ ln 4 = ½ ln 2 ≈ 34,66 %. Du musst n also gar nicht genau treffen: Schätze ruhig um ein Drittel zu hoch oder zu niedrig, lehne 37 % deines Schätzwerts ab, und du behältst bei großem n immer noch mindestens 34,5 %.

Wer nur das Beste will, landet in über einem Drittel der Fälle beim Letzten

Die Regel setzt alles auf eine Karte: den allerbesten Kandidaten. Zählt dieser aber zu den Personen, die du vorab verworfen hast – bei hundert Kandidaten passiert das in 37 % der Fälle –, kann niemand danach diesen Maßstab überbieten. Die Suche läuft bis zum Ende durch und nimmt, wer auch immer als Letztes kommt. Klick auf Hundert, 37 abgelehnt: Der erwartete Rang der gewählten Person liegt bei 20,01. Im Jahr 1964 fragten Chow, Moriguti, Robbins und Samuels nach einer Regel, die stattdessen den mittleren Rang minimiert. Sie wählt bereits jemanden, der nahe an der bisherigen Spitze liegt, und lockert diesen Anspruch gegen Ende schrittweise. Für n = 100 erzielt sie einen Erwartungsrang von 3,60. Dieser Wert bleibt für jedes n dieser Seite unter 4 und strebt gegen 3,8695; bei der 37-%-Regel dagegen wächst er mit n stetig weiter, bei tausend Kandidaten schon auf 185,54.

Punktwerte sichtbar: Die Chance steigt auf 58 %

Die 37-%-Regel nutzt nur Ränge: wer wen geschlagen hat. Stell dir nun vor, du siehst den echten Punktwert jedes Kandidaten und weißt, wie die Werte verteilt sind – etwa gleichverteilt zwischen 0 und 1. Gilbert und Mosteller lösten diese Variante 1966. Die reine Beobachtungsphase fällt hier weg. Vom ersten Kandidaten an nimmst du jeden, der bisher am besten ist und eine bestimmte Punktgrenze übertrifft. Diese Schwelle sinkt zum Ende hin: 0,5, wenn noch eine Person aussteht, 0,6899 bei zweien, 0,9240 bei zehn. Die Chance auf die absolute Bestbesetzung liegt bei 60,6 % für elf Kandidaten, bei 58,29 % für hundert und strebt gegen 58,02 % – verglichen mit 36,79 % bei bloßen Rängen. Zu wissen, was ein gutes Ergebnis ist, bringt rund 21 Prozentpunkte.

Lernpfad

Entscheiden nach dem, was du siehst

Quellen (4)

The problem as now studied (n known, random order, relative ranks only, no recall, only the best counts), the cutoff rule and its chance, and the history the page uses: Kepler, after losing his first wife in 1611, spent nearly two years over at least eleven candidates, described in a letter to Baron Strahlendorf of 23 October 1613; friends persuaded him to propose to the fourth after he met the fifth, the fourth turned him down, and he chose the fifth. Ferguson notes that for n = 11 the rule's chance is largest when the fifth is the first candidate it may take, and that Kepler's recall breaks the problem's assumptions: T. S. Ferguson, Who solved the secretary problem? Statistical Science 4(3), 282–289 (1989). doi:10.1214/ss/1177012493
The classical secretary problem solved by backward induction, the limits the page quotes in insight blocks 2 and 3: the least expected rank tends to 3.8695 (Chow, Moriguti, Robbins and Samuels), and with the values revealed and their distribution known the chance of the best tends to 0.58016 (Gilbert and Mosteller), 'to be compared to the limiting value e⁻¹ when the intrinsic values are not revealed': T. S. Ferguson, Optimal Stopping and Applications, Chapter 2, Finite Horizon Problems, §§2.1–2.3. Mathematics Department, UCLA (online text).
The rank-minimising rule of insight block 2 and solved problem 6: accept a candidate whose relative rank is within a threshold that rises as the candidates run out, with expected rank tending to 3.8695: Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal selection based on relative rank (the "secretary problem"). Israel Journal of Mathematics 2(2), 81–90 (1964). doi:10.1007/BF02759948
The full-information problem of insight block 3 and solved problem 7: values seen, independent with a known distribution; the optimal rule takes a best-so-far above a threshold that depends on how many remain, and the chance of the best tends to 0.5802: J. P. Gilbert and F. Mosteller, Recognizing the maximum of a sequence. Journal of the American Statistical Association 61(313), 35–73 (1966). doi:10.1080/01621459.1966.10502008

Vom 7-Raven-Room-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.

Die 37-%-Regel

Woher die Formel kommt

Weitere Aufgaben, nur mit Lösungen

Ein Viertel oder die Hälfte verwerfen: die gleiche Chance 🖖

Wer nur das Beste will, landet in über einem Drittel der Fälle beim Letzten 🖖

Punktwerte sichtbar: Die Chance steigt auf 58 % 🖖

Ein Viertel oder die Hälfte verwerfen: die gleiche Chance

Wer nur das Beste will, landet in über einem Drittel der Fälle beim Letzten

Punktwerte sichtbar: Die Chance steigt auf 58 %