8
$\begingroup$

I am reading about the birthday attack in Wikipedia:

We consider the following experiment. From a set of $H$ values we choose $n$ values uniformly at random thereby allowing repetitions. Let $p(n; H)$ be the probability that during this experiment at least one value is chosen more than once. This probability can be approximated as $$p(n:H) \approx 1−e^{-{n(n-1) \over 2H}}$$

My question: Where does that $e^{-{n(n-1) \over 2H}}$ value come from?

$\endgroup$
  • $\begingroup$ That 2H looks weird. Shouldn't that be in the denominator? $\endgroup$ – CodesInChaos Jul 16 '13 at 21:16
  • $\begingroup$ @CodesInChaos Look at the linked Wikipedia article. It's ambiguous with $/$ and $\cdot$ priority. $\endgroup$ – orlp Jul 16 '13 at 21:21
  • $\begingroup$ There have been 3 answers given. It would be best to choose one of them and mark it as accepted answer, so this question can be seen as answered by anybody stumbling upon it. $\endgroup$ – Maarten Bodewes Oct 8 '18 at 12:47
8
$\begingroup$

Let's first calculate the chance that every value is unique.

The chance of two values picked being unique is $H - 1 \over H$ because when picking the second value you only have $H - 1$ unique picks left, with one pick being non-unique. Picking a third number has a chance of $H - 2 \over H$ to be unique, so the total chance of picking 3 unique numbers is ${H - 1 \over H} \times {H - 2 \over H}$. This can be continued so that the chance of picking $n$ unique values is:

$${H - 1 \over H} \times {H - 2 \over H} \times \cdots \times {H - (n - 2) \over H} \times {H - (n - 1) \over H}$$

This is exactly the same as the limit for the birthday paradox.

Then a bit more math is required. An approximation is used. For $x \leq 1$ the taylor series of $e$ gives an approximation:

$$e^x \approx 1 + x$$

Then note the following:

$${H - 1 \over H} = 1 - {1 \over H} \approx e^{-{1 \over H}}$$

Then we rewrite the calculate as such:

$$e^{-{1 \over H}} \times e^{-{2 \over H}} \times \cdots \times e^{-{n - 2 \over H}}\times e^{-{n - 1 \over H}} =$$ $$e^{-{1 + 2 + \cdots + n-2 + n-1 \over H}} =$$ $$e^{-{n(n-1)/2 \over H}} = e^{-{n(n-1) \over 2H}} $$

That is the probability that every value picked is unique. If not every value is unique there must be a collision, therefore the chance of a collision is:

$$p(n:H) \approx 1−e^{-{n(n-1) \over 2H}}$$

This is also the value the linked wikipedia article means, but it's a bit ambiguous with $/$ and $\cdot$ priority rules.

$\endgroup$
  • $\begingroup$ Note that I removed the ambiguity from the question to make the questions and answer match, in case anybody cannot find it. Browse to the article to see if it is still there. $\endgroup$ – Maarten Bodewes Oct 8 '18 at 12:44
  • $\begingroup$ Please note that the correct approximation is not that $e^x\approx 1+x$ for $x\leq 1.$ That approximation is multiplicatively very bad for positive $x$ and you use it multiple times. The correct approximation is $e^{-x}\leq 1-x$ for $x>0$ very small. Since $n/H$ is very small, this works. $\endgroup$ – kodlu Oct 8 '18 at 23:36
2
$\begingroup$

Here is a slightly different approach: The total number of ways to pick $n$ numbers among $H$ value allowing repetition (and with the order of picking counted in) is $A=H^n$. The number of ways to pick without repetitions is $B=\frac{H!}{(H-n)!}.$

Clearly, the probability you want to compute is $(A-B)/A=1-B/A$. Now, does $B/A$ contains the exponential you look for ? Using Stirling's formula: $$x!\approx \sqrt{2\pi x}(x/e)^x.$$ We see that: $$ A/B\approx \sqrt{\frac{H-n}{H}}\left(\frac{H-n}{H}\right)^{H-n}e^n. $$

Taking logarithm, we find: $$\log(A/B)\approx (H-n+1/2)\log(1-n/H)+n\approx -(H-n+1/2)(n/H+(n/H)^2/2)+n$$

Develop and remove low order terms to obtain $\log(A/B)\approx n(n-1)/2H$.

Putting everything together indeed yields $$p(n:H)\approx 1-e^{\frac{n(n-1)}{2H}}.$$

The main advantage of this approach is that it avoids taking the product of many approximations (as in nightcracker's answer) which, in general, requires great care.

$\endgroup$
2
$\begingroup$

Here's yet another similar way to get this approximation.

Consider every pairing of n elements from H, ignoring elements paired with themselves but not requiring that the elements be unique. i.e. $Let\ H_n=\{n\ elements\ chosen\ from\ H\}, P_n=\{(h_i,h_j) | h_i,h_j \in H_n\ and\ i\ne j\}$.Each element can be matched with any other element, so there are $\frac{n(n-1)}{2}$ pairs in $P_n$, rejecting $(h_b, h_a)$ if $(h_a,h_b)$ is already present. The probability of any pair not being a match is $(1-1/H)$.

Notice that these pairs being nonmatches are not independent events since if $(h_1,h_2)$ is not a match and $(h_2,h_3)$ is not a match, the probability of $(h_1,h_3)$ not being a match is $(1-\frac{1}{H-1})$.

This approximation treats these as independent events. In that case,
Prob(no_matches_in_$P_n$)=$\ (1-1/H)^{n*(n-1)/2}=(1-1/H)^{H*n(n-1)/(2H)}\approx e^{-n*(n-1)/(2H)}$
Since $\lim_{H \to \infty}(1-1/H)^H=e^{-1}$

$\endgroup$

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.