0
$\begingroup$

Assume I have a total of $N$ balls with $k$ red and $N-k$ blue ones. Further, assume I have $M$ bins. Now I randomly throw each ball into one of the bins (without seeing the color of the ball). What is the probability of having at least one bin that has one (or more) red, but not a single blue ball in it. I don't need the exact probability, an upper bound would be ok.

Add-on: Would the probability of this event decrease if I change the throwing strategy? For example, I could maybe use the power of choice, where I pick 2 bins and put the ball in the emptier one.

$\endgroup$
0
$\begingroup$

Deviating from the notation in the OP, let's say we have M bins, B blue balls, and R red balls. We want to know the probability that at least one bin contains at least one red ball and no blue balls. We will solve the problem through two applications of the Principle of Inclusion and Exclusion, abbreviated PIE. (I have not attempted to solve the add-on problem.)

First we solve the following problem: Given $k$ with $1 \le k \le M$, what is the probability that bins $1, 2, 3, \dots ,k$ all contain at least one red ball? To apply PIE, let's say an arrangement of the red balls in the bins has "Property $i$" if bin $i$ has no red ball. We want to know the probability that an arrangement has none of the properties, i.e., bins $1$ through $k$ all have at least one red ball. Let $S_j$ be the total of the probabilities of the arrangements that have $j$ of the properties. Then $$\begin{align} S_1 &= \binom{k}{1} (1-1/M)^R \\ S_2 &= \binom{k}{2} (1-2/M)^R \\ S_3 &= \binom{k}{3} (1-3/M)^R \\ &\dots \\ S_k &= \binom{k}{k} (1-k/M)^R \end{align}$$ By PIE, the probability that all the bins $1$ through $k$ contain at least one red ball is $$p(k) = 1 - S_1 + S_2 - S_3 + \dots +(-1)^k S_k$$ It should be clear that the same probability applies to any set of $k$ bins, not necessarily $1$ through $k$.

Now we can tackle the original problem: What is the probability that at least one bin has one or more red balls and no blue ball? Once again, we apply PIE, but this time we define "Property $i$" as meaning that bin $i$ has at least one red ball and no blue ball. Let $T_j$ be the total of the probabilities of the arrangements that have $j$ of the properties. Then $$\begin{align} T_1 &= \binom{M}{1} \;p(1)\; (1-1/M)^B \\ T_2 &= \binom{M}{2} \;p(2)\; (1-2/M)^B \\ T_3 &= \binom{M}{3} \;p(3)\; (1-3/M)^B \\ &\dots \\ T_M &= 0 \end{align}$$ where $p(k)$ is as defined above. Then by PIE, the probability that at least one bin has one of the properties, i.e. at least one bin has one or more red balls and no blue ball, is

$$T_1 - T_2 + T_3 - \dots + (-1)^{M+1} T_M$$

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