Stellen Sie sich vor, Sie besitzen eine kleine Wohnung in Heidelberg, die Sie gerne zu einem fairen Preis vermieten möchten. Da Sie es bevorzugen, sich von Angesicht zu Angesicht zu unterhalten und nicht über E-Mail oder Telefon, beschließen Sie, einen offenen Besichtigungstermin anzubieten, an dem alle Interessenten teilnehmen können. An besagtem Tag fahren Sie zum Mietobjekt und stellen mit Erschrecken fest, dass eine riesige Menschenmenge aufgetaucht ist.

Ihnen wird sofort klar: Mit allen ein persönliches Gespräch zu führen, wird Stunden in Anspruch nehmen. Um Zeit und Aufwand zu begrenzen, möchten Sie den Bewerberinnen und Bewerbern direkt nach einer kurzen Unterhaltung eine Zu- oder Absage erteilen. Allerdings sind Sie, was die Auswahl des künftigen Mieters angeht, recht anspruchsvoll. Daher suchen Sie nach einer Strategie, um einen geeigneten Kandidaten auszuwählen, möglichst ohne mit allen sprechen zu müssen. Wie könnte eine passende Vorgehensweise aussehen?

Bereits 1961 fand Dennis Victor Lindley heraus, dass das Problem tatsächlich eine optimale Lösung besitzt: Sie sollten mit den ersten 37 Prozent der Bewerberinnen und Bewerber sprechen – und sie allesamt ablehnen. Dann führen Sie die Gespräche fort und akzeptieren die erste Person, die besser passt als die bisher abgelehnten. Die Wahrscheinlichkeit, so die beste Kandidatin oder den besten Kandidaten zu finden, liegt dann bei 37 Prozent.

Diese Strategie gibt allerdings nicht an, wie viele Gespräche Sie insgesamt führen werden. Wenn sich der ideale Mieter etwa unter den ersten 37 Prozent befindet, werden Sie sich am Ende mit jeder Person unterhalten müssen – und schließlich den letzten Kandidaten auswählen, da Sie allen anderen in diesem Szenario bereits abgesagt haben. Ist der ideale Mieter hingegen unter den verbliebenen 63 Prozent, dann wählen Sie zwangsläufig jemanden aus, der nach Ihrer Vorstellung besser für die Wohnung geeignet ist als die ersten 37 Prozent. Ihre Wahl kann dann auf den am besten passenden Kandidaten fallen – aber auch auf einen der nächstbesten, der noch nicht im ersten Block der Abgelehnten enthalten war.

Eine ideale Lösung zu vielen Problemen

In der Literatur ist die Aufgabe häufig unter der – in meinen Augen etwas angestaubten – Bezeichnung des Sekretärinnenproblems anzutreffen: Eine Firma möchte eine vakante Assistentenstelle besetzen und muss unter den (natürlich ausnahmslos weiblichen) Bewerberinnen die am besten geeignete auswählen. Eine andere Variante ist das Heiratsproblem, bei dem eine Person nach einem passenden Partner sucht. Ebenso kann man die Aufgabe auf alltagsnahe Situationen beziehen, etwa wenn man auf einer langen Autobahnfahrt nach einer günstigen Tankstelle sucht oder sich in der privilegierten Lage befindet, unter einer Vielzahl von Jobangeboten zu wählen.

Es war der Wissenschaftsjournalist Martin Gardner, der das Problem 1960 in seiner monatlichen Kolumne »Mathematical Games« in »Scientific American« populär machte. Er präsentierte es jedoch in einem ganz anderem Gewand, indem er ein Spiel zwischen zwei Personen beschrieb: Die erste notiert irgendwelche Zahlen beliebiger Größe auf Papierschnipseln und legt sie verdeckt auf einen Tisch. Der zweite Spieler dreht nacheinander die Zettel um – und soll dann stoppen, wenn er glaubt, dass die gezeigte Zahl die größte ist, die im gesamten Spiel auftaucht.

Der Weg zu den 37 Prozent

Auch hier empfiehlt es sich, die ersten 37 Prozent der Zettel aufzudecken und dann die erste Zahl auszuwählen, die größer als alle vorherigen ist. Um zu verstehen, wie dieses Ergebnis zu Stande kommt, muss man das Spiel in eine mathematische Aufgabe übersetzen. Angenommen, es gibt n Zettel mit verschiedenen Zahlen. Man muss erst eine repräsentative Auswahl gesehen haben, um mit einer gewissen Wahrscheinlichkeit beurteilen zu können, ob ein Wert der größten Zahl des Spiels entsprechen könnte. Das heißt, man muss zwangsläufig r Karten umdrehen, um sich einen Eindruck zu verschaffen. Dann wählt man jenen Wert unter den verbleibenden n − r Zettel als Sieger aus, der alle bisherigen übersteigt. Die mathematische Frage lautet: Welches r maximiert die Wahrscheinlichkeit, die richtige Wahl zu treffen?

