# Balls and Bins with colored balls

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.

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