Combinatorial problem: black and white balls divided into k groups with limits, and next picking a sequence of only black balls.

Question

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!

Answer 1

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.