Kombinatorisches Problem: Schwarze und weiße Bälle werden in k Gruppen mit Grenzen aufgeteilt und als nächstes wird eine Folge von nur schwarzen Bällen ausgewählt.

Question

Kombinatorisches Problem: Schwarze und weiße Bälle werden in k Gruppen mit Grenzen aufgeteilt und als nächstes wird eine Folge von nur schwarzen Bällen ausgewählt.

Mathematik
Wahrscheinlichkeit
Kombinatorik
Diskrete Mathematik
Binomialkoeffizienten
Wahrscheinlichkeitsverteilungen

SugerBoy

Ich habe folgendes kombinatorisches Problem: Nehmen wir an, wir haben $N$ Bälle: $W$ weiß und $B$ schwarze Kugeln ( $N = B + W$ ).

Schritt 1: Als erstes teilen wir diese zufällig auf $N$ Kugeln hinein $K$ Behälter, wobei jeder Behälter hat $n = \frac{N}{K}$ Bälle. Das Einteilen der Bälle in die Behälter erfolgt natürlich ersatzlos.

Schritt 2: Sobald die Bälle auf die Behälter verteilt sind, wählen wir zufällig einen Ball aus jedem Behälter aus (dh wir ziehen $k$ Kugeln, eine aus jeder Tonne, nach dem Zufallsprinzip).

Nun stellt sich die Frage : Wie groß ist die Wahrscheinlichkeit, dass alle gezogenen Kugeln schwarz sind? Nennen wir dieses Ereignis $E$ .

Ich habe versucht, mich im Forum nach Vorschlägen umzusehen, aber ich habe diese Art von Frage nicht gefunden. Ich habe das gefunden: Eingeschränkte kombinatorische Frage: 2 Arten von Bällen, die in k Gruppen mit Grenzen unterteilt sind , was mir einige Hinweise gegeben hat, aber noch nicht das war, wonach ich suche.

Das ist mein Denken:

Ich habe alle möglichen Möglichkeiten zum Teilen der Kugeln wie folgt berechnet:
$(\binom{N}{N}) \cdot (\binom{N - N}{N}) \cdot (\binom{N - 2 N}{N}) \cdot \dots \cdot (\binom{N - (K - 1) N}{N}) = \frac{N!}{2 N!}$ ${N \choose n }\cdot {N-n \choose n} \cdot {N-2n \choose n}\cdot \ldots \cdot {N-(K-1)n \choose n} = \frac{N!}{2n!}$ Ich überspringe die Tonne $K$ denn meiner Meinung nach gibt es nur eine Möglichkeit zu setzen $n$ Bälle da - und das sind die $n$ verbleibende Bälle. Meine Sorge hier ist jedoch, dass die Variable $K$ wurde in dieser Gleichung gestrichen, und ich frage mich, ob das in Ordnung ist?
Nun kann Schritt 2 nur dann mit einer Wahrscheinlichkeit ungleich null eintreten, wenn zumindest $1$ schwarze Kugel ist in jedem Behälter. Die hypergeometrische Verteilung erlaubt mir, „die Wahrscheinlichkeit von zu formulieren $s$ Erfolge (d. h. zufällige Ziehungen, bei denen das gezogene Objekt ein bestimmtes Merkmal hat) in $m$ schöpft ersatzlos aus einer Population von Größe $M$ das enthält genau $S$ Objekte mit dieser Funktion, bei denen jede Ziehung entweder ein Erfolg oder ein Misserfolg ist". Also dachte ich, ich könnte dies in Schritt 1 verwenden, wenn ich Bälle zufällig Behältern zuweise. Der Erfolg würde darin bestehen, einen schwarzen Ball in einen Behälter zu legen. Also verwenden Die Notation für meine schwarzen und weißen Kugeln, eine solche Wahrscheinlichkeit ist definiert als
$P R (X = X) = \frac{(\binom{B}{X}) (\binom{N - X}{N - X})}{(\binom{N}{N})} .$ $Pr(X = x) = \frac{{B \choose x}{N - x \choose n -x}}{N \choose n}.$ Und ich dachte, dass dann eine Wahrscheinlichkeit, dass ein Behälter mindestens 1 schwarze Kugel enthält, als Summe ausgedrückt würde $P R (mindestens 1 schwarze Kugel in der Tonne) = \sum_{X = 1}^{N} \frac{(\binom{B}{X}) (\binom{N - X}{N - X})}{(\binom{N}{N})} .$ $Pr(\text{at least 1 black ball in the bin}) = \sum_{x=1}^{n} \frac{{B \choose x}{N - x \choose n -x}}{N \choose n}.$ Und da haben wir $K$ bin ich müsste es an die Macht nehmen $K$ . Die Wahrscheinlichkeit, dass jeder Behälter mindestens 1 schwarze Kugel enthält, wäre also: ${(\sum_{X = 1}^{N} \frac{(\binom{B}{X}) (\binom{N - X}{N - X})}{(\binom{N}{N})})}^{K}$ $\left(\sum_{x=1}^{n} \frac{{B \choose x}{N - x \choose n -x}}{N \choose n} \right)^K$

