Mathematische Untersuchung der Strategie

Die Strategie der vier ist, die ersten $r$ der $N$ Bewerber*innen abzulehnen und danach die erste Person zu nehmen, die besser als die ersten $r$ Bewerber*innen ist. Emmy will nun $r$ so wählen, dass die Wahrscheinlichkeit $P\left(r\right)$ , mit dieser Strategie die beste Person zu finden, maximal ist. Dafür muss sie $P\left(r\right)$ in Abhängigkeit von $r$ berechnen.

Emmy geht die einzelnen Kandidat*innen nach den ersten $r$ Leuten durch und berechnet jeweils die Wahrscheinlichkeit, dass die Person die beste Wahl ist und sie mit der Strategie ausgewählt wird.

$r + 1$ ste Person

Was ist die Wahrscheinlichkeit, dass sie die beste Wahl ist und sie mit der Strategie ausgewählt wird?

Die Wahrscheinlichkeit, dass sie die beste Person ist, ist wieder $\frac 1N$ .

Weil sie die beste Person ist, ist sie auch besser als die ersten $r$ Personen. Weil sie direkt nach den abgelehnten $r$ Personen kommt und besser als sie ist, wird sie auch ausgewählt. Also ist die Wahrscheinlichkeit, dass sie ausgewählt wird, $1$ .

Insgesamt ist die Wahrscheinlichkeit, dass die $r + 1$ ste Person die beste ist und ausgewählt wird, gleich $\frac{1}{N}\cdot 1=\frac{1}{N}$ .

Wie sieht es mit der nächsten Bewerbung aus?

$r + 2$ te Person

Was ist die Wahrscheinlichkeit, dass sie die beste Wahl ist und sie mit der Strategie ausgewählt wird?

Dass Person $r + 2$ die beste ist, gilt mit einer Wahrscheinlichkeit von $\frac 1N$ .

Wir wählen Person $r + 2$ genau dann aus, wenn der*die Bewerber*in $r + 1$ nicht besser war als die ersten $r$ Personen. Mit welcher Wahrscheinlichkeit ist Person $r + 1$ besser als die ersten $r$ Bewerber*innen? Das ist der Fall, wenn die beste Person aus den Bewerber*innen $1,\ldots, r+1$ Person $r + 1$ ist. Das gilt mit einer Wahrscheinlichkeit von $\frac 1{r+1}$ .

Unsere gesuchte Wahrscheinlichkeit ist also

\displaystyle 1-\frac 1{r+1}=\frac r{r+1}.

Insgesamt ist die Wahrscheinlichkeit dafür, dass die $r + 2$ te Person die beste ist und mit dieser Strategie ausgewählt wird, gleich $\frac1N\cdot\frac{r}{r+1}$ .

Was gilt allgemeiner für die $i$ te Person, die nach den ersten $r$ kommt?

$i$ te Person mit $i > r$

Was ist die Wahrscheinlichkeit, dass sie die beste Wahl ist und sie mit der Strategie ausgewählt wird?

Die Person $i$ ist die beste mit einer Wahrscheinlichkeit von $\frac 1N$ .

Wir wählen sie genau dann aus, wenn die Personen $r+1, \ldots , i-1$ nicht besser sind als die beste der ersten $r$ Personen. Mit welcher Wahrscheinlichkeit ist keine der Personen $r+1,\ldots,i-1$ besser als die ersten $r$ Personen? Das gilt genau dann, wenn die beste der ersten $i - 1$ Personen eine der Personen $1,\ldots,r$ ist. Die Wahrscheinlichkeit dafür ist

\displaystyle \frac r{i-1}.

Insgesamt ist die Wahrscheinlichkeit, dass die $i$ te Person die beste Wahl ist und mit der Strategie ausgewählt wird, gleich $\frac1N\cdot \frac{r}{i-1}$ .

Die Gesamtwahrscheinlichkeit, mit der Strategie die beste Person auszuwählen, ist die Summe der einzelnen Wahrscheinlichkeiten für die einzelnen Personen:

\displaystyle P=P(r)=\sum_{i=r+1}^N\frac{1}{N}\cdot\frac{r}{i-1}

Emmy präsentiert die Wahrscheinlichkeit stolz ihren Freunden.

Bertrand ist noch nicht zufrieden. "Wie sollen wir nun das richtige $r$ finden, für das $P (r)$ maximal ist?", fragt er.

