Hash Crash Reloaded

A great problem, @Agnishom Chattopadhyay .

The probability that an element collides after $n$ elements are inserted (means there are total of $n+1$ elements) is

$P(n)=\frac{1000\times (1000-1)\times \dots \times (1000-n+1)}{1000^{n}} \times \frac{n}{1000}$ .

Hence, the expected value is

$\sum_{n=0}^{999} (n+1) P(n) = 40.3032129262$

Here is the code :

1
2
3
4
5
6
7
8
9

def prob(n):
    v = 1.0
    for i in range(n):
        v = v * (1000 - i) / 1000
    return v * n / 1000

ans = sum([(n + 1) * prob(n)  for n in range(1000)])

print ans

If this is not convincing enough, let's try Monte-Carlo simulation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from random import randint

tst = 0
cnt = 0
while True:
    L = [0 for i in range(1001)]
    while True:
        cnt += 1
        x = randint(1,1000)
        if L[x] == 1:
            break
        L[x] = 1
    tst += 1
    if tst % 10000 == 0:
        print tst, cnt * 1.0 / tst

Which returns 40.316 .