Das Sekretärproblem verständlich erklärt

Sie besichtigen Wohnungen nacheinander und müssen nach jeder sofort Ja oder Nein sagen. Ein Nein gilt für immer. Diese Seite zeigt eine einfache Regel für solche Entscheidungen und die Fälle, in denen sie versagt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Wohnung, die nicht wartet

Stellen Sie sich eine Stadt vor, in der Wohnungen sofort weggehen. Sie besichtigen 100 Wohnungen, eine nach der anderen. Nach jeder müssen Sie sofort entscheiden. Sagen Sie Ja, ist die Suche beendet. Sagen Sie Nein, ist die Wohnung für immer weg.

Sie wollen die beste der 100 erwischen. Das ist schwer, denn die späteren Wohnungen kennen Sie noch nicht. Zur Vereinfachung achten Sie nur auf eine Frage: Ist diese Wohnung besser als alle bisherigen?

Dieselbe Lage gibt es beim Gebrauchtwagenkauf oder bei der Einstellung von Personal. Fachleute nennen sie das Sekretärproblem.

Erst ansehen, dann zuschlagen

Eine einfache Regel hilft. Sehen Sie sich die ersten 37 Wohnungen nur an und sagen Sie zu allen Nein. Das ist die Wartezeit. Merken Sie sich, welche davon die beste war. Sie ist Ihre Messlatte.

Danach nehmen Sie die erste Wohnung, die besser ist als alle bisherigen. Kommt keine mehr, bleibt Ihnen die letzte.

Warum erst warten? Wer sofort zuschlägt, nimmt oft eine mittelmäßige Wohnung, weil er noch keine Messlatte hat. Wer zu lange wartet, lässt die beste womöglich schon vorbeiziehen. Die Wartezeit ist der Mittelweg. Dass es bei 100 Wohnungen gerade 37 sind, lässt sich ausrechnen; die Rechnung steht im zweiten Teil.

Die Regel setzt voraus, dass Sie die Gesamtzahl kennen, hier 100, denn die Wartezeit ist ein fester Anteil davon. Die Zahlen dieser Seite stammen aus einem Programm, das die Suche mit erfundenen Wohnungen viele Male durchspielt (die Messung).

Kommen die Wohnungen in zufälliger Reihenfolge, findet die Regel in etwa 37 von 100 Versuchen die beste. Zufällig heißt: Niemand hat die Wohnungen vorsortiert.

Wenn die Reihenfolge nicht zufällig ist

Die 37 von 100 gelten nur bei zufälliger Reihenfolge. Nehmen wir an, ein Makler zeigt die schlechtesten Wohnungen zuerst und die besten zum Schluss. Dann ist jede Wohnung besser als alle davor.

Ihre Regel sagt deshalb gleich nach der Wartezeit Ja. Die beste kommt aber erst viel später. Bei 100 Wohnungen und 37 zum Ansehen fand die Regel in der Messung kein einziges Mal die beste. Auch wenn nur die ersten 50 Wohnungen vom schlechtesten zum besten geordnet waren und der Rest zufällig, fand sie die beste nie.

Zeigt der Makler die Wohnungen vom besten zum schlechtesten, überspringen Sie die beste in der Wartezeit. Am Ende bleibt Ihnen die letzte Wohnung, und die ist dann die schlechteste.

Wenn man die möglichen Beträge kennt

Bisher wussten Sie nur, wie eine Wohnung im Vergleich zu den früheren abschneidet. Jetzt wechselt das Beispiel: Sie sind Verkäufer statt Suchender, und Sie wissen mehr. Sie kennen, wie hoch ein Angebot ausfallen kann und wie wahrscheinlich das ist.

Nehmen wir an, Sie verkaufen ein Auto. Zwei Käufer kommen nacheinander, und Sie sagen jedem sofort Ja oder Nein. Der erste bietet sicher 1.000 Euro. Der zweite bietet in 1 von 100 Fällen 100.000 Euro und sonst nichts.

Zum Vergleich stellen wir uns einen Seher vor (Fachwort: Prophet). Er weiß vorher, was beide bieten, und nimmt das größere. Er ist kein Vorbild, nur ein Maßstab: Mehr als er bekommt im Mittel niemand.

Was bekommt der Seher im Mittel? Meistens bietet der zweite nichts, dann nimmt er die sicheren 1.000 Euro. In 1 von 100 Fällen nimmt er die 100.000 Euro. Der Hauptgewinn bringt im Mittel 1.000 Euro je Fall. Insgesamt bekommt der Seher im Mittel fast doppelt so viel wie die sicheren 1.000 Euro.

