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.
Expected attempts before collision in multiple random numbers spaces
1
$\begingroup$
statistics
random
2 Answers
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.
-
0OP 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}$.