Tabelle

Folgende Tabelle zeigt die Anzahl ${\displaystyle r}$ der abgelehnten Bewerber, die maximalen Wahrscheinlichkeiten, die mittlere Platzierung des ausgewählten Bewerbers und die mittlere Anzahl der Einladungen für ${\displaystyle n\leq 20}$ Bewerber:

Beweis

Der beste Bewerber kann die Wahl nur gewinnen, wenn er sich nicht unter den ersten ${\displaystyle r}$ Probekandidaten befindet. Kommt er direkt danach auf Platz ${\displaystyle r+1}$, gewinnt er. Die Wahrscheinlichkeit, dass er auf diesem Platz steht, beträgt ${\displaystyle {\tfrac {1}{n}}}$. Steht er einen Platz weiter auf Platz ${\displaystyle r+2}$, wieder mit der Wahrscheinlichkeit ${\displaystyle {\tfrac {1}{n}}}$, so gewinnt er genau dann, wenn sich der beste der vorherigen Kandidaten unter den ersten ${\displaystyle r}$ Probekandidaten befindet. Das ist mit der Wahrscheinlichkeit ${\displaystyle {\tfrac {r}{r+1}}}$ der Fall, zusammengesetzt gibt das die Wahrscheinlichkeit ${\displaystyle {\tfrac {1}{n}}\cdot {\tfrac {r}{r+1}}}$.

Geht man die Fälle entsprechend weiter durch bis zur letzten Position für den Besten, so erhält man wieder als Wahrscheinlichkeit für diese Position ${\displaystyle {\tfrac {1}{n}}}$ und für die Wahrscheinlichkeit, dass der beste Vorgänger zu den ersten ${\displaystyle r}$ Probekandidaten gehörte, die Wahrscheinlichkeit ${\displaystyle {\tfrac {r}{r+n-r-1}}={\tfrac {r}{n-1}}}$, zusammen also ${\displaystyle {\tfrac {1}{n}}\cdot {\tfrac {r}{n-1}}}$.

Insgesamt ergibt sich die Wahrscheinlichkeit ${\displaystyle P}$ für einen Erfolg der Strategie zu:

${\displaystyle P=\sum _{a=r+1}^{n}{\frac {1}{n}}\cdot {\frac {r}{a-1}}={\frac {r}{n}}\sum _{a=r}^{n-1}{\frac {1}{a}}}$

Für die Summe macht man die mit wachsendem ${\displaystyle n}$ immer besser werdende Integral-Näherung:

${\displaystyle P\approx {\frac {r}{n}}\cdot \int _{r}^{n}{\frac {1}{a}}\ da=-{\frac {r}{n}}\cdot \ln \left({\frac {r}{n}}\right)}$

Das Maximum nimmt dieser Näherungsausdruck dort an, wo seine Ableitung gleich 0 ist, nämlich an der Stelle ${\displaystyle r={\tfrac {n}{e}}}$. Es beträgt ${\displaystyle {\tfrac {1}{e}}\approx 0{,}368}$. Das Maximum ist nicht sehr ausgeprägt: für den weiten Bereich ${\displaystyle {\tfrac {n}{4}}\leq r\leq {\tfrac {n}{2}}}$ wird nämlich durchweg ${\displaystyle {\tfrac {\ln(2)}{2}}\approx 0{,}346}$ nie unterschritten. Eine genauere auf der Odds-Strategie beruhende Analyse zeigt jedoch mehr, nämlich dass die Erfolgswahrscheinlichkeit immer strikt größer als ${\displaystyle {\tfrac {1}{e}}\approx 0{,}368}$ ist, also stets strikt größer als die asymptotische Erfolgswahrscheinlichkeit, wenn die Anzahl der Bewerber gegen unendlich strebt.

Bezieht man den Zweitbesten in die obige Strategie mit ein, so nähert sich die Wahrscheinlichkeit dafür, dass dieser ausgewählt wird, für große ${\displaystyle n}$ dem Wert ${\displaystyle {\tfrac {1}{e^{2}}}}$. Insgesamt wird damit die Wahrscheinlichkeit, dass man durch diese Strategie den besten oder zweitbesten Kandidaten erhält, für große ${\displaystyle n}$ etwas größer als 50 %.

Unbekannte Anzahl N von Optionen

Der Hauptnachteil des klassischen Sekretärinnenproblems für mögliche Anwendungen ist die Tatsache, dass die Anzahl ${\displaystyle N}$ der Optionen (Kandidaten) als im Voraus bekannt vorausgesetzt wird. Eine Möglichkeit dies zu umgehen ist anzunehmen, dass die Verteilung ${\displaystyle P(N=k)}$ dieser Anzahl bekannt ist. In diesem Modell ist es jedoch im Allgemeinen schwieriger, die optimale Lösung zu bestimmen. Hinzu kommt insbesondere, dass die optimale Gewinnwahrscheinlichkeit oft wesentlich kleiner ist. Es ist intuitiv klar, dass die Unkenntnis der Anzahl ${\displaystyle N}$ von Optionen ihren Preis haben sollte, doch dieser Preis ist oft sehr hoch. Tatsächlich wird in einigen Fällen die optimale Gewinnwahrscheinlichkeit praktisch null. Eine geschickte Umformulierung dieses Modells löst dieses Problem.

Beste mittlere Platzierung

Wenn die Aufgabe stattdessen darin besteht, bei einer vorher bekannten Anzahl von Kandidaten im Mittel einen Kandidaten mit einer möglichst guten Platzierung auswählen, ist folgende Strategie notwendig:

• Es wird zunächst eine bestimmte Anzahl von Kandidaten abgelehnt.
• Anschließend wird der erste Kandidat akzeptiert, der unter den bisher betrachteten Kandidaten mindestens eine bestimmte Platzierung erreicht.

Diese Platzierungen, jeweils die mittlere Platzierung für den ausgewählten Kandidaten und die mittlere Anzahl der Einladungen sind für bis zu 16 Kandidaten in folgender Tabelle aufgelistet: