There are 2N white balls and N red balls (all balls are same except for the color), to put into K different boxes, such that every box contains 3N/k balls. We say event A happens, if any box has more than one half red balls.

  1. Mix 2N white balls and N red balls uniformly then put them into K boxes randomly;
  2. First, Put some red balls to K boxes equally, then mix 2N white balls and the rest red balls uniformly and lastly put them into K boxes randomly;

Q: which case has a higher probability of A?

Actually, we regard A as some "bad" case. Intuitively, the latter is more "uniform" so with less chance to have a "overflowd" box. I was trying to prove it formally. Here are my thinkings:

Using hypergeometry distribution, we write down the probability of negative A, so my target is to prove (Here mk is the red balls that put into boxes at very beginning in case 2, for convenience, I assume it is m times of k)

\begin{equation} \frac{\sum\limits_{\substack{s_1+...+s_k \leq N \\ 0 \le s_i \le M/2}}{\prod_{i=1}^k{C_M^{s_i}}}}{C_{3N}^N} \leq \frac{\sum\limits_{\substack{s_1+...+s_k \leq N-mk \\ 0 \le s_i \le M/2-k}}{\prod_{i=1}^k{C_{M-m}^{s_i}}}}{C_{3N-mk}^{N-mk}} \end{equation}

I've tried several scale-down tricks, but none of the methods I know work.

Can anybody give me some idea? I feel this is a typical question, related materials is also a big help!

  • $\begingroup$ You might get more positive response(s) if you show your attempts to figure this out with combinatorics logic. $\endgroup$ – poetasis Jan 5 at 12:24
  • $\begingroup$ by combinatorics logic, you mean I should write down some formula? $\endgroup$ – chuangmingjj Jan 5 at 13:26
  • $\begingroup$ I don't know if you need permutations, combinations, inclusion/exclusion but showing what you have tried always gets better responses. Even the right side of this screen shows related questions that may or may not provide insight into your problem. Good luck. $\endgroup$ – poetasis Jan 5 at 16:11

Some thoughts too long for a comment. Let us consider the case where $N$ is quite large so the correlation between boxes becomes small. In case 1 the distribution of red and white balls in a box is Poisson. We can take case 2 to the extreme, distribute all the red balls evenly, and have exactly $\frac NK$ red balls in each box. We can then sum over the Poisson distribution and find the chance that a particular bin causes event A. If $\frac NK=1$ the chance one bin causes event A is about $0.183$ in case 1 and $0.135$ in case 2. If $\frac NK=10$ the chances are $0.0258$ in case 1 and $0.0050$ in case 2. I suspect this is general-increasing the variability is good for the chance of unlikely things happening and distributing the red balls randomly increases the variability. Clearly this is not a proof, but it suggests the result.

  • $\begingroup$ thanks for your thoughts! I have two questions. 1. Why it's Possion and what's the $\lambda$ in Possion? As far as I know, binomial distribution is approximated by Possion if n is large, p is small, but $\lambda=np$ is a constant. Here, my p is 1/3, that's not small. 2. How to get 0.183? Would you mind explaining a bit more $\endgroup$ – chuangmingjj Jan 10 at 2:53
  • $\begingroup$ It is Poisson if N is large because each ball has $1/N$ chance of falling in each bin. For the red balls $\lambda=\frac NK$ while for the white balls it is twice that $\endgroup$ – Ross Millikan Jan 10 at 3:28
  • $\begingroup$ I got $0.183$ in the pedestrian way. It is the chance (using Poisson) that there is one red and no whites plus the chance there is two reds and zero or one white plus... $\endgroup$ – Ross Millikan Jan 10 at 6:06

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.