4
$\begingroup$

If we sample $3$ binary strings of length $n$, uniformly and independently, what is the expected minimum Hamming distance between the closest pair?

Numerically, it seems to be asymptotic to $n/2$ but it would be great to know if there is an exact formula.

$\endgroup$
3
$\begingroup$

I realized that my original answer was unnecessarily complicated. I’m preserving it below, but here’s a more efficient approach.

As below, without loss of generality fix the first string to be all zeros. Now consider the counts $a_{ij}$ of positions in which the second and third string have the values $i$ and $j$, respectively. In contrast to the variables in the original solution, these four variables are all on an equal footing. They are all close to $\frac n4$. The Hamming distances are

\begin{eqnarray} h_{12}&=&a_{10}+a_{11}\;,\\ h_{13}&=&a_{01}+a_{11}\;,\\ h_{23}&=&a_{01}+a_{10}\;, \end{eqnarray}

and $s=\frac12\sum_{ij}a_{ij}$ and $\Delta_{ab}=h_{ab}-s$ form an orthogonal basis of the space. The count of strings is

\begin{eqnarray} 2^{-2n}\binom n{a_{00},a_{01},a_{10},a_{11}} &=& 2^{-2n}\frac{n!}{\prod_{ij}a_{ij}!} \\ &\approx& 2^{-2n}\frac{\sqrt{2\pi n}}{\prod_{ij}\sqrt{2\pi a_{ij}}}\exp\left(n\log n-\sum_{ij}a_{ij}\log a_{ij}\right)\;. \end{eqnarray}

As below, we can take the square roots to be constant, so they yield a factor $2^4(2\pi n)^{-\frac32}$. With

\begin{eqnarray} 2a_{00}&=&s-\Delta_{12}-\Delta_{13}-\Delta_{23}\;,\\ 2a_{01}&=&s-\Delta_{12}+\Delta_{13}+\Delta_{23}\;,\\ 2a_{10}&=&s+\Delta_{12}-\Delta_{13}+\Delta_{23}\;,\\ 2a_{11}&=&s+\Delta_{12}+\Delta_{13}-\Delta_{23}\;,\\ \end{eqnarray}

we get

\begin{eqnarray} && 2^{-2n}2^4(2\pi n)^{-\frac32}\iiiint\prod_{ij}\mathrm da_{ij}\delta\left(\sum_{ij}a_{ij}-n\right)\min(h_{12},h_{13},h_{23})\exp\left(n\log n-\sum_{ij}a_{ij}\log a_{ij}\right) \\ &\approx& 2^4(2\pi n)^{-\frac32}\iiiint\mathrm d\Delta_{12}\mathrm d\Delta_{13}\mathrm d\Delta_{23}\mathrm ds\delta(2s-n)\left(\frac n2+\min(\Delta_{12},\Delta_{13},\Delta_{23})\right)\exp\left(-\frac1{2n}\right. \\ && \left.\vphantom{\frac1{2n}}\left((-\Delta_{12}-\Delta_{13}-\Delta_{23})^2+(-\Delta_{12}+\Delta_{13}+\Delta_{23})^2+(\Delta_{12}-\Delta_{13}+\Delta_{23})^2+(\Delta_{12}+\Delta_{13}-\Delta_{23})^2\right)\right) \\ &=& \frac n2+2^3(2\pi n)^{-\frac32}\iiint\mathrm d\Delta_{12}\mathrm d\Delta_{13}\mathrm d\Delta_{23} \min(\Delta_{12},\Delta_{13},\Delta_{23})\exp\left(-\frac2n\left(\Delta_{12}^2+\Delta_{13}^2+\Delta_{23}^2\right)\right) \\ &=& \frac n2-\frac34\sqrt{\frac n\pi}\;, \end{eqnarray}

where the last integral is evaluated as below. This treatment should lend itself more readily to generalization to higher $N$.


Original answer:

Without loss of generality fix the first string to be all zeros. The second one has probability $2^{-n}\binom nm$ to have $m$ ones, and thus to have Hamming distance $m$ from the first string. The third one has probability

$$ 2^{-n}\binom mk\binom{n-m}l $$

to have $k$ zeros where the second string has ones and $l$ ones where the second string has zeros, and thus to have Hamming distance $k+l$ from the second string and $m-k+l$ from the first string. Thus the mean minimum distance is

$$ 2^{-2n}\sum_{m=0}^n\sum_{k=0}^m\sum_{l=0}^{n-m}\binom nm\binom mk\binom{n-m}l\min\left(m,k+l,m-k+l\right)\\=2^{-2n}\sum_{m=0}^n\sum_{k=0}^m\sum_{l=0}^{n-m}\frac{n!}{k!(m-k)!l!(n-m-l)!}\min\left(m,k+l,m-k+l\right)\;.$$

