1
$\begingroup$

We have $1000$ balls, $750$ red and $250$ blue. We distribute them uniformly at random into $10$ bins. What is the probability none of these bins is at least $1/3$ blue?

More generally I'd like to consider the case where you have $n$ balls and $k$ bins, such that $3/4$ of the balls are red and $1/4$th are blue. What is the probability no bin has $1/3$ blue?

Approximations are also desirable, mostly ones that give a probability strictly bounded below the true probability.

$\endgroup$
  • $\begingroup$ You should be clear about 33% blue vs. 1/3 blue. But ... assuming the latter, place 67 red balls in each of the 10 bins, then place 33 of what's left (250 blue, 80 red) in each bin however you like. $\endgroup$ – John Jun 7 '18 at 19:36
  • $\begingroup$ @John I've edited the title. However, there are solutions where some bins have less than 67 red balls in them (for example a bin with 1 red and 0 blue balls in it), so I don't understand the rest of your comment. $\endgroup$ – mich Jun 7 '18 at 19:40
  • $\begingroup$ You said "we distribute them uniformly at random into 10 bins." To me that means 100 balls per bin. Did you mean differently? $\endgroup$ – John Jun 7 '18 at 21:17
  • $\begingroup$ @John It means for each ball, you choose uniformly at random a bin out of the 10. $\endgroup$ – mich Jun 8 '18 at 6:34
  • 1
    $\begingroup$ This looks quite difficult, I doubt that there is a closed form solution. Are you interested in approximation for large $n,k$? $\endgroup$ – leonbloy Jun 11 '18 at 22:49
1
$\begingroup$

This looks quite difficult, I doubt that there is a closed form solution.

For the case of large $n$ balls ($ \alpha n$ red, $(1-\alpha)n$ blue), and $k$ bins, here's a simple asympotic, for large $n,k$, and $t=n/k$ approx. constant.

The amount of red balls in each bin can be approximated by $k$ iid Poisson variables $X_i$ with mean $\lambda_x= \alpha n/k=\alpha t$.

Same for blue balls, $Y_i$ with mean $\lambda_y= (1-\alpha) t$ (also $X_i, Y_j$ are independent).

We are interested in the event $E = \cap_i E_i=\cap_i [X_i > b Y_i]. $ Then:

$$P(E_i)=\sum_{x=0}^{\infty} \sum_{y=0}^{\lceil x/b \rceil-1} e^{-\alpha t} \frac{(\alpha t)^x}{x!} e^{-(1-\alpha) t} \frac{((1-\alpha) t)^y}{y!} $$

and $$P(E)= \left(e^{-t}\sum_{x=0}^{\infty}\sum_{y=0}^{\lceil x/b \rceil-1} \frac{(\alpha t)^x}{x!} \frac{((1-\alpha) t)^y}{y!}\right)^k$$

This is not very nice, and I'm afraid it's not even easy to approximate (even for $b=1$, see here). But, at least, the term inside the parenthesis only depends on $\alpha, \beta, t$. In our case, of course, $\alpha=\frac34$ and $b=2$.

$\endgroup$
  • $\begingroup$ Can you relate your approximation to the true probability? (Is it smaller, greater?) $\endgroup$ – mich Jun 12 '18 at 21:07
  • $\begingroup$ This approximation method is called Poissonization. I think that it should be doable to prove that the above $P(E)$ tends to the true probability as $k\to \infty$, but I'm not sure if it's possible to give bounds. $\endgroup$ – leonbloy Jun 13 '18 at 0:52
  • $\begingroup$ I see. Thank you. I would be more interested in an approximation that is strictly below the true value, or some error bounds. $\endgroup$ – mich Jun 14 '18 at 10:01
0
$\begingroup$

Let's distribute the 250 blue balls randomly in the 10 bins. So we will choose 1 to 10 bins out of the 10 bins and distribute the blue balls to them randomly, so that each set contains at least one ball, which is $$\sum_{i=1}^{10} {{10}\choose{i}}\cdot{{250 - 1}\choose{i-1}}$$ if the (250 - 1) term seems odd to you, check the stars and bars method.

So now for 500 out of the 750 red balls we know exactly where they should go (namely for each blue ball we have to assign two red balls in order to keep on the one third condition.

we still have 250 red balls we can distribute randomly, so it's again $$\sum_{i=1}^{10} {{10}\choose{i}}\cdot{{250 - 1}\choose{i-1}}$$ for the 250 rest red balls. Hence the total answer should be: $$\left( \sum_{i=1}^{10} {{10}\choose{i}}\cdot{{250 - 1}\choose{i-1}} \right)^2$$

Edit Instead of this sum you can use the Formula: $${250 + 10 - 1}\choose{10 - 1}$$ for which there are many explanations, one of them is, the problem is equivalent of having 250 + 10 balls distributing them to 10 slots but every slot must have a ball at least. Another explanation is found in the second theorem of stars and bars. The total answer in this case will be: $$\left({250 + 10 - 1}\choose{10 - 1}\right)^2$$

$\endgroup$
  • $\begingroup$ I don't think this is right. The first count (if we consider balls and bins are distinguishable) should simply be $10^250$. And the strategy countings for the red balls looks wrong, because you are imposing that the "first" 400 red balls are those which verify the condition. $\endgroup$ – leonbloy Jun 11 '18 at 22:32
  • $\begingroup$ sorry can you explain where the $10^250$ comes from? the second part should be okay since the balls are identical and there is no "first 500 balls". However, I think I could have used a simpler way to choose the random distribution namely the ${n+k-1}\choose{k}$ but I wasn't sure of it that's why I used the sum $\endgroup$ – narek Bojikian Jun 11 '18 at 22:37
  • $\begingroup$ Sorry, I meant $10^{250}$. That the second part should wrong can be seen by considering the simpler problem: how many ways are of putting $n$ balls in $k$ bins, such that each bin is not-empty? By your reasoning, you could say "we know where the first $k$ balls should go, one in each bin; now, let's count the combinations for the rest of the balls...". This is wrong. $\endgroup$ – leonbloy Jun 11 '18 at 23:13
  • $\begingroup$ yes my claim says that and I don't think it's wrong since if bins can't be empty we have ${n-1}\choose{k}$ ways and if we considered putting a ball in every set at first we will have n-k balls left distributing them with empty sets is ${n-k+ k - 1\choose{k}}$ = ${n-1}\choose{k}$ $\endgroup$ – narek Bojikian Jun 11 '18 at 23:33

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.