# Birthday Attack

I am reading 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)/2H}$$

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

-
That 2H looks weird. Shouldn't that be in the denominator? – CodesInChaos Jul 16 '13 at 21:16
@CodesInChaos Look at the linked Wikipedia article. It's ambiguous with $/$ and $\cdot$ priority. – orlp Jul 16 '13 at 21:21

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.

-

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.

-

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

-