Und sobald die Aufteilung auf diese Weise erfolgt ist, bleibt nur noch die Wahrscheinlichkeit, dass ich aus jedem Behälter eine schwarze Kugel nehme, und diese weiß ich nicht zu definieren.

Insgesamt denke ich also, dass die Wahrscheinlichkeit des Ereignisses $E$ wäre definiert als:

P R [E] = \frac{Anzahl von Kombinationen, die ich alle Schwarzen unter der Bedingung auswähle, dass jeder Behälter mindestens 1 Schwarzes hat}{Anzahl aller möglichen Splits und Pfade, die ich auswählen kann}

$Pr[E] = \frac{\text{number of combinations that I pick all blacks under the condition that each bin has at least 1 black one}}{\text{number of all possible splits and paths I can pick}}$

Ich wäre sehr dankbar, wenn mir jemand ein bisschen helfen könnte, da ich das Gefühl habe, um die Lösung zu schwimmen, aber nicht dorthin komme. Ist meine allgemeine Überlegung richtig, übersehe ich etwas? Jede Hilfe willkommen! Vielen Dank im Voraus!

T_M

Ich habe noch keine Lösung, aber Ihr Ansatz sieht schwierig aus. Die Wahrscheinlichkeit, einen schwarzen Ball aus jedem Behälter zu nehmen, hängt von der genauen Aufteilung ab, die Sie haben, also können Sie nicht einfach die Wahrscheinlichkeit ausrechnen, dass Sie einen Split mit mindestens einem schwarzen Ball in jedem Behälter haben, und dann den nächsten Schritt berechnen separat.

T_M

Allerdings ist es einfach, die Anzahl der „gültigen“ Splits zu zählen, dh die mit mindestens einer schwarzen Kugel. Die Formel ist

(\binom{B - 1}{K - 1})

$\binom{B-1}{K-1}$ ; siehe hier: en.wikipedia.org/wiki/…

Antworten (1)

Kombinatorisches Problem: Schwarze und weiße Bälle werden in k Gruppen mit Grenzen aufgeteilt und als nächstes wird eine Folge von nur schwarzen Bällen ausgewählt.

Ich habe noch keine Lösung, aber Ihr Ansatz sieht schwierig aus. Die Wahrscheinlichkeit, einen schwarzen Ball aus jedem Behälter zu nehmen, hängt von der genauen Aufteilung ab, die Sie haben, also können Sie nicht einfach die Wahrscheinlichkeit ausrechnen, dass Sie einen Split mit mindestens einem schwarzen Ball in jedem Behälter haben, und dann den nächsten Schritt berechnen separat.
Allerdings ist es einfach, die Anzahl der „gültigen“ Splits zu zählen, dh die mit mindestens einer schwarzen Kugel. Die Formel ist $\binom{B-1}{K-1}$ ; siehe hier: en.wikipedia.org/wiki/…

T_M · Answer 1

Ich beginne mit dem Versuch, Ihren allgemeinen Ansatz ein wenig zu formalisieren und zu sehen, ob er irgendwohin führt ... Let $B_i$ bezeichnen die Anzahl der schwarzen Kugeln in der $i^{th}$ bin und betrachte Partitionen $\mathcal{P}$ des $N$ Bälle in die $K$ Behälter, jeweils gegeben durch $B_1 = b_1, \dots, B_K = b_k$ mit $b_i \geq 0$ Und $b_1 + \dots b_K = B$ . Nach dem Gesetz der totalen Wahrscheinlichkeit: Dann

