1
$\begingroup$

I'm now familiar with a lower bound for the birthday problem as exposed in the theorem A.16 of Katz and Lindell book (alternatively see this webpage).

If one denotes by $C(q,N)$ the probability of collision when taking elements independent and uniformly distributed from a set of size $N$ The bound is obtained by assuming $q \le \sqrt{2N}$:

$C(q,N) \ge \frac{q(q-1)}{4N}$

However, the bound that I has been hold in my class is (without the inequality assumption in $q$):

$\forall N \in \mathbb{N}.C(q,N) \ge \frac{(q-1)^2}{2N}$

How can I prove this bound correct?

enter image description here

$\endgroup$
4
  • $\begingroup$ Could you write the proof from your class? $\endgroup$
    – kelalaka
    Dec 5, 2018 at 10:35
  • $\begingroup$ @kelalaka unfortunately (to me) this was just stated and written to me by e-mail, i have no proof whatsoever, so what i'm expecting is to have a counterexample here. i will ask however more details myself $\endgroup$ Dec 5, 2018 at 10:37
  • $\begingroup$ Note that the bound from class is weaker (that is the lower bound is higher) than the one from the book. $\endgroup$
    – SEJPM
    Dec 5, 2018 at 10:44
  • $\begingroup$ @SEJPM in that sense is a "better" lower bound right? that's why i ask $\endgroup$ Dec 5, 2018 at 10:49

2 Answers 2

2
$\begingroup$

The question's $\displaystyle C(q,N) \ge \frac{(q-1)^2}{2N}$ bound is wrong. That's incompatible with the well-known fact that for $N=q^2$ and large, $C(q,N)\approx1-e^{-1/2}\approx39.3\%$.

A correct bound is $\displaystyle C(q,N) \le \frac{(q-1)\,q}{2N}$, valid for all $q$ and $N\ge1$, and tight when $q\ll\sqrt N$.

Another correct bound is $\displaystyle C(q,N) \ge \frac{(q-1)^2}{4N}$ when $1\le q\le\sqrt{2N}$, which follows from the question's lemma.

See this answer for some derivations, but beware that the notation there is $(n,k)$ and $p_n$ where the question has $(q,N)$ and $C(q,N)$.

$\endgroup$
1
$\begingroup$

A larger lower bound is better. The Katz Lindell book bound gives the correct formula. It is $$ (1-e^{-1})\frac{q(q-1)}{2N} \approx 0.316360 \frac{q(q-1)}{N}, $$ which they weaken further to $$ \frac{q(q-1)}{4N} $$ for simplicity.

The bound you ask about which is $$ 0.5 \frac{(q-1)^2}{N}, $$ is actually not weaker but stronger than even the stronger bound of Katz Lindell with the $(1-e^{-1})$ factor, as $N,q$ grow, and I don't see how it can be correct, regardless of the value of $q.$

$\endgroup$
2
  • $\begingroup$ for the part "you wrote it wrong" see the edit above, maybe we are using different versions $\endgroup$ Dec 5, 2018 at 11:12
  • $\begingroup$ You’re right. Sorry. $\endgroup$
    – kodlu
    Dec 5, 2018 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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