For large $n$, all three distances will be close to $\frac n2$, so $m\approx\frac n2$ and $k\approx\frac n4$, $l\approx\frac n4$. We can approximate the factorials and replace the bounded sums by unbounded integrals to obtain

$$ 2^{-2n}\int_{-\infty}^\infty\mathrm dm\int_{-\infty}^\infty\mathrm dk\int_{-\infty}^\infty\mathrm dl\min\left(m,k+l,m-k+l\right)\frac{\sqrt{2\pi n}}{\sqrt{2\pi k}\sqrt{2\pi(m-k)}\sqrt{2\pi l}\sqrt{2\pi (n-m-l)}}\\\exp\left(n\log n-k\log k-(m-k)\log(m-k)-l\log l-(n-m-l)\log(n-m-l)\right)\;. $$

With $m=\left(\frac12+\mu\right)n$, $k=\left(\frac14+\kappa\right)n$ and $l=\left(\frac14+\lambda\right)n$ this is

$$ 2^{-2n}\left(\frac n{2\pi}\right)^\frac32\int_{-\infty}^\infty\mathrm d\mu\int_{-\infty}^\infty\mathrm d\kappa\int_{-\infty}^\infty\mathrm d\lambda \left(\frac12+\min\left(\mu,\kappa+\lambda,\mu-\kappa+\lambda\right)\right)n \\ \frac1{\sqrt{\frac14+\kappa}\sqrt{\frac14+\mu-\kappa}\sqrt{\frac14+\lambda}\sqrt{\frac14-\mu-\lambda}} \\ \exp\left(-n\left(\left(\frac14+\kappa\right)\log\left(\frac14+\kappa\right)+\left(\frac14+\mu-\kappa\right)\log\left(\frac14+\mu-\kappa\right)\right.\right. \\ \left.\left.+\left(\frac14+\lambda\right)\log\left(\frac14+\lambda\right)+\left(\frac14-\mu-\lambda\right)\log\left(\frac14-\mu-\lambda\right)\right)\right) \\ \approx \frac n2+n\cdot2^4\left(\frac n{2\pi}\right)^\frac32\int_{-\infty}^\infty\mathrm d\mu\int_{-\infty}^\infty\mathrm d\kappa\int_{-\infty}^\infty\mathrm d\lambda\min\left(\mu,\kappa+\lambda,\mu-\kappa+\lambda\right) \\ \exp\left(-2n\left(\kappa^2+(\mu-\kappa)^2+\lambda^2+(\mu+\lambda)^2\right)\right) $$

(where we can take the square roots in the denominator to be constant because their linear terms cancel). This is a Gaussian integral with covariance matrix

$$ 4n\pmatrix{2&-1&1\\-1&2&0\\1&0&2}\;, $$

which has eigenvalues $4n\left(2+\sqrt2\right)$, $4n\cdot2$ and $4n\left(2-\sqrt2\right)$ and corresponding orthonormal eigenvectors $\left(\frac1{\sqrt2},-\frac12,\frac12\right)$, $\left(0,\frac1{\sqrt2},\frac1{\sqrt2}\right)$ and $\left(-\frac1{\sqrt2},-\frac12,\frac12\right)$. We can check at this point that the integral without the minimum Hamming distance is $1$, so the approximations have preserved the normalization.

By symmetry, we can evaluate the part of the integral where the minimum is $\mu$ and multiply by $3$. With the transformation

$$ \pmatrix{\mu\\\kappa\\\lambda}=\pmatrix{ \frac1{\sqrt2}&0&-\frac1{\sqrt2}\\ -\frac12&\frac1{\sqrt2}&-\frac12\\ \frac12&\frac1{\sqrt2}&\frac12 } \operatorname{diag}\left(4n\left(2+\sqrt2\right),4n\cdot2,4n\left(2-\sqrt2\right)\right)^{-\frac12} \pmatrix{x\\y\\z} $$

that transforms the covariance matrix to the identity, the boundary planes $\mu\lt\kappa+\lambda$ and $\mu\lt\mu-\kappa+\lambda$, that is, $\kappa\lt\lambda$, become

$$\sqrt{2-\sqrt2}\cdot x-\sqrt{2+\sqrt2}\cdot z\lt2y$$

and

$$\sqrt{2-\sqrt2}\cdot x+\sqrt{2+\sqrt2}\cdot z\gt0\;,$$

respectively. The $\mu$ in the integrand becomes $\frac1{4\sqrt n}\left(\sqrt{2-\sqrt2}\cdot x-\sqrt{2+\sqrt2}\cdot z\right)$. It makes sense to rotate to

$$ \pmatrix{u\\v}=\frac12\pmatrix{ \sqrt{2-\sqrt2}&-\sqrt{2+\sqrt2} \\ \sqrt{2+\sqrt2}&\sqrt{2-\sqrt2} }\pmatrix{x\\z} $$