\begin{array}{rcl} P (alle gepflückten Bälle sind schwarz) \\ = \sum_{\begin{matrix} B_{1} + \dots B_{K} = B \\ B_{ich} \geq 1 \forall ich \end{matrix}} P (alle gepflückten Bälle sind schwarz | B_{1} = B_{1}, \dots, B_{K} = B_{K}) \times P (B_{1} = B_{1}, \dots, B_{K} = B_{K}) \end{array}

$\begin{eqnarray} & \mathbb{P}\bigl(\text{all picked balls are black}\bigr) \\ & = \sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\mathbb{P}\bigl(\text{all picked balls are black}\ \big|\ B_1 = b_1,\dots,B_K = b_K\bigr) \times \mathbb{P}(B_1 = b_1,\dots,B_K = b_K) \end{eqnarray}$ Wie Sie darauf hingewiesen haben, enthalten wir in der Summe keine Partitionen mit

b_{i} = 0

$b_i = 0$ für einige

i

$i$ weil die Wahrscheinlichkeit, bei einer dieser Partitionen alles zurückzubekommen, automatisch null ist.

Beginnen Sie für den ersten Term mit der Beobachtung, dass

P (alle gepflückten Bälle sind schwarz | P) = P (⋂_{ich = 1}^{K} {schwarze Kugel wird ausgewählt {ich}^{T H} Behälter | P})) .

$\mathbb{P}\bigl(\text{all picked balls are black}\ \big|\ \mathcal{P}\bigr) = \mathbb{P}\bigl(\bigcap_{i=1}^K\{\text{black ball is picked from}\ i^{th}\ \text{bin}\ |\ \mathcal{P}\}\bigr)).$ Und diese Ereignisse auf der rechten Seite sind unabhängig, also

P (⋂_{ich = 1}^{K} {schwarze Kugel wird ausgewählt {ich}^{T H} Behälter | P})) = \prod_{ich = 1}^{K} \frac{B_{ich}}{N} .

$\mathbb{P}\bigl(\bigcap_{i=1}^K\{\text{black ball is picked from}\ i^{th}\ \text{bin}\ |\ \mathcal{P}\}\bigr)) = \prod_{i=1}^K \frac{b_i}{n}.$ Drei mögliche Interpretationen:

Wenn wir versuchen, auf Nummer sicher zu gehen und die Mülltonnen und die schwarzen Kugeln tatsächlich zu beschriften, landen wir beim Rechnen
$\begin{aligned} P (B_{1} = B_{1}, \dots, B_{K} = B_{k}) \\ = \frac{Anzahl der Möglichkeiten zum Platzieren von B unterschiedlichen Objekten in K Behältern mit B_{ich} Objekte in der {ich}^{T H} Behälter}{Anzahl der Möglichkeiten, B verschiedene Objekte in K Behältern zu platzieren} \\ = \frac{(\binom{B}{B_{1}, \dots, B_{K}})}{K^{B}} . \end{aligned}$ $\begin{align} &\mathbb{P}(B_1 = b_1,\dots,B_K = b_k) \\ & = \frac{\text{Number of ways of placing B distinct objects into K bins with}\ b_i\ \text{objects in the}\ i^{th}\ \text{bin}}{\text{Number of ways of placing B distinct objects into K bins}} \\ & = \frac{\binom{B}{b_1,\dots,b_K}}{K^B}. \end{align}$
Wenn wir Bins beschriften, aber keine Bälle, dann sind wir an Tupeln interessiert $(b_1,\dots,b_K)$ von nicht negativen ganzen Zahlen, die sich summieren $B$ In diesem Fall ist jede mögliche Partition nur 1 Multinomial von allen, zufällig ausgewählt (gleichmäßig, denke ich?), dh
$\begin{aligned} P (B_{1} = B_{1}, \dots, B_{K} = B_{k}) \\ = \frac{Anzahl von K Tupel genau der Form (B_{1}, \dots, B_{K})}{Anzahl von K Tupel von nicht negativen ganzen Zahlen, die summiert werden B} \\ = \frac{1}{(\binom{B + K - 1}{B})} = \frac{B! (K - 1)!}{(B + K - 1)!} . \end{aligned}$ $\begin{align} &\mathbb{P}(B_1 = b_1,\dots,B_K = b_k) \\ & = \frac{\text{Number of}\ K\ \text{tuples of exactly the form}\ (b_1,\dots,b_K)}{\text{Number of}\ K\ \text{tuples of non-negative integers that sum to}\ B} \\ & = \frac{1}{\binom{B+K-1}{B}} = \frac{B!(K-1)!}{(B+K-1)!}. \end{align}$
Wenn weder Bälle noch Tonnen beschriftet sind, dann kommt man in Partitionen von $B$ mit höchstens $K$ Teile. Keine guten Formeln, zu hart. Unter der Annahme, dass alles einheitlich gemacht wird, denke ich nicht, dass es darauf ankommt, was Sie tun. Wenn Sie die zweite der drei oben genannten Interpretationen verwenden, die natürlich erscheint, sehen Sie Folgendes:
$\begin{aligned} P (alle gepflückten Bälle sind schwarz) = \sum_{\begin{matrix} B_{1} + \dots B_{K} = B \\ B_{ich} \geq 1 \forall ich \end{matrix}} (\prod_{ich = 1}^{K} \frac{B_{ich}}{N}) \frac{B! (K - 1)!}{(B + K - 1)!} . \end{aligned}$ $\begin{align} & \mathbb{P}\bigl(\text{all picked balls are black}\bigr) = \sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\Bigl(\prod_{i=1}^K \frac{b_i}{n}\Bigr)\frac{B!(K-1)!}{(B+K-1)!}. \\ \end{align}$ Aber ich weiß nicht, was Sie mit diesem Ausdruck anfangen können.

