Skip to main content
1 of 2
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Probability of Hamming weight

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick $2^{n^t}$ random vectors $\{v_i\}_{i=1}^{2^{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$.

Denote $v_j\cap v_j$ to be vector that is $1$ at a location iff both $v_i,v_j$ are $1$s at that location. Denote $v=v_1\cap v_2\cap\dots\cap v_{2^{n^t}-1}\cap v_{2^{n^t}}$.

Is probability that there is a $c>1$ such that $$|v|_{hamming}<2^{n/c}$$ close to $1$ or $0$?

Turbo
  • 13.9k
  • 1
  • 27
  • 76