<p>I believe this question was answered positively in three independent papers:</p>

<p>C. R. Rao (1947), "Factorial experiments derivable from combinatorial arrangements of arrays", <em>Journal of the Royal Statistical Society</em> 9:1, 128-139.</p>

<p>B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, and R. Smolensky (1985), "The bit extraction problem or t-resilient functions", <em>26th IEEE Symposium on Foundations of Computer Science</em>, 396-407.</p>

<p>N. Alon, L. Babai, and A. Itai (1986), "A fast and simple randomized algorithm for the maximal independent set problem", <em>Journal of Algorithms</em> 7:4, 567-583.</p>

CC BY-SA 3.0
2018-03-26T02:31:36.783Z
2018-03-26T02:31:36.783Z
Ravi Boppana
<p>So I have this question which I can't seem to find a solution to:</p>

<blockquote>
  <p>Prove that if $X = (X_1, ... X_n)$ is $k$-wise uniform* and each $X_i$ is Boolean then $\left|\operatorname{Supp}(X)\right| \geq \mathbf B(\frac{k}{2}, n)$, where $\mathbf B(r, n)$ is the number of words of weight at most $r$.</p>
</blockquote>

<p>$*$ Where <em>$k$-wise uniform</em> means that, for each subset $S=\{i_1,\dots, i_s\}\subseteq [n]$ of size $s\leq k$, the distribution of $(X_{i_1},\dots,X_{i_s})$ is uniform.</p>

CC BY-SA 3.0
2018-03-23T10:29:18.610Z
Isn't the constant distribution $\delta_{1^n}$ (i.e., $X_i = 1$ a.s. for every $i\in[n]$) $k$-wise independent for every $1\leq k\leq n$?
Clement C.
CC BY-SA 3.0
2018-03-24T10:47:51.773Z
no, it is not even 1-wise independent, k-wise independent means that if we look at a subset (every subset) of length k it will look uniform.
Itaysason
CC BY-SA 3.0
2018-03-24T13:59:53.587Z
That's only one of the possible definitions. One of the standard ones defines it as "every subset of at most k of the variables is mutually independent". (With yours, pairwise and 2-wise do not coincide.)
Clement C.
CC BY-SA 3.0
2018-03-24T16:23:09.220Z
For this question, I recommend using the term "k-wise uniform" instead of "k-wise independent".
Ravi Boppana
CC BY-SA 3.0
2018-03-25T16:51:44.450Z
@RaviBoppana and Itaysason: I have edited the OP that way, to make it clear the assumption implies uniformity.
Clement C.
<pr.probability>
Support size lower bound for $k$-wise uniform distribution
Itaysason
# Support size lower bound for $k$-wise uniform distribution

(Asked by: username_0 on 2018-03-23)

So I have this question which I can't seem to find a solution to:

> Prove that if $X = (X\_1, ... X\_n)$ is $k$-wise uniform\* and each $X\_i$ is Boolean then $\left|\operatorname{Supp}(X)\right| \geq \mathbf B(\frac{k}{2}, n)$, where $\mathbf B(r, n)$ is the number of words of weight at most $r$.

$\*$ Where *$k$-wise uniform* means that, for each subset $S=\{i\_1,\dots, i\_s\}\subseteq [n]$ of size $s\leq k$, the distribution of $(X\_{i\_1},\dots,X\_{i\_s})$ is uniform.

**Tags:** pr.probability
> **Comments:**
> **username_1**: Isn't the constant distribution $\delta_{1^n}$ (i.e., $X_i = 1$ a.s. for every $i\in[n]$) $k$-wise independent for every $1\leq k\leq n$?  
> **username_0**: no, it is not even 1-wise independent, k-wise independent means that if we look at a subset (every subset) of length k it will look uniform.  
> **username_1**: That's only one of the possible definitions. One of the standard ones defines it as "every subset of at most k of the variables is mutually independent". (With yours, pairwise and 2-wise do not coincide.)  
> **username_2**: For this question, I recommend using the term "k-wise uniform" instead of "k-wise independent".  
> **username_1**: @RaviBoppana and Itaysason: I have edited the OP that way, to make it clear the assumption implies uniformity.  

---

## 1 answers

### Answer by username_2 on 2018-03-26. Score: 4

I believe this question was answered positively in three independent papers:

C. R. Rao (1947), "Factorial experiments derivable from combinatorial arrangements of arrays", *Journal of the Royal Statistical Society* 9:1, 128-139.

B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, and R. Smolensky (1985), "The bit extraction problem or t-resilient functions", *26th IEEE Symposium on Foundations of Computer Science*, 396-407.

N. Alon, L. Babai, and A. Itai (1986), "A fast and simple randomized algorithm for the maximal independent set problem", *Journal of Algorithms* 7:4, 567-583.


---