Wenn Sie die erste Interpretation verwenden, erhalten Sie möglicherweise einen komplizierteren Ausdruck, aber er scheint am Ende summierbar zu sein; du hast:

\begin{aligned} P (alle gepflückten Bälle sind schwarz) & = \sum_{\begin{matrix} B_{1} + \dots B_{K} = B \\ B_{ich} \geq 1 \forall ich \end{matrix}} (\prod_{ich = 1}^{K} \frac{B_{ich}}{N}) \frac{(\binom{B}{B_{1}, \dots, B_{K}})}{K^{B}} \\ = \frac{1}{N^{K} K^{B}} \sum_{\begin{matrix} B_{1} + \dots B_{K} = B \\ B_{ich} \geq 1 \forall ich \end{matrix}} \frac{B!}{(B_{1} - 1)! \dots (B_{K} - 1)!} \\ = \frac{B!}{N^{K} K^{B} (B - K)!} \sum_{\begin{matrix} B_{1} + \dots B_{K} = B \\ B_{ich} \geq 1 \forall ich \end{matrix}} \frac{(B - K)!}{(B_{1} - 1)! \dots (B_{K} - 1)!} \\ = \frac{B!}{N^{K} K^{B} (B - K)!} \sum_{\begin{matrix} C_{1} + \dots C_{K} = B - K \\ C_{ich} \geq 0 \forall ich \end{matrix}} \frac{(B - K)!}{C_{1}! \dots C_{K}!} \\ = \frac{B!}{N^{K} K^{B} (B - K)!} K^{B - K} \\ = \frac{B!}{N^{K} K^{K} (B - K)!} . \end{aligned}

$\begin{align} \mathbb{P}\bigl(\text{all picked balls are black}\bigr) & = \sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\Bigl(\prod_{i=1}^K \frac{b_i}{n}\Bigr)\frac{\binom{B}{b_1,\dots,b_K}}{K^B} \\ &= \frac{1}{n^KK^B}\sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\frac{B!}{(b_1-1)! \dots (b_K-1)!} \\ &= \frac{B!}{n^KK^B(B-K)!}\sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\frac{(B-K)!}{(b_1-1)! \dots (b_K-1)!} \\ &= \frac{B!}{n^KK^B(B-K)!}\sum_{\substack{c_1 + \dots c_K = B-K \\ c_i \geq 0\ \forall i}}\frac{(B-K)!}{c_1! \dots c_K!} \\ &= \frac{B!}{n^KK^B(B-K)!}K^{B-K} \\ &= \frac{B!}{n^KK^K(B-K)!}. \end{align}$ Mit

