3
$\begingroup$

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{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_{{n^t}-1}\cap v_{{n^t}}$.

Is there is a $c>1$ such that $$\Bbb{Pr}(|v|_{hamming}<2^{{n}/c})>\frac{1}2?$$

$\endgroup$

1 Answer 1

0
$\begingroup$

The probability that a fixed entry of $v$ is 1 equals $2^{-n^{s+t}}$. Hence the expected Hamming weight of $v$ is $2^{n-n^{s+t}}$. If $s+t\geq 1$, this implies that with high probability the Hamming weight of $v$ is much smaller than $2^{n/c}$. If $s+t<1-\varepsilon$, use the second moment trick: If the first coordinate of $v_1$ is 1, the conditional probability that the second is 1 is $\frac{2^{n−n^s}-1}{2^n-1}<2^{-n^s}$, hence the variance of the hamming weight of $v$ is slightly smaller than the variance of a sum of independent random variables would be. Hence $|v|$ is larger than $2^{(1-\varepsilon)n}$ with probability tending to 1.

$\endgroup$
2
  • $\begingroup$ Shouldn't it be $2^{\epsilon n}$? $\endgroup$
    – Turbo
    Jun 21, 2015 at 1:12
  • $\begingroup$ The expected weight is $2^{n-n^{s+t}}$. So if $s+t<(1-\varepsilon)$, and $n$ is large, the expected weight is larger than $2^{(1-\varepsilon)n}$. $\endgroup$ Jun 22, 2015 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.