MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. 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.

share|cite|improve this answer
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.

share|cite|improve this answer
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:… 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.