B = W = K = 2

$B = W = K = 2$ (in welchem Fall

n = 2

$n = 2$ ), ergibt diese Formel:

\frac{2!}{2^{2} 2^{2} 0!} = \frac{2}{16} = \frac{1}{8},

$\frac{2!}{2^22^2 0!} = \frac{2}{16} = \frac{1}{8},$ was ich auch versucht habe in den Kommentaren zu erklären. OK, es sieht also so aus, als würde dies eine Art Formel hervorbringen.

Für $B=W=K=2$ dieser letzte Ausdruck ist $\frac13$ ; wenn ich das problem richtig verstanden habe, macht es eine eigentliche aufzählung der möglichkeiten $\frac23$ . Ich bin aber nicht auf die Herleitung gegangen.
Es gibt einige Unklarheiten in der Frage, was "zufällig" geteilt wird $N$ Kugeln hinein $K$ bins bedeutet, aber jetzt, wo ich darüber nachdenke, würde ich das normalerweise so verstehen, dass die Bins beschriftet sind, also wären die möglichen Partitionen BB|WW, BW|BW, WW|BB. Die Partition BW|BW tritt mit Wahrscheinlichkeit 1/2 auf, die anderen jeweils mit Wahrscheinlichkeit 1/4. Um am Ende ganz schwarz zu werden, braucht man BW|BW. Dann müssen Sie auch die schwarze Kugel aus Behälter 1 mit Wahrscheinlichkeit 1/2 und die schwarze Kugel aus Behälter 2 mit Wahrscheinlichkeit 1/2 ziehen . Du bekommst also 1/8!?
Ich dachte, meine Zählung für die Anzahl der Partitionen würde BB|WW und WW|BB als gleich zählen ( $2 = 2 + 0$ ) und dann sagen, dass es mit der gleichen Wahrscheinlichkeit auftritt wie BW|BW (2 = 1 + 1). Sie würden also dieselbe Antwort erhalten, aber anscheinend fehlt mir etwas anderes
@T_M Vielen Dank für deine Hilfe! In der Tat ist Ihr Ansatz so einfach - ich habe einige Zeit darüber nachgedacht, und es macht absolut Sinn! Ich hatte nur Schwierigkeiten zu verstehen, wie Sie gekommen sind $K^{B-K}$ von der letzten Summe, aber ich nehme an, es gibt eine nette Formel, die dabei hilft! Ich habe auch einen kleinen Python-Simulator geschrieben, um die durchschnittliche Wahrscheinlichkeit zu schätzen, und er liefert praktisch die gleichen Ergebnisse wie die Berechnung der Wahrscheinlichkeit direkt aus Ihrer Formel. Nochmals vielen Dank!

Kombinatorisches Problem: Schwarze und weiße Bälle werden in k Gruppen mit Grenzen aufgeteilt und als nächstes wird eine Folge von nur schwarzen Bällen ausgewählt.

SugerBoy

T_M

T_M

Antworten (1)

T_M

Brian M. Scott

T_M

T_M

SugerBoy

Wahrscheinlichkeit, dass zwei bestimmte Elemente in einer zufälligen Partition mit festen Größen gruppiert sind

Binomialkoeffizientenpfade?

Eine Frage zu einem Sonderfall des Inklusions-Exklusions-Prinzips

Wahrscheinlichkeit, dass 5 Karten aus dem gemischten Deck gezogen werden

Kombinatorischer (und algebraischer Beweis) einer Identität mit Lah-Zahlen

Berechnung der Mindestpunktzahl, um als Team in einer Sportliga zu bestehen

Zählen der Wege auf dem Gitter, wenn man sich von (x,y)(x,y)(x,y) nach (x+a,x+b)(x+a,x+b)(x+a, x) bewegen kann +b) für beliebige x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0.

Anzahl von 5-Buchstaben-Wörtern mit mindestens einem Doppelbuchstaben

Die Wahrscheinlichkeit, beim Fünf-Karten-Poker ein Full House zu bekommen, wenn Karten in Suite fehlen

Beweisen Sie eine kombinatorische Identität, die das Summieren von Produkten von Binomialkoeffizienten beinhaltet