Ihre Regel: Legen Sie eine Grenze (Fachwort: Schwelle) auf die Hälfte dessen, was der Seher im Mittel bekäme. Das wären knapp 1.000 Euro. Nehmen Sie das erste Angebot, das diese Grenze erreicht.

Kommt der erste Käufer zuerst, nehmen Sie seine 1.000 Euro und verpassen den seltenen Hauptgewinn. Dann haben Sie nur wenig mehr als die Hälfte vom Seher. Das ist der ungünstigste Fall. Kommt der zweite zuerst, nehmen Sie ihn nur bei Hauptgewinn und sonst den ersten. Dann bekommen Sie im Mittel so viel wie der Seher.

Das gilt über das Beispiel hinaus. Die Angebote müssen unabhängig sein, eines sagt also nichts über das nächste, und keines darf negativ sein. Außerdem müssen Sie die möglichen Beträge und ihre Wahrscheinlichkeiten kennen, wie hier. Dann sichert die Grenze mindestens die Hälfte dessen, was der Seher bekäme. Das gilt in jeder Reihenfolge, auch wenn jemand sie vor dem Eintreffen der Angebote absichtlich zu Ihrem Nachteil festlegt.

Die Hälfte klingt besser als 37 von 100, misst aber etwas anderes. Die 37 von 100 zählen, wie oft man genau die beste erwischt. Die Hälfte meint die Hälfte des Betrags, den der Seher im Mittel bekäme. Gegeneinander aufrechnen lassen sich beide nicht.

Die beste oder eine gute?

Wollen Sie genau die beste Wohnung, passen 37 Wohnungen zum Ansehen. Reicht Ihnen eine gute, warten Sie besser kürzer. Das Programm nutzt erfundene Wohnungen, deren Qualität gleichmäßig zwischen schlecht und bestmöglich liegt. Damit war die gewählte Wohnung mit 10 zum Ansehen im Mittel besser als mit 37. Die beste fand die Regel dann aber seltener.

Eine Deutung dieser Seite: Langes Warten lässt die beste öfter in der Wartezeit verschwinden. Dann bleibt nur die letzte Wohnung. Das passiert bei 37 zum Ansehen in 37 von 100 Fällen, bei 10 in 10 von 100. Für eine gute Wohnung lohnt langes Warten wenig. Schon eine Wohnung, die besser ist als die ersten 10, liegt im Mittel nahe an der besten.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser. Der erste Knopf unten öffnet es. Der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie das Programm nicht.

Es spielt die Suche mit erfundenen Angeboten viele Male durch und zählt, wie oft die Regel die beste findet. Die Aussagen in diesem Teil beschreiben dieses vereinfachte Rechenbild (Fachwort: Modell), nicht die Wirklichkeit.

Häufige Missverständnisse

• „Verfehle ich die beste, war alles umsonst.“ Nein. Die Regel zielt auf die beste. In der Messung (100 Wohnungen, 37 zum Ansehen) gehörte die gewählte Wohnung aber in etwa 63 von 100 Versuchen zu den fünf besten.
• „Die Grenze bringt mir genau die Hälfte.“ Nein. Die Hälfte ist nur das Mindeste im ungünstigsten Fall. Bei zufällig erzeugten Beispielen und zufälliger Reihenfolge lag der Wert im Mittel über vier Fünfteln dessen, was der Seher bekam.

Woran Sie das im Alltag erkennen

Anzeichen für diese Art von Entscheidung:

• Sie müssen sofort entscheiden, und ein Nein ist endgültig, etwa bei einer Wohnung, einem Gebrauchtwagen oder einer Stelle.
• Spätere Angebote sehen Sie nicht, die früheren können Sie aber mit dem aktuellen vergleichen.
• Am Ende steht genau eine Wahl, und Sie wissen vorab ungefähr, wie viele Angebote kommen.

Wie ernst ist das Rechenbild zu nehmen?

Die Angebote im Programm sind erfunden, ihre Reihenfolge ist zufällig oder von Hand geordnet. Echte Märkte sind unordentlicher.

Was Sie mitnehmen:

• Fragen Sie sich vor der Suche, ob nur die beste zählt oder auch eine gute.
• Prüfen Sie, ob jemand die Reihenfolge der Angebote lenken kann. Dann kann die Regel mit Wartezeit versagen.
• Wer die übliche Streuung der Angebote kennt, hat eine zweite Möglichkeit: eine Grenze, deren Mindestergebnis nicht an der Reihenfolge hängt.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst Modell und Messungen der Demo zusammen.

