Skip to main content
deleted 23 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

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

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

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$?

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?$$

Source Link
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$?