so that the bounds are $u\lt y$ and $u\lt v$, respectively, and the factor $\mu$ in the integrand is $\frac u{2\sqrt n}$. Note that the bounds are now manifestly symmetric and include the third of the solid angle in which $u$ is the least of $u,v,y$. We can now evaluate the integral in spherical coordinates $y=r\cos\theta$, $u=r\sin\theta\cos\phi$ and $v=r\sin\theta\sin\phi$:

\begin{eqnarray} && n\cdot(2\pi)^{-\frac32}\iiint\limits_{u\lt\min(v,y)}\frac u{2\sqrt n}\mathrm e^{-\frac12\left(u^2+v^2+y^2\right)}\mathrm du\,\mathrm dv\,\mathrm dy \\ &=& \frac{\sqrt n}2\cdot(2\pi)^{-\frac32}\int_0^\infty\mathrm e^{-\frac12r^2}r^3\mathrm dr\int_{\frac\pi4}^{\frac{5\pi}4}\int_0^{\operatorname{arccot}\cos\phi}\sin^2\theta\mathrm d\theta\cos\phi\mathrm d\phi \\ &=& \frac{\sqrt n}2\cdot(2\pi)^{-\frac32}\int_0^\infty\mathrm e^{-\frac12r^2}r^3\mathrm dr\int_{\frac\pi4}^{\frac{5\pi}4}\frac12\left(\operatorname{arccot}\cos\phi-\frac{\cos\phi}{1+\cos^2\phi}\right)\cos\phi\mathrm d\phi \\ &=& \frac{\sqrt n}2\cdot(2\pi)^{-\frac32}\int_{\frac\pi4}^{\frac{5\pi}4}\left(\operatorname{arccot}\cos\phi-\frac{\cos\phi}{1+\cos^2\phi}\right)\cos\phi\mathrm d\phi \\ &=& \frac{\sqrt n}2\cdot(2\pi)^{-\frac32}\left(\pi\left(1-\frac3{\sqrt2}\right)-\pi\left(1-\frac1{\sqrt2}\right)\right) \\ &=& -\frac14\sqrt\frac n\pi\;. \end{eqnarray}

We need to multiply this by $3$ and add it to the main term $\frac n2$ to obtain

$$ \boxed{\frac n2-\frac34\sqrt\frac n\pi}\;. $$

Here’s code that performs a simulation for $n=64$ to check the result. The simulation yields a mean minimum Hamming distance of $28.575$, compared to

$$ \frac{64}2-\frac34\sqrt\frac{64}\pi=32-\frac6{\sqrt\pi}\approx28.615 $$

from the asymptotic analysis.

$\endgroup$
14
  • 1
    $\begingroup$ This answer is the normal approximation: for uncorrelated binomial sums $S_1=\sum_{i=1}^n|Y_i-X_i|$, $S_2=\sum_{i=1}^n|Y_i-Z_i|$, $S_3=\sum_{i=1}^n|X_i-Z_i|$ $$\mathbb E\min(S_1,S_2,S_3)= \frac n2+\sqrt \frac n4 \mathbb E\min\left\{\frac{S_1-n/2}{\sqrt{n/4}},\frac{S_2-n/2}{\sqrt{n/4}},\frac{S_3-n/2}{\sqrt{n/4}}\right\} $$ (by multivariate CLT) $$ \approx \frac n2+\sqrt{\frac n4}\mathbb E\min\{V_1,V_2,V_3\} = \frac n2-\sqrt \frac n4 \cdot \frac{3}{2\sqrt{pi}}=\frac n2-\frac34\sqrt\frac n\pi. $$ math.stackexchange.com/a/473237 where $V_i$ are independent standard normal r.v.'s. $\endgroup$
    – NCh
    Jan 27 '20 at 6:58
  • $\begingroup$ @Nch Could that approach be extended to work for $N >3$ strings, perhaps using numerical integration? $\endgroup$
    – fomin
    Jan 27 '20 at 8:25
  • 1
    $\begingroup$ @fomin: Thanks. I realized that this can actually be done more simply, and in a way that generalizes better for higher $n$; I'll try to post that soon, but I don't know when I'll get around to it. Interesting, I hadn't seen those closed-form answers. It's interesting that Wolfram|Alpha can't find them from the integrals in Robert Israel's answer. Unfortunately, for $n=4$ here we'll have $\binom42=6$ binomial sums, so the integrals up to $5$ don't help in that case :-) Please do let me know when you post the follow-up question. $\endgroup$
    – joriki
    Jan 27 '20 at 11:14
  • 1
    $\begingroup$ @joriki math.stackexchange.com/questions/3524445/… $\endgroup$
    – fomin
    Jan 27 '20 at 14:04
  • 1
    $\begingroup$ @fomin: I've updated the answer with the simpler approach (at the top). $\endgroup$
    – joriki
    Jan 27 '20 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.