Probability in ball coloring

Question

You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ball can be given a color $i$ with probability $\frac{1}{n^2}$ (uniform probability of assignment of colors). You pick $n^{b}$ balls without replacement. What is the probability that atleast $n^{a}$ balls are of the same color with $0 < a < b \leq 2$? Floor any real numbers to get integers - in any case - I am looking for asymptotic bounds.

Answer 1

Presumably you are drawing with replacement. We assume you want exactly $n^a$ that match, with the rest non-matching. If you just want at least $n^a$, you have to sum over $n^a$ up to $n^b$. If $2n^a \gt n^b$ it is easier, as you can't get two sets of the same color. There are $(n^2)^{(n^b)}$ ordered draws. To get $n^a$ that match, you can choose the positions of the matching ones in ${n^b \choose n^a}$ ways, the color in $n^2$ ways, and the remaining colors in $(n^2-1)^{(n^b-n^a)}$ ways. So we have a probability of $$\frac {{n^b \choose n^a}n^2(n^2-1)^{(n^b-n^a)}}{(n^2)^{(n^b)}}$$ This will overcount if $2n^a \le n^b$ because times you get two groups of $n^a$ are counted twice and so on. There is no magic in making everything powers of $n$-you could as easily use $a,b,n$ for the numbers. It should be clear how to modify the expression to do that.

Answer 2

Note that you don't have to account for initially choosing the $n^b$ balls out of $n^2$. In particular, we could start with just $n^b$ balls and ask what is the probability that at least $n^a$ have the same color. Let $X$ denote the number of sets of $n^a$ balls of the same color, so we wish to bound the probability that $X$ is at least 1. So \begin{align*} P(X \geq 1) \leq E[X] &= \sum_{A : |A|=n^a} P(\text{the balls of }A\text{ are mono colored}) \end{align*} For any specific such set of balls $A$, note that this probability is exactly $$\left( \frac{1}{n^2} \right)^{|A|-1},$$ since the first ball can be any color, but each of the following balls of $A$ must be the same as the first one.

Hence \begin{align*} P(X \geq 1) &\leq {n^b \choose n^a} \left( \frac{1}{n^2} \right)^{n^a-1} \leq \left( \frac{e n^b}{n^a} \right)^{n^a} \left( \frac{1}{n^2} \right)^{n^a-1} \\& \leq n^2 \left( \frac{e n^b}{n^a n^2} \right)^{n^a}=\exp \left( -n^a(2-b+a)\ln n+o(n^a \ln n)\right). \end{align*}