• Teil A, Sekretärproblem: \(n\) Angebote mit verschiedenen Werten, gleichverteilt in \((0, 1)\), kommen in zufälliger Reihenfolge; größer ist besser. Nach dem \(t\)-ten Angebot ist nur bekannt, ob es das beste unter den ersten \(t\) ist. Die Regel mit Wartezeit \(k\): die ersten \(k\) Angebote nur ansehen, dann das erste nehmen, das besser ist als alle bisherigen; kommt keines, das letzte. Voreinstellung der Demo: \(n = 100\) und \(k = 37\).
• Kennzahlen in Teil A: Der Erfolg ist der Anteil der Folgen, in denen das beste Angebot gewählt wird. Wert/Maximum ist der Wert des gewählten Angebots geteilt durch den des besten, gemittelt über die Folgen. „Unter den besten 5“ ist der Anteil der Folgen, in denen das gewählte Angebot zu den fünf größten gehört.
• Verletzte Annahme: Ein einstellbarer Anteil der Folge am Anfang wird aufsteigend sortiert (0 % ist zufällige Reihenfolge, 100 % ganz aufsteigend). „Absteigend“ heißt: die ganze Folge absteigend sortiert.
• Teil B, Prophet-Ungleichung: Die Angebote \(X_1, \dots, X_n \ge 0\) sind unabhängig mit bekannten Verteilungen und kommen in einer Reihenfolge, die ein Gegner wählt; die Demo prüft nur feste, vor den Ziehungen gewählte Reihenfolgen. Der Prophet sieht alle Werte und nimmt das größte, sein Mittelwert ist \(\mathbb{E}[\max_i X_i]\). Eine Regel mit Schwelle \(T\) nimmt das erste Angebot mit \(X_i \ge T\), sonst das letzte.
• Scharfes Beispiel: zwei Angebote, \(X_1 = 1\) sicher und \(X_2 = 1/\varepsilon\) mit Wahrscheinlichkeit \(\varepsilon\), sonst 0. Dann ist \(\mathbb{E}[\max] = 2 - \varepsilon\). Voreinstellung \(\varepsilon = 0{,}01\); die Demo erlaubt \(\varepsilon\) ab \(0{,}01\).
• Vier Regeln und drei Reihenfolgen im scharfen Beispiel: Schwelle \(T = \mathbb{E}[\max]/2\); Schwelle am Median des Maximums (kleinster Wert \(t\) mit \(P(\max \le t) \ge \tfrac{1}{2}\)); immer das erste Angebot; optimal (Rückwärtsrechnung, kennt die Reihenfolge: nimm ein Angebot, wenn es mehr wert ist als der erwartete Wert der übrigen; bei Gleichheit ist man unentschieden und der Wert derselbe). Reihenfolgen: „kleine zuerst“ (das sichere Angebot zuerst), „große zuerst“ (das riskante zuerst) und „zufällig“ (beide mit gleicher Wahrscheinlichkeit).
• Rechenweg: Die Erfolgswahrscheinlichkeit bei zufälliger Reihenfolge, das scharfe Beispiel und die gleichverteilten Angebote sind exakt gerechnet. Die Kennzahlen bei gewählter Reihenfolge sind Schätzungen aus gezogenen Folgen: 4000 Folgen im Einzelfall, 50 000 je Zeile der festen Messreihen, mit festem Zufallsstartwert. Die Voraussetzungen der einzelnen Messreihen stehen in der Befundtabelle.
• Rückfall auf das letzte Angebot: Dass die Regel das letzte Angebot nimmt, wenn keines die Bedingung erfüllt, ist eine Festlegung der Demo. In Teil A ist dieser Fall der Misserfolg (das beste liegt dann in der Wartezeit). In Teil B kann der Rückfall die Garantie nur verbessern, denn die Angebote sind nicht negativ und das letzte ist nie schlechter als nichts.

Die Formeln

Teil A. Für \(k \ge 1\) ist die Wahrscheinlichkeit \(P(n, k)\), bei zufälliger Reihenfolge das beste Angebot zu wählen,

\[P(n, k) = \dfrac{k}{n} \sum_{i=k}^{n-1} \dfrac{1}{i}\]

