Estimate the mean minimum Hamming distance 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 &gt; 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\$.
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 &lt;&lt; b
    for k in range(b):
        s += c
        m += exp(e * (log1p(-s / t) if 2 * s &lt; 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 &lt; y \le n\$) is a random variable distributed as the Binomial distribution \$B{\left(b, \tfrac12\right)}\$:

$$
\Pr[D_{x, y} &gt; 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 &lt; y \le n} D_{x,y}\$ exactly:

$$
\begin{gather*}
\Pr[D &gt; 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 &gt; 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.