2
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ If $k=\Theta(n)$ then you should need $m=\Theta(n^2)$. $\endgroup$ Jul 16, 2013 at 12:12
  • $\begingroup$ You can rule out any power smaller than quadratic by Hoeffding's inequality, which isn't sharp. $\endgroup$ Jul 16, 2013 at 15:16
  • $\begingroup$ Can you explain more? I also think n^2 is needed but Ben's answer which uses Talagrand's inequality seems to imply quasilinearness! $\endgroup$
    – Turbo
    Jul 16, 2013 at 15:26
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 16, 2013 at 16:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ben Barber
    Jul 16, 2013 at 17:07

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$? $\endgroup$
    – Turbo
    Jul 17, 2013 at 12:54
0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Could you please explain more? I am unfamiliar with concentration inequalities. $\endgroup$
    – Turbo
    Jul 16, 2013 at 11:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ben Barber
    Jul 16, 2013 at 11:24
  • $\begingroup$ Interesting. OK. Let me take a look and see what I can gather. Thankyou for the link. $\endgroup$
    – Turbo
    Jul 16, 2013 at 11:27
  • $\begingroup$ If $k = \theta(n^{b})$, where $b>0$, would you still need $\theta(n^{2b})$ as $m$ for both $b <1$ and $b>1$? $\endgroup$
    – Turbo
    Jul 16, 2013 at 18:19
  • $\begingroup$ If $0 < b << 1$, would the concentration trick show something different? $\endgroup$
    – Turbo
    Jul 16, 2013 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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