Für \(k = 0\) (das erste Angebot nehmen) ist sie \(1/n\). Für \(n \to \infty\) und \(k/n \to x\) geht sie gegen \(-x \ln x\), mit dem Maximum \(1/e\) bei \(x = 1/e\).

Teil B. Die Schwellenregel nimmt das erste \(X_i \ge T\), sonst das letzte, mit der Schwelle

\[T = \tfrac{1}{2} \mathbb{E}[\max_i X_i]\]

Prophet-Ungleichung: Bei unabhängigen \(X_i \ge 0\) ist der erwartete Wert dieser Regel für jede feste, vorab gewählte Reihenfolge mindestens \(\tfrac{1}{2} \mathbb{E}[\max_i X_i]\). Die Konstante \(\tfrac{1}{2}\) ist scharf: Im scharfen Beispiel mit \(X_1 = 1\) zuerst ergibt sich der Quotient \(\tfrac{1}{2 - \varepsilon}\), denn der Prophet erreicht \(\mathbb{E}[\max] = 2 - \varepsilon\) und die Regel nur 1. Für \(\varepsilon \to 0\) geht der Quotient gegen \(\tfrac{1}{2}\). Die Demo belegt die Garantie durch Rechnen kleiner Fälle und durch Stichproben, nicht durch einen Beweis.

Unabhängig und gleich verteilt. Der optimale Wert \(v_m\) bei \(m\) noch ausstehenden Angeboten, gleichverteilt in \((0, 1]\), erfüllt \(v_1 = \tfrac{1}{2}\) und

\[v_{m+1} = \tfrac{1 + v_m^2}{2}\]

Dabei nimmt man das aktuelle Angebot, wenn es mehr wert ist als \(v_m\); bei Gleichheit ist der Wert derselbe.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo. Wo die Demo dieselbe Aussage prüft, steht es dabei.

Die Erfolgswahrscheinlichkeit \(P(n, k)\).

• Schritt 1: Das beste Angebot liegt an Platz \(j\), für jedes \(j\) mit Wahrscheinlichkeit \(1/n\).
• Schritt 2: Liegt es in den ersten \(k\) Plätzen, wird es nie gewählt. Die Regel sieht es nur an, danach übertrifft nichts das Bisherige, also nimmt sie das letzte Angebot, und das ist dann nicht das beste.
• Schritt 3: Liegt es an Platz \(j > k\), wird es genau dann gewählt, wenn das beste der ersten \(j-1\) Angebote in den ersten \(k\) liegt, sonst hätte die Regel früher zugeschlagen. Bei zufälliger Reihenfolge hat das die Wahrscheinlichkeit \(k/(j-1)\).
• Schritt 4: Summiert ergibt sich \(P(n, k) = \sum_{j=k+1}^{n} \tfrac{1}{n} \cdot \tfrac{k}{j-1} = \tfrac{k}{n} \sum_{i=k}^{n-1} \tfrac{1}{i}\).
• Probe: Die Demo prüft die Formel gegen das Aufzählen aller Reihenfolgen für \(n = 1\) bis 7 und jedes \(k\).

Durchgerechnet: \(n = 3\) und \(k = 1\). Rechnung dieser Seite: Die Ränge der drei Angebote (3 ist das beste) kommen in einer der sechs Reihenfolgen. Die Regel sieht das erste Angebot nur an.

Ränge in der Reihenfolge	Gewählt	Bestes gewählt?
1, 2, 3	Rang 2, denn er ist besser als der erste	nein
1, 3, 2	Rang 3	ja
2, 1, 3	Rang 3, denn Rang 1 ist nicht besser als der erste	ja
2, 3, 1	Rang 3	ja
3, 1, 2	Rang 2, das letzte, denn nichts übertrifft Rang 3	nein
3, 2, 1	Rang 1, das letzte	nein

Drei von sechs Reihenfolgen gewinnen. Das stimmt mit der Formel überein: \(P(3, 1) = \tfrac{1}{3}\big(1 + \tfrac{1}{2}\big) = \tfrac{1}{2}\).

Der Grenzwert \(1/e\).

• Schritt 1: Für große \(k\) und \(n\) ist \(\sum_{i=k}^{n-1} 1/i \approx \int_k^n dt/t = \ln(n/k)\).
• Schritt 2: Mit \(x = k/n\) wird \(P \approx x \ln(1/x) = -x \ln x\).
• Schritt 3: Die Ableitung \(-\ln x - 1\) verschwindet bei \(x = 1/e\), und dort ist der Wert \(1/e\). Das Optimum liegt also bei \(k \approx n/e\) mit dem Erfolg \(\approx 1/e\).