"Das ist ja einfach eine Extremwertaufgabe", meint Carl, "ich weiß, wie das geht, da muss man die Ableitung von $P (r)$ finden und herausfinden, für welches $r$ die Ableitung Null ist!"

"Wie willst du denn bitte diese Funktion nach $r$ ableiten?!", entgegnet Maryam. "Siehst du nicht, dass auch der Index der Summe von $r$ abhängt?"

"Ich hab da eine Idee", meint Emmy. "Wir können die Summe durch ein Integral abschätzen."

\displaystyle P(r)=\sum_{i=r+1}^N\frac{1}{N}\cdot\frac{r}{i-1}\approx\frac{1}{N}\int_{r+1}^{N+1}\frac{r}{x-1}\mathrm{dx}^{ }

"Die Summe ist dann die linke Riemannsumme des Integrals", erklärt Emmy.

Abb.1: Linke Riemannsumme der Funktion $\frac{1}{x}$

"Das Integral können wir ganz leicht berechnen", fährt Emmy fort.

\displaystyle \frac{1}{N}\int_{r+1}^{N+1}\frac{r}{x-1}\mathrm{dx}=-\frac{r}{N}\ln\left(\frac{r}{N}\right)

"Das ging mir jetzt zu schnell! Wie hast du denn das Integral berechnet?", fragt Bertrand.

"Cool, das kann ich nun nach $r$ ableiten!", behauptet Carl und fängt an zu rechnen. Nach einem kurzen Moment zeigt er den anderen sein Ergebnis:

\displaystyle \frac{\mathrm{d}}{\mathrm{d}r}\left(-\frac{r}{N}\ln\left(\frac{r}{N}\right)\right)=-\frac 1N\ln\left(\frac rN\right)-\frac rN \cdot\frac Nr\frac 1N =-\frac 1N\left(\ln\left(\frac rN\right)+1\right)

Carl fährt fort: "Wir brauchen also ein $r$ , so dass

\displaystyle -\frac 1N\left(\ln\left(\frac rN\right)+1\right)=0.

Das gilt genau dann, wenn

\displaystyle \ln\left(\frac rN\right)=-1.

Also muss gelten $\frac rN=\frac 1e.$ "

"Wir haben unser $r$ gefunden!", meint Maryam.

\displaystyle r=\frac Ne

"Ist das nun auch ein Maximum der Funktion?", fragt Bertrand. "Es könnte ja auch ein Minimum oder ein Terrassenpunkt sein."

"Gute Frage! Lasst uns die Funktion $-\frac 1N\left(\ln\left(\frac rN\right)+1\right)$ aufmalen, dann sehen wir schon, ob unser $r$ ein Maximum ist", schlägt Carl vor.

Graph der Funktion $-\frac{x}{73}\ln\left(\frac{x}{73}\right)$

"Ah, es gibt ein Maximum bei unserem $r$ . Das heißt, für $r=\frac Ne$ ist die Erfolgswahrscheinlichkeit unserer Strategie maximal", meint Maryam.

"Das stimmt nicht ganz.", entgegnet Bertrand, "wir haben die Summe ja nicht genau bestimmt sondern nur abgeschätzt. Außerdem können wir $r$ in Echt nur als ganze Zahl wählen, aber bei uns ist

\displaystyle \frac{N}{e}=\frac{73}{e}\approx 26{,}86.

Wir können nicht $26,86$ Personen ablehnen, sondern nur $26$ oder $27$ ."

"Ok, alles ist nur abgeschätzt. Aber was ist denn nun die Wahrscheinlichkeit, dass die Strategie funktioniert, wenn wir $r=\frac{N}{e}$ wählen?", fragt Maryam.

$P(r)\approx -\frac rN \ln\left(\frac rN\right)\approx -\frac{N}{eN}\ln\left( \frac{N}{eN}\right)=-\frac 1e\ln\left(\frac 1e\right)=\frac 1e\approx 36{,}79\%$

"Wow, also mit einer Wahrscheinlichkeit von ungefähr $36{,}79\%$ finden wir mit der Strategie die beste Person!", ruft Carl.

Quellen:

Abb. 1: zugeschnittenes Bild Lefthand-Riemann-Sum-Integral-Test von Lazauya, CC BY-SA 4.0, via Wikimedia Commons

4Mathematische Untersuchung der Strategie