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

6 events

when toggle format	what		by	license	comment
Mar 23, 2023 at 21:47	comment	added	dohmatob		Indeed thanks. Comment deleted.
Mar 23, 2023 at 20:51	comment	added	Jason Gaitonde		@dohmatob sure, but up to the sign thing, this value should be tight. If you sample $x_1,\ldots,x_N$, the events $A_{i,j}=\{d_H(x_i,x_j)<\gamma n\}$ with $i\neq j$ are pairwise independent, so a simple second moment argument works (this value of $c$ gives the exact threshold when the expected number of close pairs is exponentially small/large). There is no transition for constant $c$ when $\alpha<1$ and $n\to \infty$; with extremely high probability, the minimum distance will have minimum distance at least $n/2-O(\sqrt{n^{1+\alpha}})=(1/2-o_c(1))n$ by Chernoff where the constant depends $c$.
Mar 23, 2023 at 20:22	comment	added	dohmatob		You probably meant $0 \lt c \lt (1 - H_2(\gamma))/2$ or something like that.
Mar 23, 2023 at 20:17	comment	added	dohmatob		N.B.: Your condition on $c$ can be written $0 \lt c \lt (H_2(\gamma) - 1)/2$, where $H_2(\gamma) := -\gamma \log_2(\gamma) - (1-\gamma)\log_2(1 - \gamma)$ is the binary entropy. It is known that $0 \lt H_2(\gamma) \le H_2(1/2) = 1$ for all $\gamma \in (0,1)$. Thus, the $0 \lt c \lt (H_2(\gamma) - 1)/2 \le 0$ is impossible (i.e it never holds). Or am I missing something ?
Mar 23, 2023 at 18:08	history	edited	Will Sawin	CC BY-SA 4.0	added 123 characters in body
Mar 23, 2023 at 17:50	history	answered	Will Sawin	CC BY-SA 4.0