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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Shouldn't the answer dependent of the batch size too ? Is the batch size grows, the expected number of generations needed should decrease. If batch size > 2^64, then one generation is enough. $\endgroup$ – Sasha Aug 9 '11 at 15:57
  • $\begingroup$ OP said there were groups of 1000. Unfortunately I used groups of 64. I'll fix. $\endgroup$ – Ross Millikan Aug 9 '11 at 16:13

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.