What is the mean smallest Hamming distance asymptotic to?

Question

Consider a collection $S_n$ of $n$ independent and uniformly distributed binary strings, each of length $n$. Let $f(S_n)$ be the smallest Hamming distance between any pair of strings in $S_n$. I am interested in $\mathbb{E}(f(S_n))$.

Let $X$ be the Hamming distance between a randomly chosen pair of strings in $S_n$. If we let $\mu = \frac{n}{2}$ then we know by the Chernoff bound that:

$$P( X \le (1-\delta)\mu) \le e^{-\frac{\delta^2\mu}{2}}, \qquad 0 \le \delta \le 1.$$

and

$$Pr( X \ge (1+\delta)\mu)\le e^{-\frac{\delta^2\mu}{2+\delta}}, \qquad 0 \le \delta$$

Therefore we may suspect that $\mathbb{E}(f(S_n))$ will be close to $\frac{n}{2}$ for large $n$.

For small $n$, we have e.g. $\mathbb{E}(f(S_4)) = \frac{3}{4}$.

My question is this:

What is $\mathbb{E}(f(S_n))$ asymptotic to?

I am particularly interested in the lower order terms.

Answer 1

Between 2 and 100, a fair estimate seems to be $$\mathbb{E}(f(S_n))\approx \frac n2+1-\frac12\sqrt{\pi n\ln(n+1)}$$ Here is the graph after $n/2$ has been subtracted from both sides

It may be possible to derive that formula or a similar one by assuming all of the $n\choose2$ distances are independent and normally distributed.

Answer 2

I'm surprised nobody more qualified than me has attempted a solution. Here's my attempt. It is non-rigorous in a few places and I will point them out.

As the OP implies, the linear term of $E[f(S_n)]$ is $\frac n2$. The min distance is obviously going to be less than $\frac n2$, so there is a gap $g(n)$, i.e. $E[f(S_n)] = \frac n2 - g(n)$ where $g(n)$ is positive and sub-linear.

Claim: for any constant $c \in \mathbb{R}$, the gap $g(n) > c\sqrt{n}$ asymptotically.
(Note that this is weaker than Empy2's experimental finding of $g(n) \approx c \sqrt{n \ln n}.)$

My approach is to find $h(n)$ s.t. $P(f(S_n) > \frac n2 - h(n)) \to 0$. This would imply $E[f(S_n)] \le \frac n2 - h(n)$ and provide a lower bound to the gap: $g(n) = \frac n2 - E[f(S_n)] \ge h(n)$.

Let $D_{ij}$ denote the distance between string $i$ and string $j$, for $1 \le i < j \le n$. Note that all $D_{ij}$ are identically distributed as $D\sim Binomial(n, \frac12)$, although they are not independent. We have:

$$ \begin{array}{} P(f(S_n) > \frac n2 - h(n)) &=& P(\bigcap_{i<j} ~(D_{ij} > \frac n2 - h(n)))\\ &\overset{?}{<}& \prod_{i < j}~ P(D_{ij} > \frac n2 - h(n)) \\ &=& P(D > \frac n2 - h(n))^{n(n-1)/2} \\ &:=& a \end{array} $$

The "$\overset{?}{<}$" step is biggest non-rigorous hole in my approach. The intuition is that having some $D_{ij} > \frac n2 - h(n)$ would "space out" strings $i$ and $j$, and make it harder for another $D_{i'j'} > \frac n2 - h(n)$, i.e. the two events are "anti-correlated", so the probability of the conjunction is less than if they were independent events, i.e. the product of individual probabilities.

Anyway, the next non-rigorous step is to use the Gaussian approximation to Binomial. We have $Var(D) = \frac n4$ so $\frac Dn \sim N(\frac 12, \sigma= {1 \over 2\sqrt{n}})$.

$$ \begin{array}{} b := P(D > \frac n2 - h(n)) &=& P(\frac Dn - \frac 12 > -{h(n) \over n})\\ &=& 1 - P(\frac Dn - \frac 12 \le -{h(n)\over n})\\ &\approx& 1 - \Phi(-{h(n) / n \over \sigma})\\ &=& 1 - \Phi(-{2 h(n) \over \sqrt{n}})\\ &:=& 1 - r(n) \end{array} $$

where $\Phi(x) = P(N(0,1) \le x)$ is the cdf of a standard normal variable.

Note that $-{2 h(n) \over \sqrt{n}} < 0 \implies r(n) := \Phi(-{2 h(n) \over \sqrt{n}}) \in (0, \frac12) \implies b \in (\frac12, 1)$, and in fact for interesting choices of $h(n)$ we will have $r(n) \to 0, b \to 1$. However, all we need is that $a = b^{n(n-1)/2} \to 0$, and this can be achieved by having $r(n) \to 0, b \to 1$ slowly enough. But first, we can now prove:

Claim: for any constant $c \in \mathbb{R}$, the gap $g(n) > c\sqrt{n}$ asymptotically.

Proof: take $h(n) = c\sqrt{n} \implies b = 1 - \Phi(-2c) = $ some constant $< 1 \implies a = b^{n(n-1)/2} \to 0. ~\square$

Further thoughts: When $h(n) = c\sqrt{n}$, we have $r(n) = \Phi(-2c)=$ a constant $> 0$. More interestingly, we can increase $h(n)$ beyond $\sqrt{n}$ and let $r(n) \to 0$. One way to do that and still have $a \to 0$ is to have $t(n) := {1 \over r(n)}$ grow slower than $n^2$, i.e. in the little-o notation:

$$t(n) := {1 \over r(n)} = o(n^2)$$

because if the above holds, then $n^2 / t(n) \to \infty$ and:

$$a = (1 - r(n))^{n(n-1)/2} = \big( (1-{1 \over t(n)})^{t(n)} \big)^{n(n-1)/2t(n)} \to e^{-n(n-1)/2t(n)} \to 0$$

At this point, the problem becomes bounding the tail of a Gaussian $r(n) = \Phi(-{2h(n) \over \sqrt{n}})$. I'm sure lots of work has been done on this issue, and I am completely out of my depth.

One weird aspect is that in this approach, we need to lower bound the Gaussian tail: we need $r(n) \to 0$ slowly enough s.t. $a \to 0$. So e.g. Chebyshev's inequality which gives the upperbound

$$r(n) = \Phi(-{2h(n) \over \sqrt{n}}) \le \frac12 {n \over (2 h(n))^2}$$

is in the wrong direction and does not help (at least not in this direct way).