Estimate the mean minimum Hamming distance
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.