Skip to main content
2 of 2
added 220 characters in body
kodlu
  • 10.4k
  • 2
  • 36
  • 55

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}.$$

kodlu
  • 10.4k
  • 2
  • 36
  • 55