3
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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}. $$

$\endgroup$
  • 1
    $\begingroup$ Thanks, but doesn't that assume that each distribution of the balls is equally likely? But it's much more likely to have approximately the same number of black balls in each bin, rather than (e.g.) all balls in the first bin. Or am I missing something? $\endgroup$ – Lorenz Dec 7 '16 at 16:15
  • $\begingroup$ Oh I see. Yes, I think my answer is wrong assuming each ball is assigned to a uniform random bin. $\endgroup$ – TorsionSquid Dec 7 '16 at 17:33
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! Denominator should be $k^n$, that's clear. But I'm unsure about the numerator. The number of red balls in each bin follows a binomial distribution (B(n, k/n)). I'm not sure what you mean by "choose that partition from n/2 balls"? $\endgroup$ – Lorenz Dec 8 '16 at 13:26
  • $\begingroup$ Yes. Agree to denominator. $\endgroup$ – aman_cc Dec 8 '16 at 13:31
  • $\begingroup$ Sorry I pressed enter to fast, I guess. $\endgroup$ – aman_cc Dec 8 '16 at 13:32
  • $\begingroup$ numerator - Assuming you have 5 different balls and 3 different bins. A possible partition is (2,1,2) Ways to choose the partition among 5 different balls is 5C2*3C1*2c2 For e.g. there is only 1 way to choose partition (0,0,5) (Hence I say this way they are equally likely) If I sum above acorss all possible paritions - I get 3^5 $\endgroup$ – aman_cc Dec 8 '16 at 13:37
  • 1
    $\begingroup$ Yes, assuming two buckets for simplicity the probability of configuration (x, n-x) is $\binom{n}{x}\cdot(\frac{1}{2})^n$ $\endgroup$ – Lorenz Dec 8 '16 at 13:40
0
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.