# 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 > 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\$$.
• I thought this was posted on the Sandbox earlier today. Feb 8, 2020 at 1:19
• @S.S.Anne Yes I posted it there first. I look forward to the first answers!
– user9207
Feb 8, 2020 at 6:38
• The time limit is probably unnecessary as it both limits users to tio languages and needlessly disqualifies solutions that take a long time, but do solve the problem. I understand wanting to prevent brute forcing, but I’d argue that should also be valid Feb 8, 2020 at 7:44
• @ATaco I understand that point of view but it completely changes the challenge. Brute force solutions are valid here of course. It's just a question of what score you get. The time limit/TIO is also crucial as otherwise you will just get a higher score by having a more powerful computer or leaving it to run for longer.
– user9207
Feb 8, 2020 at 7:48
• Using TIO for timing is not a good idea. Had you left this in the sandbox longer, I'd have suggested you switching to requiring that submissions pass your examples within a certain time limit which you would verify (like fastest-code). What you currently have makes it extremely difficult to determine what the score of any submission should actually be. Feb 8, 2020 at 19:03

# 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.

• Awesome! And quickly done too.
– user9207
Feb 8, 2020 at 11:37