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
    Commented 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$ Commented Jun 22, 2015 at 14:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .