# How many boxes so that there is $k$ of same of color from $n$ different colors?

Say you have $m$ boxes each of which is colored with one of $n$ colors. What should $m$ be so that the probability that there is atleast $k$ boxes with one same color is strictly greater than $\frac{1}{2}$?

If $k = \Theta(n^{c})$, then what is $m$ if $c < 1$, $c > 1$? Is $m = \Omega(n^{c+1})$ in general?

I was trying to generalize birthday paradox problem. By Pigeon hole I can get only $m=\Omega(n^{2})$ if $k=O(n)$ for 'certainty'. Using pigeon hole I cannot give a probabilistic argument here. Was curious for general sizes of $m$, $n$ and $k$ and what would replace pigeon hole?

http://www.math.ucsd.edu/~tkemp/180A/180A.LectureNotes.pdf says answer for $n=365$ and general $k$ was not known till $1995$ but does not provide reference.

In this problem, there are two cases: $k < n$ and $k > n$.

-
If $k=\Theta(n)$ then you should need $m=\Theta(n^2)$. – Douglas Zare Jul 16 '13 at 12:12
You can rule out any power smaller than quadratic by Hoeffding's inequality, which isn't sharp. – Douglas Zare Jul 16 '13 at 15:16
Can you explain more? I also think n^2 is needed but Ben's answer which uses Talagrand's inequality seems to imply quasilinearness! – Turbo Jul 16 '13 at 15:26
I could say more, but this is not research level mathematics. en.wikipedia.org/wiki/Hoeffding%27s_inequality The application is straightforward. If you want to know more about what Ben Barber meant, ask him. – Douglas Zare Jul 16 '13 at 16:30
Sorry Arul, I was imagining $k$ fixed, which is not the question you asked. If $k = \Theta (n)$ then my heuristic agrees with what Douglas Zare said. – Ben Barber Jul 16 '13 at 17:07

Googling on "birthday problem 1995" turns up references to a paper by L. Holst, the abstract to which reads

The general birthday problem with unlike birth probabilities and the waiting time N until c people with the same birthday have been obtained is studied in this article. It is shown that N is stochastically largest when the birth probabilities are equal. By embedding in Poisson processes it is shown how the moments of N can be expressed in moments of the minimum of gamma random variables.

The Holst paper doesn't appear to be available online, but a later paper by Camarri and Pitman may be worth a look.

-
Does it give information for what happens if $k = \Theta(n^{c})$. Then is $m = O(n^{c+1})$ or $m = O(n^{2c})$ for both $c <1$ and $c >1$? – Turbo Jul 17 '13 at 12:54

Edit: This answer was for $k$ fixed, rather than $k = \Theta (n)$ as specified in the original question.

You should be able to use (for example) Talagrand's concentration inequality to show that the number of k-sets which are all the same colour is tightly concentrated. So the critical value for $m$ should satisfy $\binom m k / n^{k-1} \approx 1$, i.e. $m \approx n^{1-1/k}$, which happily agrees with the answer for the birthday problem.

There are lots of details to check here if you want to make sure this argument holds water.

-
Could you please explain more? I am unfamiliar with concentration inequalities. – Turbo Jul 16 '13 at 11:17
I'm afraid I don't have time to expand this example right now, but you might find this answer to an older question helpful: mathoverflow.net/questions/119157/runs-in-coin-flips/… Concentration inequalities are wonderful tools, and my first port of call when presented with anything remotely resembling random variables on product spaces. – Ben Barber Jul 16 '13 at 11:24
Interesting. OK. Let me take a look and see what I can gather. Thankyou for the link. – Turbo Jul 16 '13 at 11:27
If $k = \theta(n^{b})$, where $b>0$, would you still need $\theta(n^{2b})$ as $m$ for both $b <1$ and $b>1$? – Turbo Jul 16 '13 at 18:19
If $0 < b << 1$, would the concentration trick show something different? – Turbo Jul 16 '13 at 18:35