Warum der Wert eine kürzere Wartezeit will als der Erfolg. Deutung dieser Seite, gemessen ist nur die Tabelle zum Ziel im Abschnitt Befunde.

• Schritt 1: Die Regel fällt auf das letzte Angebot zurück genau dann, wenn das beste in den ersten \(k\) Plätzen liegt, bei zufälliger Reihenfolge mit Wahrscheinlichkeit \(k/n\).
• Schritt 2: Das letzte Angebot ist bei zufälliger Reihenfolge ein zufällig gezogenes, im Mittel also ein durchschnittliches.
• Schritt 3: Mit wachsendem \(k\) fällt die Regel öfter auf dieses Angebot zurück, das kostet Wert. Der Gewinn des Wartens ist beim Wert klein, weil schon ein Angebot, das die ersten wenigen übertrifft, nahe am Maximum liegt (Wert/Maximum 0,899 bei \(k = 5\)). Beim Erfolg zählt nur das beste, dort lohnt das Warten länger.

Sortierte Folgen. Die Demo prüft: Eine aufsteigende Folge verfehlt das beste Angebot außer bei \(k = n-1\), eine absteigende nur ohne Wartezeit.

• Aufsteigend: Jedes Angebot ist besser als alle vorherigen. Die Regel wählt Platz \(k+1\), das beste liegt an Platz \(n\).
• Absteigend: Platz 1 ist das beste und wird nie übertroffen. Für \(k \ge 1\) wird es nur angesehen, danach nimmt die Regel das letzte, das schlechteste.
• Anfang aus \(s\) Plätzen aufsteigend sortiert: Ist \(s \le k\), ändert das Sortieren innerhalb der Wartezeit die Menge der angesehenen Werte nicht, und der Erfolg bleibt \(P(n, k)\). Ist \(s > k\), ist Platz \(k+1\) besser als alle bisherigen, und die Regel nimmt ihn. Für \(s \ge k+2\) übertrifft ihn Platz \(k+2\), der Erfolg ist also null. Für \(s = k+1\) ist er der größte der ersten \(s\) und mit Wahrscheinlichkeit \(s/n\) das beste insgesamt.

Das scharfe Beispiel. Die Demo rechnet es exakt und prüft es gegen eine getrennte Aufzählung der Ausgänge.

• Prophet: \(\mathbb{E}[\max] = (1 - \varepsilon) \cdot 1 + \varepsilon \cdot \tfrac{1}{\varepsilon} = 2 - \varepsilon\).
• Kleine zuerst, Schwelle \(\mathbb{E}[\max]/2\): Die Schwelle ist \(1 - \varepsilon/2 \le 1\), die sichere 1 erreicht sie und wird genommen. Der Wert ist 1, der Quotient \(1/(2 - \varepsilon)\).
• Große zuerst, dieselbe Schwelle: Das riskante Angebot hat entweder den Wert \(1/\varepsilon \ge 1\) und wird genommen, oder den Wert 0 und liegt unter der Schwelle. Dann bleibt das letzte, die sichere 1. Der Wert ist \(\varepsilon \cdot \tfrac{1}{\varepsilon} + (1 - \varepsilon) \cdot 1 = 2 - \varepsilon\), der Quotient 1.
• Zufällig: das Mittel beider Reihenfolgen, \(\tfrac{1}{2}\big(1 + \tfrac{1}{2 - \varepsilon}\big)\) für den Quotienten; für \(\varepsilon \to 0\) also gegen drei Viertel.
• Immer das erste: Beide Angebote haben den Erwartungswert 1, denn \(\mathbb{E}[X_2] = \varepsilon \cdot \tfrac{1}{\varepsilon}\). Der Wert ist 1 in jeder Reihenfolge, der Quotient \(1/(2 - \varepsilon)\).
• Optimal: Rückwärts gerechnet nimmt man das erste Angebot, wenn es mindestens den Erwartungswert des zweiten hat. „Kleine zuerst“: 1 gegen \(\mathbb{E}[X_2] = 1\), man ist unentschieden, der Wert ist 1. „Große zuerst“: Man nimmt \(X_2\) nur bei \(1/\varepsilon\) und sonst die 1, wie die Schwelle.
• Median des Maximums: Für \(\varepsilon \le \tfrac{1}{2}\) ist \(P(\max \le 1) = 1 - \varepsilon \ge \tfrac{1}{2}\), der Median ist also 1. Die Entscheidungen sind dieselben wie bei der anderen Schwelle.

