# Probability in ball coloring

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.

• could you elaborate? – Turbo Jul 29 '13 at 17:34
• Are $a$, $b$, and $n$ exponents? Are we to assume that $a$ and $b$ are either $0$,$1$, or $2$, or can they be arbitrary real numbers? – Omnomnomnom Jul 29 '13 at 18:32
• What do you mean? All $a,b,n$ are variables. If it helps analysis, you could substitute constants. – Turbo Jul 29 '13 at 18:35
• Is $a=1.5$ allowed? – Tomas Jul 29 '13 at 20:23

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.
• Then you have to specify the distribution. If the colors are randomly picked, you will have a Poisson distribution with mean $1$. About $\frac 1e$ of the colors will be absent, about $\frac 1e$ will have only one marble, others will have a few more. The chance of getting any reasonable number of matches is still very small. – Ross Millikan Jul 30 '13 at 13:24
• I had some exponents backwards, now fixed. The top exponent in the denominator is $b$, not $a$ (and not $2$). Basically, you have so many colors (assuming $n$ isn't too small) that you can't get very many matches. – Ross Millikan Jul 30 '13 at 14:26
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.