Zur Hauptseite ..\ | zur Glossarseite Ohne Frames

# Sekretärinnenproblem

Eine Firma möchte aus einer Reihe von Bewerbungen die am besten geeignete Kandidatin herausfinden, und zwar unter den folgenden Nebenbedingungen:

- Jede Kandidatin wird maximal einmal vorgeladen,

- Die Firma muss nach jeder Vorladung eine endgültige Entscheidung treffen: Entweder Ablehnung oder Zusage.

- Nach der ersten Zusage werden keine weiteren Bewerberinnen mehr vorgeladen.

- Die Anzahl der Bewerberinnen ist von vorne herein bekannt.

Die genaue Aufgabenstellung lautet:

Suche nach derjenigen Strategie, die die Wahrscheinlichkeit des Auffindens ausschliesslich der besten Kandidatin maximiert.

(Alle anderen Kandidatinnen sind gleichermassen uninteressant)

Der allgemeine Versuchsrahmen ist vorgegeben: Man schaut sich eine Reihe Bewerberinnen an und entscheidet sich irgendwann einmal für die momentan Anwesende.

Es liegt intuitiv nahe, dass man sich erst einmal einen Teil der Bewerberinnen anschaut, um sich ein Bild von der generellen Lage zu machen. "Anschauen" ist hier mit "Ablehnen" gleichzusetzen.

Ansatz:

Sei "Anna" die Beste von Allen, die mit der zu suchenden Strategie gefunden werden soll.

Sei ferner "Berta" die Beste unter denjenigen, die vor Anna kommen.

Wenn Anna in der ersten Gruppe ist, wird sie nicht gefunden, da ja alle Teilnehmer der ersten Gruppe abgelehnt werden.

Wenn Anna in der zweiten Gruppe ist, dann wird sie nur dann gefunden, wenn in der zweiten Gruppe vor ihr nur Bewerberinnen kommen, die schlechter sind als die Beste der ersten Gruppe ("Berta").

Ob Berta unter Allen die Zweit-, Dritt- oder X-Beste ist, braucht nicht zu interessieren.

Entscheidend ist lediglich, dass Berta die Beste ist, die zeitlich vor Anna auftaucht, UND dass Berta sich in der ersten Gruppe befindet und nicht in der zweiten Gruppe vor Anna.

Wenn also Anna an der Stelle x kommt, dann muss die Zusammensetzung der Kandidatinnen vor x so sein, dass

Berta (synonym für die Beste, die zeitlich vor Anna auftaucht) in der ersten Gruppe ist.

Nun sei die Grösse der ersten Gruppe a, die Gesamtzahl der Bewerberinnen n,

und die Stelle, an der Anna kommt, x >a.

Die Wahrscheinlichkeit p, dass die an der Stelle x>a befindliche Anna gefunden wird, beträgt nach obigen Erklärungen p = .

Für die Gesamtwahrscheinlichkeit P, dass Anna gefunden wird, muss man x von a+1 bis n hochzählen und aufsummieren.

, bzw.

Diese Gleichung enthält a als Parameter, der so zu wählen ist, dass P maximal wird.

Mit grösser werdendem a wächst zwar der Vorfaktor a/n; die Summe wird aber kleiner, da die Anzahl Glieder kleiner wird. Da sich die Anzahl der Summanden ändert, kann man den Ausdruck nicht einfach nach a ableiten und nullsetzen.

Allerdings kann man den Ausdruck für a+1 von demjenigen Ausdruck für a abziehen und dasjenige a finden, für das der resultierende Ausdruck möglichst nahe bei Null liegt.

So erhält man unmittelbar die Bedingung.

Dies sauber zu lösen erfordert etwas höheren mathematischen Formalismus.

Wir begnügen uns mit einem mathematisch "schlampigen", jedoch anschaulichen Weg.

Die "Schlampigkeit besteht darin, "einfach so" vom diskreten in den kontinuierlichen Fall überzugehen.

Die zuletzt dargestellte Bedingung bekommt dann die Gestalt:

Für sehr grosse n (und daraus folgend sehr grosse a) ist n~n-1 und a~a+1, und es folgt:

= was weiterhin 1 ergeben muss.

Per Auge erkennt man, dass dies für a=n/e erfüllt ist, wobei e = 2,71828....., bzw. 1/e = 0,368....

--> Die Grösse der ersten Gruppe ist so zu wählen, dass die ersten 36,8 % der Bewerberinnen darin enthalten sind.

Die Teilnehmer dieser Gruppe sind alle abzulehnen. Diejenige Teilnehmerin, die als Erste der zweiten Gruppe besser ist als die Beste der ersten Gruppe, ist zu wählen und das Auswahlverfahren abzubrechen.

In dieser Exceltabelle ist das Sekretärinnenproblem für n = 10, 100 und 1000 visualisiert.