Gleichverteilte Angebote.

• Schritt 1: Bei \(m+1\) ausstehenden Angeboten nimmt man das aktuelle \(x\), wenn \(x > v_m\), sonst erwartet man \(v_m\). Der Wert ist \(\int_{v_m}^{1} x\,dx + v_m \cdot v_m = \tfrac{1 - v_m^2}{2} + v_m^2 = \tfrac{1 + v_m^2}{2}\). Mit \(v_1 = \mathbb{E}[X] = \tfrac{1}{2}\) folgt die Rekursion.
• Schritt 2: Das Maximum von \(n\) gleichverteilten Angeboten hat den Mittelwert \(n/(n+1)\).
• Schritt 3: Bei Schwelle \(T\) liegt ein Angebot mit Wahrscheinlichkeit \(1 - T\) darüber. Das erste darüber hat den Mittelwert \((1 + T)/2\). Liegt keines darüber, mit Wahrscheinlichkeit \(T^n\), ist das letzte gleichverteilt in \((0, T]\) mit Mittelwert \(T/2\). Der Wert ist \((1 - T^n)\,\tfrac{1 + T}{2} + T^n\,\tfrac{T}{2}\). Der Median des Maximums erfüllt \(T^n = \tfrac{1}{2}\).
• Probe für \(n = 2\): \(v_2 = \tfrac{5}{8}\) (die Demo prüft diesen Wert), \(\mathbb{E}[\max] = \tfrac{2}{3}\), der Quotient also \(\tfrac{15}{16}\).
• Grenzwert: Für \(n \to \infty\) geht \(\mathbb{E}[\max]\) gegen 1, die Schwelle gegen \(\tfrac{1}{2}\) und \(T^n\) gegen 0. Der Wert der Schwellenregel nähert sich \((1 + \tfrac{1}{2})/2\), der Quotient also drei Vierteln. Die optimale Regel nähert sich dem Maximum. Beides passt zu den Zahlen für \(n = 100\) in der Tabelle.

Befunde

Alle Zahlen der Tabelle sind Messungen der Demo. Zahlen aus gezogenen Folgen sind Stichproben mit festem Zufallsstartwert; die Standardabweichung eines Anteils um 37 % beträgt bei 4000 Folgen rund 0,8 Punkte. Sie sinkt mit der Wurzel der Folgenzahl und ist bei 50 000 Folgen gut dreimal kleiner (Rechnung dieser Seite). Abweichungen vom exakten Wert von etwa ±1 Punkt (4000 Folgen) und ±0,4 Punkten (50 000 Folgen) entsprechen also ein bis zwei Standardabweichungen. Als exakt gekennzeichnete Zahlen sind gerechnet.

