Wahrscheinlichkeit für Teilmengen / Binomialkoeffizient mit großen Werten berechnen

10.11.2012, 00:08	Calvin	Auf diesen Beitrag antworten »
Wahrscheinlichkeit für Teilmengen / Binomialkoeffizient mit großen Werten berechnen Hallo zusammen, ich habe ein Problem, das ich im Kleinen lösen konnte. Allerdings sind in meinem konkreten Fall die Zahlen sehr groß, so dass ich kein vernünftiges Ergebnis mehr bekomme. Meine zwei Fragen sind, ob mein Ansatz grundsätzlich richtig ist bzw. wie man sich bei großen Zahlen verhält. Es geht darum, dass ich zwei Mengen $\begin{eqnarray} A \end{eqnarray}$ und $\begin{eqnarray} B \end{eqnarray}$ habe, wobei gilt $\begin{eqnarray} B\subset A \end{eqnarray}$ . Diese beiden Mengen sind mir bekannt. Außerdem gibt es noch eine Menge $\begin{eqnarray} C\subseteq A \end{eqnarray}$ , von der ich nur die Anzahl der Elemente kenne. Frage: Wie groß ist die Wahrscheinlichkeit, dass $\begin{eqnarray} C\subseteq B \end{eqnarray}$ ist? In einem kleinen Beispiel habe ich es folgendermaßen gerechnet: $\begin{eqnarray} A=\{0,1,2,3,4\} \end{eqnarray}$ $\begin{eqnarray} B=\{0,1,2\} \end{eqnarray}$ $\begin{eqnarray} C \end{eqnarray}$ enthält 2 Elemente aus $\begin{eqnarray} A \end{eqnarray}$ Für C ergeben sich damit $\begin{eqnarray} \binom{5}{2}=10 \end{eqnarray}$ verschiedene Möglichkeiten, eine zweielementige Teilmenge aus A zu bilden. Außerdem gibt es $\begin{eqnarray} \binom{3}{2}=3 \end{eqnarray}$ Möglichkeiten, eine zweielementige Teilmenge aus B zu bilden. Die Wahrscheinlichkeit, dass $\begin{eqnarray} C\subseteq B \end{eqnarray}$ ist, beträgt in meinen Augen also $\begin{eqnarray} \frac{3}{10}=30% \end{eqnarray}$ Soweit richtig? Jetzt ist für mich das Problem, dass in meinem konkreten Fall die Mengen zwischen $\begin{eqnarray} 10^6 \end{eqnarray}$ und $\begin{eqnarray} 10^9 \end{eqnarray}$ Elemente haben. Da ist die Berechnung des Binomialkoeffizienten natürlich schwierig. Deshalb habe ich versucht, das ganze ein bisschen zu vereinfachen, und zwar mit der Formel $\begin{eqnarray} \binom{n}{k}=\prod_{i=1}^{k} \frac{n+1-i}{i} \end{eqnarray}$ Außerdem setze ich folgende Variablen: Die Anzahl der Elemente aus A ist n. Die Anzahl der Elemente aus B ist m. Die Anzahl der Elemente aus C ist k. Damit ergibt sich: $\begin{eqnarray} \frac{\binom{m}{k}}{\binom{n}{k}}=\prod_{i=1}^{k} \frac{m+1-i}{i} \cdot \prod_{i=1}^{k} \frac{i}{n+1-i}=\prod_{i=1}^k\frac{m+1-i}{n+1-i} \end{eqnarray}$ Kann man das irgendwie vereinfachen, so dass es sich auch bei sehr großen k,m,n berechnen lässt? Oder zumindest abschätzen?
11.11.2012, 14:14	Huggy	Auf diesen Beitrag antworten »
RE: Wahrscheinlichkeit für Teilmengen / Binomialkoeffizient mit großen Werten berechnen Wenn man die beiden Binomialkoeffizienten durch Fakultäten ausdrückt, kürzt sich k! weg. Wenn alle 4 verbleibenden Fakultäten groß sind, könnte man für jede von ihnen die Stirlingsche Formel als Näherung verwenden.
11.11.2012, 14:42	Calvin	Auf diesen Beitrag antworten »
Danke, das könnte helfen. Werde ich mir mal im Detail anschauen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »