1
$\begingroup$

I am generating random 64-bit numbers, in groups of 1000 numbers. How many groups can I expect to generate before there is a collision within one of the groups? Again, I don't care if anything in the first group collides with anything from the second group, only if numbers collide within the same group.

2 Answers 2

1

Working approximately, there are ${1000 \choose 2} = \frac{1000\cdot 999}{2}=499500$ pairs in a group, with each pair having a collision probability of $2^{-64}$, so the chance in one group is $499500 \cdot 2^{-64} \approx 2.7 \cdot 10^{-14}$. We can argue about factors like $e$, but you should expect to generate of order $2.7 \cdot 10^{14}$ before a collision.

  • 0
    OP said there were groups of 1000. Unfortunately I used groups of 64. I'll fix.2011-08-09
1

There are $2^{64 \cdot 1000}$ combinations for the batch of 1000. Probability of having a collision within this batch is

$ 1 - \frac{1}{2^{64 \cdot 1000}} 2^{64} ( 2^{64}-1 ) \ldots (2^{64} - 999) \approx 2.7 \cdot 10^{-14} $

The expected number of batches is the reciprocal of this probability, which is about $3.7 \cdot 10^{13}$.