Estimate the mean minimum Hamming distance

Question

Task

Inputs \$b \leq 100\$ and \$n \geq 2\$. Consider \$n\$ binary strings, each of length \$b\$ sampled uniformly and independently. We would like to compute the expected minimum Hamming distance between any pair. If \$n = 2\$ the answer is always \$b/2\$.

Correctness

Your code should ideally be within \$\pm0.5\$ of the correct mean. However, as I don't know what the correct mean is, for values of \$n\$ which are not too large I have computed an estimate and your code should be within \$\pm0.5\$ of my estimate (I believe my estimate is within \$\pm0.1\$ of the correct mean). For larger values than my independent tests will allow, your answer should explain why it is correct.

• \$b = 99, n = 2^{16}.\$ Estimated avg. \$19.61\$.
• \$b = 89, n = 2^{16}.\$ Estimated avg. \$16.3\$.
• \$b = 79, n = 2^{16}.\$ Estimated avg. \$13.09\$.
• \$b = 69, n = 2^{16}.\$ Estimated avg. \$10.03\$.
• \$b = 59, n = 2^{16}.\$ Estimated avg. \$7.03\$.
• \$b = 99, n = 2^{15}.\$ Estimated avg. \$20.67\$.
• \$b = 89, n = 2^{15}.\$ Estimated avg. \$17.26\$.
• \$b = 79, n = 2^{15}.\$ Estimated avg. \$13.99\$.
• \$b = 69, n = 2^{15}.\$ Estimated avg. \$10.73\$.
• \$b = 59, n = 2^{15}.\$ Estimated avg. \$7.74\$.
• \$b = 99, n = 2^{14}.\$ Estimated avg. \$21.65\$.
• \$b = 89, n = 2^{14}.\$ Estimated avg. \$18.23\$.
• \$b = 79, n = 2^{14}.\$ Estimated avg. \$14.83\$.
• \$b = 69, n = 2^{14}.\$ Estimated avg. \$11.57\$.
• \$b = 59, n = 2^{14}.\$ Estimated avg. \$8.46\$.

Score

Your base score will be the number of the examples above that your code gets right within \$\pm0.5\$. On top of this you should add \$x > 16\$ for the largest \$n = 2^x\$ for which your code gives the right answer within \$\pm0.5\$ for all of \$b = 59, 69, 79, 89, 99\$ (and also all smaller values of \$x\$). That is, if your code can achieve this for \$n=2^{18}\$ then you should add \$18\$ to your score. You only get this extra score if you can also solve all the instances for all smaller \$n\$ as well. The number of strings \$n\$ will always be a power of two.

Time limits

For a single \$n, b\$ pair, your code should run on TIO without timing out.

Rougher approximation answers for larger values of \$n\$

For larger values of \$n\$ my independent estimates will not be as accurate but may serve as a helpful guide nonetheless. I will add them here as I can compute them.

• \$b = 99, n = 2^{17}.\$ Rough estimate \$18.7\$.
• \$b = 99, n = 2^{18}.\$ Rough estimate \$17.9\$.
• \$b = 99, n = 2^{19}.\$ Rough estimate \$16.8\$.

Answer 1

Python 3, score = big(?)

from math import exp, log, log1p

def f(b, n):
    e = n * (n - 1) / 2
    m = 0
    c = 1
    s = 0
    t = 1 << b
    for k in range(b):
        s += c
        m += exp(e * (log1p(-s / t) if 2 * s < t else log((t - s) / t)))
        c = c * (b - k) // (k + 1)
    return m

Try it online!

The Hamming distance \$D_{x, y}\$ between any two of the strings (\$1 \le x < y \le n\$) is a random variable distributed as the Binomial distribution \$B{\left(b, \tfrac12\right)}\$:

$$ \Pr[D_{x, y} > k] = 1 - \frac{1}{2^b} \sum_{i=0}^k \binom bi. $$

Furthermore, any (distinct) two of these \$\binom n2\$ random variables are independent.

If we make the incorrect but empirically useful assumption that all \$\binom n2\$ of these random variables are independent, then we can compute the distribution of their minimum \$D = \min_{1 \le x < y \le n} D_{x,y}\$ exactly:

$$ \begin{gather*} \Pr[D > k] = \left(1 - \frac{1}{2^b} \sum_{i=0}^k \binom bi\right)^{\binom n2}, \\ \mathbb E[D] = \sum_{k=0}^{b-1} \Pr[D > k]. \end{gather*} $$

This result can be computed extremely quickly and seems to be close enough. Numerical evidence suggests that the absolute error is worst at \$b = 1, n = 3\$ (where we estimate the expected minimum as \$\tfrac18\$ when it is actually \$0\$), and drops off quickly to zero as \$b\$ and/or \$n\$ get large.