Frage	Befund
Klassisch: \(n = 100\), \(k = 37\), zufällige Reihenfolge?	Exakt 37,1 %, gezogen 37,1 % (4000 Folgen). Das gewählte Angebot ist im Mittel das 0,81-Fache des besten und liegt in 63 % der Fälle unter den besten 5 (Werte gleichverteilt in \((0, 1)\)).
Bestes \(k\) bei wachsendem \(n\) (exakt)?	\(n\) = 3 / 10 / 100 / 1000 / 10 000: \(k\) = 1 / 3 / 37 / 368 / 3679, Erfolg 50,0 % / 39,9 % / 37,1 % / 36,8 % / 36,8 %. In diesen Werten fällt der Erfolg von oben gegen \(1/e\) = 36,79 %, der Anteil \(k/n\) liegt bei \(n\) = 10 000 bei 0,3679.
Kleine Folge: \(n = 10\), \(k = 3\)?	Exakt 39,9 %: Bei wenigen Angeboten liegt der Erfolg über dem Grenzwert 36,8 %.
Aufsteigend sortierte Folge (\(n = 100\), \(k = 37\), 4000 Folgen)?	Das beste Angebot wird in 0,0 % der Fälle gewählt. Gewählt wird das 38. Angebot; das Mittel der Quotienten gewählt/beste ist 0,379.
Nur der Anfang sortiert (\(n = 100\), \(k = 37\), 50 000 Folgen je Zeile)?	Erste 25 %: 36,8 % (die Sortierung liegt in der Wartezeit und schadet nicht). Erste 50 %, 75 %, 100 % und absteigend: je 0,0 %. Wert/Maximum: 0,752 bei 50 %, 0,505 bei 75 %, 0,380 aufsteigend, 0,010 absteigend. Zufällig: 37,6 % bei exakt 37,1 %, ein Ausreißer von gut zwei Standardabweichungen.
Früh zuschlagen: \(n = 100\), \(k = 10\)?	Exakt 23,5 %, gezogen 23,1 % (4000 Folgen).
Was ist das Ziel? (\(n = 100\), zufällige Reihenfolge, 50 000 Folgen je \(k\))	\(k\) = 0 / 5 / 10 / 20 / 37 / 50 / 70: Erfolg 1,0 % / 15,2 % / 23,3 % / 32,6 % / 37,2 % / 35,0 % / 25,2 %; Wert/Maximum 0,504 / 0,899 / 0,913 / 0,885 / 0,810 / 0,748 / 0,650; unter den besten 5: 4,8 % / 47,0 % / 62,1 % / 70,5 % / 63,1 % / 51,9 % / 33,0 %. Unter den getesteten Wartezeiten ist \(k = 37\) für den Erfolg, \(k = 10\) für den Wert und \(k = 20\) für die besten 5 am besten.
Scharfes Beispiel (\(\varepsilon = 0{,}01\), exakt)?	\(\mathbb{E}[\max] = 1{,}99\). Schwelle \(\mathbb{E}[\max]/2\): 0,5025 des Maximums bei „kleine zuerst“, 1,000 bei „große zuerst“, 0,7513 zufällig. Immer das erste: 0,5025 in jeder Reihenfolge. Bei \(\varepsilon = 0{,}5\): 0,667 / 1,000 / 0,833.
Optimale Regel im scharfen Beispiel?	Gleich wie die Schwelle (0,5025 / 1,000 / 0,7513): Schon hier ist die Schwelle in allen drei Reihenfolgen optimal. Beide Schwellen (\(\mathbb{E}[\max]/2\) und Median) stimmen für \(\varepsilon \le 0{,}5\) überein.
Zufällige Instanzen (Schwelle \(\mathbb{E}[\max]/2\), Mittel über 20 Instanzen)?	Jede Instanz hat 8 unabhängige Verteilungen vom Typ Exponential, Zwei-Punkt oder Gleich; Typ und Parameter (Mittelwert, Wahrscheinlichkeit und Höhe des Zwei-Punkt-Wertes, Obergrenze der Gleichverteilung) sind je Verteilung zufällig aus festen Bereichen gezogen, je 50 000 Stichproben. „Zufällig“ heißt: Mittel über mehrere zufällig gezogene Reihenfolgen je Instanz; „aufsteigend“ und „absteigend“ ordnen nach dem Stichprobenmittel \(\mathbb{E}[X]\). Ergebnis: Zufällige Reihenfolge im Mittel 0,854 des erwarteten Maximums (Minimum 0,756), aufsteigend nach \(\mathbb{E}[X]\) 0,800 (Minimum 0,680), absteigend 0,866 (Minimum 0,759). Weit über der Garantie 0,5, und „kleine zuerst“ schadet auch hier.
Unabhängig und gleich verteilt (exakt)?	Angegeben ist der Wert der Regel geteilt durch das erwartete Maximum \(n/(n+1)\), keine Werte selbst. \(n\) = 2 / 10 / 100: optimale Regel 0,9375 / 0,9472 / 0,9910, Schwelle \(\mathbb{E}[\max]/2\) 0,9167 / 0,7998 / 0,7550, Schwelle am Median 0,9053 / 0,7882 / 0,7540. Die Schwelle als Worst-Case-Regel lässt bei \(n = 100\) 23,6 Punkte liegen.

Grenzen und was die Messung zeigt

Was sie belegt:

• Die exakte Formel \(P(n, k)\) und die Werte des scharfen Beispiels und der gleichverteilten Angebote: Sie sind gerechnet, die Formel zusätzlich gegen das Aufzählen aller Reihenfolgen bis \(n = 7\) und gegen gezogene Folgen geprüft, mit einem bewusst weiten Toleranzband von 4,5 Standardabweichungen.
• Den Befund zur sortierten Folge: Er folgt aus der Herleitung oben und stimmt mit der Messung überein.
• Die Rangfolge der Regeln im scharfen Beispiel in allen drei Reihenfolgen.

Was sie nicht belegt, und die Grenzen:

