Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on $\{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$ ?