I'd appreciate some help on the below problem.
Let's say you have $d$ each of $n$ colors of otherwise identical balls, and $m$ buckets. You cannot put more than one ball of the same color in any single bucket. All of the balls are distributed randomly and $\frac{1}{2}n<m<n$.
What's the probability that some set of $k$ colors are contained wholly in fewer than $k/2$ buckets, for any $k\in\mathbb{Z}^{+}$?
A nontrivial upper bound would be acceptable.
Thank you!
Edit: Just to clarify, $k$ isn't fixed. I'm asking about the probability that there is a $k$ such that the above condition is satisfied.
To begin, let’s calculate the probability for a fixed $k$.
Since we have $k$ colors, we know we have our $k*d$ balls in (at most) $k/2$ bins. Let’s fix the $k$ colors and $k/2$ bins we’re considering, and handle combinations later.
For each color, the probability that all $d$ balls are in these fixed $k/2$ bins is
$$\frac{k/2}{m}*\frac{k/2-1}{m-1} * \dots * \frac{k/2-d+1}{m-d+1} $$ $$=\frac{(k/2)!/(k/2-d)!}{m!/(m-d)!}$$
Which we know since the $i$th ball to be placed has $m-(i-1)$ bins that it can be placed in total, and $(k/2)-(i-1)$ of those are in our set of $k/2$ and don’t already have a ball.
Since there are $k$ colors, and they’re independent, the probability that all colors are like this is simply
$$P(\text{fixed k colors in fixed k/2 bins}) = (\frac{(k/2)!/(k/2-d)!}{m!/(m-d)!})^k$$
Now, since we can have this happen for any $k$ colors (out of $n$ many) and any $k-2$ bins (out of $m$ many), we simply multiply by the number of combinations to get:
$$P(\text{any k colors in any k/2 bins}) = \binom{n}{k} * \binom{m}{k/2} * (\frac{(k/2)!/(k/2-d)!}{m!/(m-d)!})^k$$
Now, if this probability was independent for each unique $k$, we could sum these probabilities to get the probability that this is true for any $k$. However, I’m not convinced they are independent, and don’t know how to prove they are even if I did, so instead we can just take the sum of the possibilities as an upper bound:
$$P(\text{any such } k) \leq $$ $$\sum_{k=2d}^{n} \binom{n}{k} * \binom{m}{k/2} * (\frac{(k/2)!/(k/2-d)!}{m!/(m-d)!})^k$$
Also, I will note that this doesn’t handle rounding issues related to $k$ being odd, nor the strict inequality, as I thought it would over-clutter the equations. You can throw a floor function around $k/2$ for odd $k$ and a $k/2-1$ for even k if that distinction is important.
This is my first time posting, so apologies for any formatting errors or general mistakes!