• Erfundene Angebote: Geprüft ist nur an gleichverteilten Werten in Teil A, einem Zwei-Punkt-Beispiel, zufälligen Verteilungen und gleichverteilten Angeboten in Teil B. Wert/Maximum und „unter den besten 5“ hängen an den gleichverteilten Werten; der Erfolg nicht, denn die Wahl der Regel hängt nur von der Rangfolge ab.
• Wert gegen Rang: Das Sekretärproblem sieht nur die Rangfolge, das Prophet-Problem die Werte. Die Zahlen beider Teile sind nicht vergleichbar, nur die Idee einer einzigen Wahl ohne Zurück verbindet sie.
• Grenzwert: Der Wert \(1/e\) gilt für große \(n\); bei kleinem \(n\) liegt der beste erreichbare Erfolg höher. Dass die Regel mit Wartezeit unter allen Regeln bei zufälliger Reihenfolge optimal ist, ist ein bekanntes Ergebnis der Literatur; die Demo vergleicht nur verschiedene Wartezeiten \(k\) und prüft diese Optimalität nicht.
• Die Garantie \(\tfrac{1}{2}\) gilt im schlechtesten Fall und ist nur im Grenzfall \(\varepsilon \to 0\) scharf, die Demo erlaubt \(\varepsilon\) ab \(0{,}01\). Das scharfe Beispiel zeigt, dass keine Garantie, die für alle Reihenfolgen zugleich gilt, mehr als etwa die Hälfte versprechen kann; in der Reihenfolge „große zuerst“ ist der Quotient 1. Im Mittel über die 20 zufälligen Instanzen liegt die Schwelle in jeder der drei Reihenfolgen bei etwa 0,8 oder darüber (in der ungünstigsten Instanz nicht unter 0,680); 20 Instanzen sind eine kleine Stichprobe mit festem Zufallsstartwert.
• Stichproben: Erfolg bei gewählter Reihenfolge, Wert/Maximum, „unter den besten 5“ und die zufälligen Instanzen sind Schätzungen. Bei früh zuschlagen mit \(k = 10\) kommen zwei Mittelwerte vor, 0,92-fach bei 4000 Folgen und 0,913 bei 50 000 Folgen (Tabelle zum Ziel); sie gehören zu verschiedenen Stichproben.
• Gegner: Im Sekretärproblem sind nur die aufsteigende und die absteigende Reihenfolge geprüft. In Teil B wählt der Gegner vor den Ziehungen; über eine Wahl nach Sicht der Werte sagt die Demo nichts.
• Nicht modelliert: mehrere Zuschläge, Kosten fürs Ansehen, abhängige Angebote. Bei Abhängigkeiten gilt die Garantie \(\tfrac{1}{2}\) nicht allgemein; das ist ein Hinweis, gemessen ist es nicht.
• Keine Beweise: Die Garantien sind durch Rechnen und Stichproben belegt, nicht bewiesen. Es gibt keinen Vergleich mit Werten aus der Literatur.

Erweiterungen und Verweise

Verwandtes auf dieser Website; nur das Matroid-Sekretärproblem erweitert das hier gezeigte Modell:

• Mehrere Zuschläge: Das Matroid-Sekretärproblem erlaubt mehrere Zuschläge, solange sie zusammen zulässig bleiben, und misst Stichprobenregeln gegen das Optimum des Offline-Greedy (ein Greedy-Verfahren, das alle Angebote vorab kennt).
• Verwandtes Modell mit bekannten Verteilungen: Die Einzelgut-Auktion legt bei bekannten Verteilungen der Werte ein Mindestgebot fest.
• Viele Entscheidungen statt einer: Die Online-Allokation entscheidet über viele Buchungen mit Preisen für knappen Platz.

Quellen

• Dynkin zur Regel mit Wartezeit und dem Anteil \(1/e\); Ferguson: Who Solved the Secretary Problem?, Statistical Science 4 (1989), zu Geschichte und Lösung.
• Krengel und Sucheston zur Prophet-Ungleichung; Samuel-Cahn (1984) zur Schwelle am Median des Maximums. Die Schwelle \(\mathbb{E}[\max]/2\) wird Kleinberg und Weinberg (2012) zugeschrieben.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/sekretaerproblem-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Namen und Zuordnung stammen aus der Dokumentation der Demo, die die Volltexte ebenfalls nicht eingesehen hat, und aus dem Gedächtnis, nicht im Original geprüft; die Zuschreibung an Kleinberg und Weinberg beruht nur auf Sekundärquellen. Die Herleitungen und das durchgerechnete Beispiel sind Rechnungen dieser Seite und keine Messungen der Demo.