Dafür kann man alle Situationen durchgehen, in denen man gewinnen würde – und die dazugehörigen Wahrscheinlichkeiten summieren. So gelangt man zu einer Gesamtwahrscheinlichkeit für den Sieg in Abhängigkeit von r. Die größte Zahl darf sich nicht unter den ersten r Zahlen befinden, sonst hat man zwangsläufig verloren. Man gewinnt hingegen automatisch, wenn sie an der r +1-ten Stelle auftritt. Die Wahrscheinlichkeit für diesen Fall beträgt 1/n.

Befindet sich der größte Wert hingegen an der r +2-ten Stelle (wieder eine Wahrscheinlichkeit von 1/n), gewinnt man nur, falls die r +1-te Zahl kleiner als die vorangehenden r Karten ist. Das bedeutet, der beste der bisher aufgedeckten Kandidaten muss sich im Bereich der ersten r Zahlen befinden. Die Chancen dafür betragen r/(r+1). Um die Gewinnwahrscheinlichkeit für diese Situation zu berechnen, muss man die zwei Wahrscheinlichkeiten (höchste Zahl an em>r +2-te Stelle und bisher höchste Karte innerhalb der ersten r Karten) also multiplizieren: 1/n · r/(r+1).

So kann man sich durch alle Stellen weiter durcharbeiten. Liegt die höchste Zahl an der r +3-ten Stelle, darf sich der nächstgrößere Wert wieder nur unter den ersten r Aufdeckungen befinden, so dass man eine Gewinnchance von 1/n · r/(r+2) erhält. Die r +3-te Platzierung berechnet sich entsprechend zu 1/n · r/(r+3) und so weiter.

Die Gesamtwahrscheinlichkeit P für einen Gewinn ergibt sich daher über die Summe $$P = \sum_{k=r+1}^{n} \frac{1}{n}\cdot \frac{r}{k-1}.$$ Diesen Ausdruck kann man umschreiben, um ihn später weiter zu vereinfachen. Dazu verschiebt man den Start- und Endpunkt der Summe und gleicht dafür die zu addierenden Terme an, damit sich das Ergebnis nicht ändert: $$P = \frac{r}{n}\cdot \sum_{k=r}^{n-1} \frac{1}{k}.$$ Liegen nur wenige Karten auf dem Tisch (das heißt, n ist klein), kann man die Summe schnell ausrechnen. Das Ergebnis hängt von r ab – man muss nur noch herausfinden, für welches r die Gewinnwahrscheinlichkeit am größten ist.

Wie viele Karten muss man mindestens umdrehen?

Doch wenn es hunderte oder gar tausende Papierschnipsel gibt, wird es unübersichtlich. Fachleute aus der Statistik greifen dann zu einem beliebten Trick: Sie nähern die Summe durch ein Integral, das sich einfacher auswerten lässt: $$P = \frac{r}{n}\cdot \sum_{k=r}^{n-1} \frac{1}{k} \approx \frac{r}{n}\cdot \int_r^{n} \frac{1}{k} dk.$$ Für dieses kann man die Stammfunktion bestimmen und die Integrationsgrenzen einsetzen: $$ P \approx \frac{r}{n}\cdot \int_r^{n} \frac{1}{k} dk = -\frac{r}{n}\text{ln} \frac{r}{n}.$$

Nun hat man also eine gute Näherung für die Wahrscheinlichkeit, dass man die richtige Entscheidung trifft, wenn man zunächst r Zettel verwirft und auf den nachfolgenden größten Wert setzt. Die Frage ist: Wie viele Papierschnipsel r sollte man beiseitelegen, um die Gewinnchance P möglichst groß zu gestalten? In mathematische Sprache übersetzt: Für welches r wird P maximal? Wenn Sie sich an ihre Schulzeit erinnern, dann wissen Sie, dass man dafür eine Kurvendiskussion machen muss. Das heißt, man leitet die Funktion P nach r ab und bestimmt dann die Nullstellen. Dort findet sich dann ein Extremwert. Die erste Ableitung der Gewinnfunktion lautet: $$ P'(r) \approx -\frac{1}{n}\left(\text{ln} \frac{r}{n} +1\right).$$ Dieser Ausdruck wird null, wenn das Innere der Klammer verschwindet, also: ln(r/n) = −1. Das ist der Fall, wenn r = n/e – das sind zirka 37 Prozent von n.

Setzt man r = n/e in die ursprüngliche Gleichung für die Gewinnwahrscheinlichkeit ein, erhält man das Ergebnis: P = 1/e ≈ 0,37… Damit beträgt die Wahrscheinlichkeit, mit besagter Strategie auf Anhieb die größte Zahl auszuwählen, etwa 37 Prozent. Wie sich allerdings in mehreren psychologischen Studien herausgestellt hat, sind die meisten Menschen zu ungeduldig: Personen, die ähnlichen Problemen ausgesetzt sind, neigen dazu, viel zu schnell eine Entscheidung zu treffen – und nicht erst 37 Prozent der Möglichkeiten abzulehnen. Auf diese Weise erzielt man in der Regel allerdings ein schlechteres Ergebnis. Es empfiehlt sich daher, mehr Geduld zu zeigen.

Was ist euer Lieblingsmathetheorem? Schreibt es gerne in die Kommentare – und vielleicht ist es schon bald das Thema dieser Kolumne!