1
$\begingroup$

Say we throw $b$ blue balls and $r$ red balls uniformly into $n$ boxes. The probability that no box contains a red as well as a blue ball is then, by the inclusion exclusion principle:

$$p = \sum_{k,\ m} \binom{n}{k} \binom{n-k}{m} (-1)^{n-m-k} \left(\frac{m}{n}\right)^r \left(\frac{k}{n}\right)^b$$

I'm interested in upper bounding $p$. If we assume the red balls are thrown first, and without replacement, we can lower bound it as

$$\left(1-\frac{r}{n}\right)^b$$

Or 1 if both $r$ and $b$ are as big as $n$. Note $e^{-rb/n}$ is another good approximation, though neither a lower nor an upper bound.

Can you see any way to get a simple upper bound? I've tried to look into asymptotic expansions, but I don't see how I can be done.

$\endgroup$
1
$\begingroup$

Not what you are looking after, but a simple asymtoptic result would be: assume the number of blue (red) balls in each box are iid Poisson with $\lambda_B = b/n$ ($\lambda_R=r/n$), hence the probability that no box has red and blue balls would be

$$P \approx \left(1-(1-e^{-\lambda_B})(1-e^{-\lambda_R}) \right)^n=\left(e^{-b/n} + e^{-r/n} - e^{-(r+b)/n} \right)^n \tag{1}$$

I would bet that this is only useful for $n$ much bigger than $r,b$, and that it overestimates $P$, but it does not seem easy to prove that it's an upper bound.

Another approximation: the expected number of boxes with red balls is $E_r=n \left(1-(1-1/n)^r\right)$. Equating this (expected) number with the actual number, we get

$$P \approx \frac{(n-E_r)!(n-E_b)!}{n! \, (n-E_r-E_b)!} \tag{2}$$

A few results (ps comes from simulation, pa1 and pa2 are the above approximations)

  n  b    r   ps     pa1     pa2
1000 30  10  0.741  0.745  0.736
 500 30  30  0.165  0.183  0.168  
 500 80   8  0.278  0.309  0.275 
 500 20   6  0.786  0.791  0.782
  10  5   3  0.215  0.341  0.167
$\endgroup$
  • $\begingroup$ I suppose in the first case we don't really need to assume poisson. The main assumption is that the boxes are independent. If we use this assumption with the uniform distribution we get $((1-1/n)^r+(1-1/n)^b-(1-1/n)^{r+b})^n$. I'm sure there must be a good argument for why that's an upper bound. Just can't think of it right now. $\endgroup$ – Thomas Ahle Feb 24 '15 at 18:08
  • $\begingroup$ Something about, that in the dependent case, once you have a separated box, it increases the chance that a later box is mixed. $\endgroup$ – Thomas Ahle Feb 24 '15 at 18:14
0
$\begingroup$

In case anyone is interested, this chart plots the seperation probability for $n\in[1,20]$, $r=2,b=3$. The dots are the correct value, the green line is $e^{-rb/n}$, the orange line is the lower bound from my original post, and the blue line is the upper bound from my comment to leonbloy.

Diagram

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