Zähltechniken und Wahrscheinlichkeiten

Kombination, Variation und Permutation sind die am häufigsten verwendeten Zähltechniken in der Wahrscheinlichkeitslehre, da sie das Studium von Experimenten mit gleichwahrscheinlichen Ergebnissen erleichtern. Eines der bekanntesten Beispiele für solche Experimente stammt aus Glücksspielen. Diese sind im Allgemeinen nicht-deterministische Prozesse über einem Stichprobenraum \Omega = \{\omega_1, \omega_2, \cdots, \omega_N\}. Diese Experimente haben die gemeinsame Eigenschaft, dass alle Ereignisse der Form \{\omega_i\}\in\mathcal{A}_\Omega, mit i\in\{1,2,\cdots, n\}, die gleiche Eintrittswahrscheinlichkeit haben.

Ausgehend von der Wahrscheinlichkeitsmaß-Definition als Grenzwert relativer Häufigkeiten können wir die Wahrscheinlichkeit eines Ereignisses als Quotient von Kardinalitäten festlegen. Wie wir bereits gesehen haben, geschieht dies durch die Beziehung:

P(E) = \displaystyle \lim_{N\to\infty}g_N(E) = \lim_{N\to\infty}\frac{f_N(E)}{N}= \frac{\# E}{\# \Omega}

Hier bezieht sich das Symbol „#“ auf die Kardinalität der Menge. Dies ist als die Formel der günstigen Fälle über die möglichen Fälle bekannt.

In diesen Situationen reduziert sich die Wahrscheinlichkeitsberechnung auf die Bestimmung der Kardinalität des Stichprobenraums und des zu messenden Ereignisses. Deshalb ist es sehr nützlich, zunächst einige Zähltechniken zu überprüfen.

Herleitung der Zähltechniken

Um Kombinationen, Variationen und Permutationen einzuführen, entwerfen wir einige Experimente mit gleichwahrscheinlichen Ergebnissen und leiten daraus die Zähltechniken ab.

Angenommen, wir haben eine „perfekte Zufallsmaschine“, die aus einer Blackbox, einem Speicher, einer Aktionstaste und einer Reset-Taste besteht. Die Maschine hat die folgenden Eigenschaften:

1. Die Maschine hat nur eine einstellbare Konfiguration: die Kardinalität ihres Stichprobenraums \Omega_N = \{\omega_1,\cdots,\omega_N\}
2. Beim Drücken der Aktionstaste zeigt sie auf dem Bildschirm eines der Elemente aus \Omega_N an.
3. Wenn ein Ergebnis angezeigt wird, wird es im Speicher gespeichert und erscheint nicht erneut, solange es dort gespeichert ist.
4. Wenn die Maschine bereits alle möglichen Ergebnisse angezeigt hat, friert sie ein und zeigt nichts mehr an.
5. Die Reset-Taste löscht den Speicher und die Anzeige auf dem Bildschirm.

Mit dieser Maschine werden wir einige gedachte Experimente entwerfen und ihre Stichprobenräume analysieren.

Experiment 1 (AORm): Auslösen – In Reihenfolge notieren – Zurücksetzen, m-mal wiederholen

Die Maschine wird konfiguriert mit \#\Omega = N und die folgende Abfolge von Schritten wird m\leq N-mal wiederholt:

1. Die Aktionstaste drücken
2. Das Ergebnis in eine geordnete Liste eintragen
3. Zurücksetzen

Am Ende erhalten wir eine geordnete Liste mit m Elementen aus \Omega_N = \{\omega_1,\cdots,\omega_N\}. Diese Liste kann als m-Tupel von \Omega_N interpretiert werden. Mit anderen Worten: Der Stichprobenraum dieses Experiments \Omega_{AORm} hat die Form

\Omega_{AORm}=\Omega_N \times \cdots \times \Omega_N = \Omega_N^m

Daraus folgt, dass \#\Omega_{AORm}=\#\Omega_N^m = N^m.

Experiment 2 (AOk): Auslösen – In Reihenfolge notieren, k-mal wiederholen

Wir konfigurieren die Maschine erneut mit \#\Omega = N und wiederholen k-mal (k\leq N) die folgende Abfolge von Schritten:

1. Die Aktionstaste drücken.
2. Das Ergebnis in eine geordnete Liste eintragen.

Am Ende erhalten wir eine geordnete Liste mit k Elementen aus \Omega_N = \{\omega_1,\cdots,\omega_N\}, wobei kein Element mit einem der vorhergehenden identisch ist.

Da die Maschine grundsätzlich kein mögliches Ergebnis bevorzugt (weil sie vollkommen zufällig ist), kann man ohne Beschränkung der Allgemeinheit annehmen, dass beim ersten Auslösen das Ereignis \{\omega_1\} eintritt, sodass der Stichprobenraum der nächsten Aktion \Omega_N\setminus\{\omega_1\} ist. Analog kann man annehmen, dass beim zweiten Auslösen das Ereignis \{\omega_2\} eintritt; folglich ist der Stichprobenraum der nächsten Aktion von der Form (\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}. Setzen wir dieses Verfahren fort, so hat die k-te Aktion einen Stichprobenraum der Form

(\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}\cdots)\setminus\{\omega_{k-1}\}

Daraus folgt, dass der Stichprobenraum der möglichen Ergebnisse dieses Experiments die Form hat

\Omega_{AOk}= \Omega \times (\Omega_N\setminus\{\omega_1\}) \times ((\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}) \times \cdots \times ((\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}\cdots)\setminus\{\omega_{k-1}\})

Wenn wir die Kardinalität dieser Menge berechnen, erhalten wir

\#\Omega_{AOk}= N \cdot (N-1) \cdot (N-2) \cdots [N-(k-1)]=\displaystyle \frac{N!}{(N-k)!}

Aus diesem Ergebnis ergibt sich die folgende Definition:

Experiment 3 (ADk): Auslösen – Ungeordnet notieren, k-mal wiederholen

Dieses Experiment ist genau wie das vorherige, nur dass nun die Reihenfolge, in der die Elemente von \Omega_N erscheinen, nicht erfasst wird. Das heißt, zwei k-Tupel mit denselben Elementen, aber in unterschiedlicher Reihenfolge, werden jetzt als dasselbe betrachtet. Auf diese Weise, unter Ausnutzung der Tatsache, dass jedes im Experiment AOk erhaltene k-Tupel auf (k)_k=k! verschiedene Weisen geschrieben werden kann, ergibt sich, dass die Kardinalität des Stichprobenraums dieses Experiments die Form hat

\#\Omega_{ADk} = \displaystyle \frac{\#\Omega_{AOk}}{(k)_k} = \frac{(N)_k}{k!} = \frac{N!}{k!(N-k)!}

Daraus kann folgende Definition aufgestellt werden:

Mit den Zähltechniken der Permutation, Variation und Kombination können wir nun die Größe einer großen Vielfalt von Mengen bestimmen.