Wenn wir die Zahlen $1$ bis $n$ auf Plättchen schreiben, in einen Sack werfen, und dann $k$ Plättchen ohne zurücklegen herausnehmen, wie groß ist dann im Erwartungswert die kleinste gezogene Zahl?
Wir müssen etwas ausholen. Für eine Menge $A$ ist
\begin{align*} {A \choose k} := \{B \subseteq A \ | \ |B| = k \} \ , \end{align*}die Menge aller $k$-elementigen Untermengen. Die Größe der Menge
\begin{align*} \left|{A \choose k} \right| \end{align*}hängt nicht von den Elementen in $A$ ab, sondern nur von deren Anzahl $n$. Wir definieren daher
\begin{align} {n \choose k} := \left|{A \choose k} \right| \ , \label{binomial-coefficient} \end{align}wobei $A$ eine beliebige Menge der Größe $n$ ist. Sie kennen vielleicht die Formel ${n \choose k} = \frac{n!}{k!(n-k)!}$, in diesem Teilkapitel will ich allerdings vermeiden, sie zu verwenden. Nehmen Sie (\ref{binomial-coefficient}) als Definition von ${n \choose k}$.
Problem Sei $A = \{1, \dots, n\}$. Wir wählen eine Menge $\{Y_1, \dots, Y_k\}$ gleichverteilt aus der Menge ${A \choose k}$ (auf Deutsch: wir ziehen $k$ Zahlen ohne Zurücklegen) und setzen $Y := \min \{Y_1, \dots, Y_k\}$.
Was ist $\E[Y]$?
Beispiel: $k=1$. Wir können den Erwartungswert ganz einfach nach seiner Formel berechnen:
\begin{align*} \E[Y] & = \sum_{i=1}^n i \cdot \Pr[Y = i] ]\\ & = \sum_{i=1}^n i \cdot \frac{1}{n} = \frac{{n + 1 \choose 2}}{n} \\ & = \frac{n+1}{2} \ . \end{align*}Beispiel: $k=2$. Wir gehen genau gleich vor. Was ist $\Pr[Y = i]$? Damit das Minimum von $\{Y_1, Y_2\}$ gleich $i$ ist, muss das eine $i$ sein und das andere aus $\{i+1, \dots, n\}$. Es gibt also $n-i$ Mengen $\{Y_1, Y_2\}$ mit Minimum $i$, von insgesamt ${n \choose 2}$ möglichen Mengen. Daher:
\begin{align*} \E[Y] & = \sum_{i=1}^n i \cdot \Pr[Y = i] ]\\ & = \sum_{i=1}^n i \cdot \frac{n-i}{{n \choose 2}} \\ & = \frac{1}{{n \choose 2}} \left( n \cdot \sum_{i=1}^n i - \sum_{i=1}^n i^2\right) \ . \end{align*}Die erste Summe ist das altbekannte $\frac{n(n+1)}{2}$. Für die zweite Summe kennt (oder Sie persönlich) eine Formel:
\begin{align*} \sum_{i=1}^n i^2 & = \frac{n(n+1)(2n+1)}{6} \ . \end{align*}Jetzt können wir $\E[Y]$ weiter ausrechnen:
\begin{align*} \E[Y] & = \dots = \frac{1}{{n \choose 2}} \left( n \cdot \sum_{i=1}^n i - \sum_{i=1}^n i^2\right) \\ & = \frac{1}{{n \choose 2}} \left( n \cdot \frac{n(n+1)}{2} - \frac{n(n+1)(2n+1)}{6}\right) \\ & = \frac{n(n+1)}{{n \choose 2}} \left( \frac{n}{2} - \frac{2n+1}{6}\right)\\ & = \frac{2 n(n+1)}{n (n-1)} \cdot \frac{n-1}{6}\\ & = \frac{n+1}{3} \ . \end{align*}Für $k=1$ ist der Erwartungswert des Minimums gleich $\frac{n+1}{2}$, für $k=2$ ist er $\frac{n+1}{3}$. Ist er denn dann auch $\frac{n+1}{k+1}$ für allgemeines $k$? Wenn wir den Rechenweg vom obigen Beispiel $k=2$ für $k=3$ weitergehen, dann werden wir wahrscheinlich irgendwo der Summe $\sum_{i=1}^n i^3$ begegneen. Dafür gibt uns Google vielleicht noch eine Formel. Für allgemeines $k$ werden wir die Summe $\sum_{i=1}^n i^k$ antreffen, und da wird es schwierig mit einer einfachen allgemeinen Formel. Glücklicherweise haben wir einen alternativen Weg, den Erwartungswert zu berechnen, nämlich mit Hilfe von
Lemma Sei $Y$ das Minimum $k$ zufällig und ohne Zurücklegen gewählter Zahlen in $\{1,\dots,n\}$. Dann gilt $\E[Y] = \frac{n+1}{k+1}$.
Beweis. Mit rechnen wir
$\E[Y] = \sum_{i=1}^n \Pr[Y \geq i]$. Damit $Y \geq i$ ist, müssen $Y_1,\dots,Y_k$ alle mindestens $i$ sein, also $\{Y_1,\dots, Y_k\} \subseteq \{i, \dots, n\}$. Somit ist \begin{align*} \Pr[Y \geq i] & = \frac{\left| { \{i, i+1, \dots, n\} \choose k} \right|}{{n \choose k}} = \frac{{n-i+1 \choose k}}{{n \choose k}} \end{align*}und
\begin{align*} \E[Y] & = \sum_{i=1}^n \frac{{n-i+1 \choose k}}{{n \choose k}} \\ & = \sum_{j=1}^n \frac{{j \choose k}}{{n \choose k}} \tag{Wechsel zu $j := n-i+1$.} \end{align*}Mit (siehe weiter unten) folgt nun
\begin{align*} E[Y] & = \dots = \sum_{j=1}^n \frac{{j \choose k}}{{n \choose k}} = \frac{{n+1\choose k+1}}{{n \choose k}} \end{align*}Im Lemma beginnt die Summe zwar bereits bei $j=0$, allerdings spielt das bei $k \geq 1$ keine Rolle, da ${0 \choose k}$ da eh $0$ ist. Dass das $\frac{n+1}{k+1}$ ist, können wir einfach mit der Formel ${a \choose b} = \frac{a!}{b!(a-b)!}$ herleiten. Mehr Spaß macht es aber, wenn man sich kombinatorisch überlegt, dass ${n+1 \choose k+1} \cdot (k+1) = {n \choose k} \cdot (n+1)$ gilt:
Nun die andere Seite:
Und somit haben wir $\E[Y] = \frac{n+1}{k+1}$ gezeigt.\(\square\)
Lemma Für alle $n, k \in \N$ gilt $\sum_{j=0}^n {j \choose k} = {n+1 \choose k+1}$.
Beweis. Sei $S := {\{1, \dots, n+1\} \choose k+1}$ die Menge aller $I \subseteq \{1, \dots, n+1\}$ mit $|I| = k+1$. Wir zerlegen $S$ in Teilmengen $S_1, \dots, S_{n+1}$, je nach Maximum, also
\begin{align*} S_i := \{ I \in S \ | \ \max(I) = i \} \end{align*}Die Mengen $S_1, \dots, S_{k}$ sind natürlich leer; $S_{k+1}$ besteht hat nur ein einziges Element, es gilt $S_{k+1} = \{ \{1, 2, \dots, k, k+1 \}\}$. Ganz allgemein: wie groß ist $S_i$? Wenn $I \in S_i$, dann gilt $\max(I) = i$, und alle anderen $k$ Elemente von $I$ sind kleiner, also in $\{1,\dots,i-1\}$. Daher: $|S_i| = {i-1\choose k}$. und somit gilt
\begin{align*} {n+1 \choose k+1} & = |S| = \left|\bigcup_{i=1}^{n+1} S_i \right| \\ & = \sum_{i=1}^{n+1} |S_i|= \sum_{i=1}^{n+1} {i-1 \choose k} = \sum_{i=0}^n {i \choose k} \ , \end{align*}und das Lemma ist bewiesen. \(\square\)
Die Formel $\E[Y] = \frac{n+1}{k+1}$ hat auch eine ganz intuitive Interpretation: die $k$ zufällig gewählten Zahlen teilen den Raum $\{1, \dots, n\}$ in $k+1$ Intervalle, und das Minimum ist einfach die Länge des ersten Intervalls. Kann man diese Intuition rigoros machen? Versuchen wir's:
Zweiter Beweis von . Unseren $k$ zufälligen Zahlen $Y_1, \dots, Y_k$ fügen wir eine weitere hinzu: $Y_0 := 0$. Das Minimum $Y := \min \{Y_1, \dots, Y_k\}$ ist nun einfach der Abstand von $Y_0$ zum nächsten $Y_i$. Wir stellen uns die Menge $\{0,1, \dots, n\}$ als große Uhr vor:
Jetzt rotieren wir die Uhr um einen zufälligen Wert $R \in \{0, \dots, n\}$. Formal setzen wir $Z_i := Y_i + R \mod (n+1)$:
Jetzt haben wir im Prinzip einfach $k+1$ viele von den $n+1$ Stellen ausgewählt, dort Punkte hingesetzt und einen rot gefärbt und die anderen blau. Unser Minimum $Y$ ist der Abstand vom roten Punkt zum im Uhrzeigersinn nächsten blauen.
Jetzt führen wir das Zufallsexperiment nochmals auf andere aber äquivalente Weise durch. Wir wählen zuerst $k+1$ violette Punkte:
und nun wählen wir daraus einen aus, färben ihn rot und färben die anderen $k$ Punkte blau. Das ist offenbar zum vorherigen Experiment äquivalent. Allerdings fügen wir noch einen Zwischenschritt ein: wir messen die $k+1$ Abstände zwischen den Punkten und nennen sie $D_1, \dots, D_{k+1}$:
Wenn wir nun einen Punkt zufällig rot wählen und als $Y$ den Abstand zum im Uhrzeigersinn nächsten ausgeben, dann können wir das abkürzen, indem wir einfach $I \in \{1, \dots, k+1\}$ wählen und $D_I$ ausgeben. Es gilt also
\begin{align*} \E[Y] & = \E_{I \in \{1,\dots,k+1\}} [D_I] = \sum_{i=1}^{k+1} \Pr[I=i] D_I \\ & = \sum_{i=1}^{k+1} \frac{1}{k+1} D_I \\ & = \frac{n+1}{k+1} \ , \end{align*}da die $D_i$ sich ja zu $n+1$ aufsummieren.\(\square\)