What is the expectation value of the minimum 'distance' between two random 64-bit numbers out of a set of N?

Question

Assume we have a set of N random integer numbers in the interval [0, 2^64> (or equivalent, consider N randomly chosen corners (vectors) of a 64-dimensional hypercube with side 1).

Find the two numbers that have the smallest number of bits that are different (or equivalent, find the square of the minimum distance between two of those N corners). Lets call this number of different bits 'the distance'. This distance can be zero (two numbers are equal / two of the vectors are the same). It can not be 64 when N is larger than 2.

Empirically I determined that for N = 39800, the (expected) minimum distance is near 9. That is; with 39800 numbers/vectors you can form 39800 * 39799 = 1584000200 pairs - and most of the time I found one or more pairs had only 9 different bits while all other pairs had more than 9 different bits. Sometimes this minimum was 10 or 8 or even 7, but on average I'd say 9.

Can someone derive a function that gives the expectation value for the minimum distance as function of N? For example, such a function could give f(39800) = 8.438....

Note that this problem is remotely related to the birthday paradox: having 39800 people and 2^64 birthdays - you could calculate what the chance is that two people have the same birthday; but that corresponds to asking what is the chance that the distance is zero. Instead I want to know what the expectation value is for the minimum distance (the chance that that is zero is still very very small).

Answer 1

• There are in fact ${39800 \choose 2}= 792000100$ pairs (half your number, because of duplicates). Let's call this $m$.

• The probability that a particular distance is $n$ or less is $p_n=\sum\limits_{i=0}^{n}{64 \choose i}2^{-i}$.

• For $n=9$ this is about $p_9=1.77\times 10^{-9}$ and $p_9 m \approx 1.4$ so we are talking about opposite orders of magnitude.

• The distances are not quite independent but there are so many pairs that they are close to independent.

• Assuming independence, the probability that any of $m$ distances are $n$ or less is $1-(1-p_n)^m$

• So the probability that the minimum distance is exactly $n$ is $(1-p_{n-1})^{m}-(1-p_n)^m$ which give the following probabilities for the minimum distance

   n    prob. minimum distance is n
   2    0.0000001
   3    0.0000018
   4    0.0000273
   5    0.0003273
   6    0.0032126
   7    0.0262251
   8    0.1679132
   9    0.5563657
  10    0.2455585
  11    0.0003685
  

with a median and mode of $9$ and mean about $9.01$.

This seems broadly consistent with your observation of "most of the time I found one or more pairs had only 9 different bits while all other pairs had more than 9 different bits. Sometimes this minimum was 10 or 8 or even 7, but on average I'd say 9."