I have the following combinatorial problem: Let's assume we have $N$ balls: $W$ white, and $B$ black balls ($N = B + W$).
Step 1: The first thing we do is to randomly divide these $N$ balls into $K$ bins, each bin having $n = \frac{N}{K}$ balls. Dividing the balls into the bins is of course done without replacement.
Step2: Now, once the balls are divided among the bins, we select randomly one ball from each bin (i.e., we draw $k$ balls, one from each bin, at random).
Now, the question is – what is the probability that all picked balls are black? Let's call this event $E$.
I tried to look around the forum for some suggestions, but I didn't find this type of question. I found that one: Constrained combinatorial question: 2 types of balls divided into k groups with limits, which gave me some hints but wasn't yet what I am looking for.
This is my thinking:
-
I computed all possible ways to split the balls as:
$${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!}$$
I skip bin $K$ since in my opinion there is only one way to put $n$ balls there – and these are the $n$ remaining balls. However, my concern here is that the variable $K$ got canceled in this equation, and I wonder whether that's ok? -
Now, Step 2 can happen with a non-zero probability only if at least $1$ black ball is in each bin. The hypergeometric distribution allows me to "formulate the probability of $s$ successes (i.e., random draws, for which the object drawn has a specified feature) in $m$ draws, without replacement, from a population of size $M$ that contains exactly $S$ objects with that feature, where each draw is either a success or a failure". So I thought I can use this in Step 1 when I am randomly assigning balls to bins. The success would be putting to a bin a black ball. So using the notation for my black and white balls, such probability is defined as
$$Pr(X = x) = \frac{{B \choose x}{N – x \choose n -x}}{N \choose n}.$$ And I thought that then a probability that a bin contains at least 1 black ball would be expressed as the sum
$$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}.$$
And since we have $K$ bins I would have to take it to the power of $K$. So the probability that each bin contains at least 1 black ball would be:
$$ \left(\sum_{x=1}^{n} \frac{{B \choose x}{N – x \choose n -x}}{N \choose n} \right)^K$$
And once the split is done in such a way, the only thing left is – the probability that I will pick a black ball from each bin and this one I don't know how to define.
So overall, my thinking is that the probability of event $E$ would be defined as:
$$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}}$$
I would be very grateful if someone can help me a bit since I feel like I'm swimming around the solution but can't get there. Is my general consideration correct, am I'm missing something? Any help welcome!
Many thanks in advance!
Best Answer
I'll start by trying to formalise a bit your general approach and see if it goes anywhere... Let $B_i$ denote the number of black balls in the $i^{th}$ bin and consider partitions $\mathcal{P}$ of the $N$ balls into the $K$ bins, each one given by $B_1 = b_1, \dots, B_K = b_k$ with $b_i \geq 0$ and $b_1 + \dots b_K = B$. By the law of total probability: Then \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} As you pointed out, we don't include in the sum any partitions with $b_i = 0$ for some $i$ because the probability of getting all back given one of those partitions is automatically zero.
For the first term, start with the observation that $$ \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)). $$ And these events on the right-hand side are independent, so $$ \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}. $$ Three possible interpretations:
If we try to play it safe and actually label the bins and the black balls, we end up computing \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}
If we label bins but not balls then we are interested in tuples $(b_1,\dots,b_K)$ of non-negative integers that sum to $B$ in which case each possible partition is just 1 multinomial out of all of them, picked (uniformly I guess?) at random, i.e. \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}
If neither balls nor bins are labelled then you get into partitions of $B$ with at most $K$ parts. No good formulae, too hard. Assuming everything is done uniformly I don't think it matters which you do. Using the second of the above three interpretations, which seems natural, you are looking at: \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} But I don't know what you can do with this expression.
Using the first interpretation, you get a more complicated expression potentially but it seems to be summable in the end; you have:
\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} With $B = W = K = 2$ (in which case $n = 2$), this formula gives: $$ \frac{2!}{2^22^2 0!} = \frac{2}{16} = \frac{1}{8}, $$ which is what I also tried to explain in the comments. OK so it looks like this does product some kind of formula.