Timeline for Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27, 2023 at 8:55 | comment | added | dohmatob | Ah, of course. Thanks again. | |
| Mar 27, 2023 at 0:38 | answer | added | kodlu | timeline score: 0 | |
| Mar 26, 2023 at 15:14 | comment | added | Jason Gaitonde | It's actually a bit easier. If $N=2^{nc}$ and $X=\sum_{1\leq i \neq j\leq N} A_{i,j}$ as in my comment below, then $\mathbb{E}[X] = 2^{2cn+H(\gamma)n-1+o(1)}$ while $\text{Var}(X)=\sum_{i\neq j} \text{Var}(A_{i,j})\leq \mathbb{E}[X]$. When $c>(1-H(\gamma))/2$, the mean is exponentially large and its square exponentially dominates the variance, so Chebyshev's inequality implies $X$ is 0 with exponentially small probability for any such $c$. | |
| Mar 24, 2023 at 19:51 | comment | added | dohmatob | Thanks again. If by "second moment argument", you mean exponentiating, using independence, and then using Paley–Zygmund inequality, then I kinda see how to get there :). If not, please go ahead and post your thoughts in answer. | |
| Mar 24, 2023 at 18:13 | comment | added | Jason Gaitonde | Are you satisfied with Will's answer below now? I can elaborate on why the value he derives is tight for $\alpha=1$ using the second moment argument if needed, just didn't have space below. | |
| Mar 23, 2023 at 19:29 | history | edited | dohmatob | CC BY-SA 4.0 |
added 30 characters in body
|
| Mar 23, 2023 at 17:50 | answer | added | Will Sawin | timeline score: 2 | |
| Mar 23, 2023 at 17:26 | history | asked | dohmatob | CC BY-SA 4.0 |