Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$

Question

Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \ne j} d_H(x_i,x_j)$, where $d_H$ is Hamming distance. Note that $\delta_{N,n}$ is a random variable with values in $\{0,\ldots,n\}$. I'm interested in good tail bounds for $\delta_{N,n}$. To this end, given $\gamma \in (0,1)$, define $p_{N,n,\gamma} \in [0,1]$ by

\begin{eqnarray} p_{N,n,\gamma} := \mathbb P(\delta_{N,n} \ge \gamma n). \end{eqnarray}

Question 1. What are good upper and lower-bounds for $p_{N,n,\gamma}$ ?

I'm particularly interested in the following case:

• $N = N(n) \asymp n$, i.e $cn \le N \le Cn$ for some constants $c,C \gt 0$.
• $N = N(n) \asymp 2^{c n^\alpha}$ for some constants $\alpha \in (0,1]$ and $c \gt 0$
• ...

Phase transition

Now, let $N = N(n) = 2^{cn^\alpha}$ for some constants $\alpha \in (0,1]$ and $c \gt 0$.

Question 2. For what values of $(c,\alpha)$ do we have $\liminf_{n \to \infty} p_{N(n),n,\gamma} = 0$ ?

Question 3. For what values of $(c,\alpha)$ do we have $\limsup_{n \to \infty} p_{N(n),n,\gamma} = 1$ ?

Answer 1

A trivial lower bound is $$p_{N,n,\gamma} \geq 1 - \binom{N}{2} \mathbb P ( d_H (x_1,x_2)< \gamma n) \geq 1 - \binom{N}{2} ( \gamma^{-\gamma} (1-\gamma)^{-(1-\gamma) } 2^{-1} ) ^n $$ with the last inequality for $\gamma \leq 1/2$.

This in particular implies that $\lim_{n\to\infty} p_{2^{cn^\alpha}, n,\gamma}=1$ for all $\gamma < 1/2$ and $\alpha<1$, as well as for $\gamma<1/2, \alpha=1, c< ( (-\gamma \log \gamma - (1-\gamma) \log (1-\gamma) ) - 1 )/2$ (with the logarithms to base $2$).

I would guess that this value of $c$ is actually the transition point.

Answer 2

I am not sure if this is correct/useful but here goes:

We can use Theorem 21 from Lugosi's concentration of measure notes, in a differential manner. Let $m=N(N-1)/2,$ and let the differences of your variables $x_i\oplus x_j$ for $1\leq i<j\leq N,$ form the set $A:=\{X_1,\ldots,X_m\}.$ You can then apply his bound to $d(0,A)=\min_{y \in A} d(0,y),$ since the minimum Hamming distance of your original set of $N$ points is the distance to the zero vector of the differences of the points listed in $A$.

Since the set $A$ is made up of $m=N(N-1)/2$ i.i.d. uniform vectors (differences are uniform i.i.d. if the $x_i$ are i.i.d.) we have $$ \mathbb{P}(A)=\frac{N(N-1)/2}{2^n}\sim \frac{N^2}{2^{n+1}}. $$ By Theorem 21, for any $t > 0$, $$\mathbb{P}\left(d(0,A) \geq t + \sqrt{\frac{n}{2} \mathrm{log}\frac{1}{\mathbb{P}(A)}}\right) \leq e^{-2t^2/n}.$$

Now the logarithm inside the square root is $\sim \ln 2 \cdot (n+1)-2 \log N,$ giving $$\mathbb{P}\left(d(0,A) \geq t + \sqrt{\frac{\ln 2}{2}(n^2+n)-n\ln N} \right) \stackrel{<}{\sim} e^{-2t^2/n},$$ which can be rewritten approximately as $$\mathbb{P}\left(d(0,A) \geq t + \sqrt{n\left[\frac{\ln 2}{2} (n+1)-\ln N\right]} \right) \leq e^{-2t^2/n}.$$ If we want to obtain the bound for $d(0,A)\geq \gamma n,$ and if $N=2^{c n},$ we have $\ln N=(\ln 2) c n$ and if we pick $c$ small enough for the first term inside the square brackets inside the square root to dominate yielding an upper bound of the form $$\mathbb{P}\left(d(0,A) \geq t + \sqrt{c'n^2} \right)= \mathbb{P}\left(d(0,A) \geq t + c''n\right)\leq e^{-2t^2/n}.$$

Now let $\lambda n = t + c''n,$ which implies $t=(\lambda-c'')n,$ giving

$$\mathbb{P}\left(d(0,A) \geq t + \sqrt{c'n^2} \right)= \mathbb{P}\left(d(0,A) \geq t + c''n\right)\leq e^{-2(\lambda - c'')^2/n}.$$