Balls in bins: probability of equal number of red and black balls in every bin

Question

Given $n$ balls, half of which are red and half are black (assume $n$ is even), and $k$ bins. What is the probability that for each bin, there is an equal number of red and black balls in it?

I've tried solving this by taking the number of possible pairs times the number of ways to distribute these pairs, but that doesn't look right—if more than one pair ends up in a bin, I don't care which way those balls were paired up. Nor did I get anywhere by distributing the black balls ($\binom{k+n/2-1}{n/2}$ ways), since I couldn't figure out how many ways there are to distribute the red balls so that each bin has an equal number of red and black balls.

So what would be the right way of going about this?

Thanks!

Answer 1

With help from @aman_cc, I think I figured it out. I'll start with two buckets and then generalise from 2 to k. Sum over the number of red balls in the left bucket, $l$. For simplicity define $m=n/2$ to be the number of balls of either colour. Then the right bucket must contain $m - l$ red balls. There are $\binom{m}{l}$ ways to put $l$ red balls in the left bucket. The same needs to happen for the black balls (→ square it). There are $2^m$ ways of putting $m$ balls into two bins. Thus, for the probability $X_{2,m}$ of having an equal number of black and red balls in both bins, we obtain

$$X_{2,m}=\sum_{l=0}^{m}{\left(\binom{m}{l}2^{-m}\right)^2} = 4^{-m}\sum_{l=0}^{m}{\binom{m}{l}^2}=4^{-m}\binom{2m}{m} \leq 4^{-m}\cdot\frac{4^{m}}{\sqrt{3m+1}} < \frac{1}{\sqrt{2m}} \ .$$

We can see that the probability of this happening decreases as we add more balls (at least for two buckets), as we would expect intuitively. To prepare for the generalisation, the number of configurations with matching numbers of red and black balls in each bucket is $X_{2,m}$ without the $4^{-m}$ factor. Call this $C_{2,m} = \binom{2m}{m}$.

Then we have $$C_{k,m} = \sum_{l=0}^{k}{\binom{m}{l}^2 C_{k-1,\,m-l}}$$ (Note that $l_k$ will always be 0 as the last bucket is fully determined, I could have ended it at $l_{k-1}$ but it looks cleaner this way). Then $X_{k,m} = C_{k,m} k^{-2m}$ is the probability we are looking for. Or rather, put in terms of $n$:

$$X_{k,n} = C_{k,\frac{n}{2}}\cdot k^{-n}$$

Thanks to @aman_cc for the help!

Answer 2

Assuming balls of the same color are identical, the number of ways we can distribute them such that each bin is chromatically balanced is $$ \binom{k+n/2-1}{n/2}. $$ (Once you pick a distribution of the black balls, the distribution of the red ones is determined.)

The total number of distributions of the $n/2+n/2$ balls is $$ \binom{k+n/2-1}{n/2}^2. $$ (Pick a distribution of black balls and a distribution of red balls.)

So the answer is $$ \binom{k+n/2-1}{n/2}^{-1}. $$

Answer 3

Hint: 1. You need to compute probability. Hence assume the n balls are all different. (This is important else you will not get equally likely cases - for e.g. a distribution where all balls go in one box is quite less likely) 2. Denominator should be easy with above. 3. For numerator distribute only red balls. (in terms of numbers of balls in each urn). Black will follow the same. Now all you do is choose that partition from n/2 balls (for each color) Hope that helps. (Try small values of n and k - it will help I guess)

TorsionSquid ans above misses on pt#1 I wrote.

I would let you give a shot at it before I post a detailed ans.

I worked on a similar problem on this forum. There's $M_i$ balls of color $i=1,..,N$. $n$ balls are drawn without replacement. Find: probability that each of the colors is represented Have a look. It will help me check my work too. Thanks