<p>For arbitrary $b$, <a href="http://www.sciencedirect.com/science/article/pii/0196677486900192">Alon, Babai and Itai</a> showed a lower bound on the probability space size of $m(n,\lfloor k/2 \rfloor)$ where
$$ m(n,k) = \sum\limits_{i=0}^k \binom{n}{i}$$</p>

<p>which is $\Omega(n^{k/2})$ for constant $k$.</p>

<p>They also gave a construction of size $O(n^{k/2})$ in the case of $b = 1$.</p>

<p>For $b=1$ there is a paper by <a href="http://dl.acm.org/citation.cfm?id=195409">Karloff and Mansour</a> which shows lower bounds and upper bounds for arbitrary probabilities, i.e., for $p_1,\ldots,p_n$ with $p_i = P(Y_i = 1)$. E.g., there are probabilities $p_1,\ldots,p_n$ such that the probability space size is at least $m(n,k)$. They also say that $m(n,k)$ is also a upper bound for arbitrary probabilities.</p>

<p>I don't known any construction with a better upper bound than $O(n^k)$ which is given by the construction (see <a href="http://projecteuclid.org/euclid.aop/1176996762">here</a>) mentioned by Thomas as a comment.</p>

CC BY-SA 3.0
2014-04-03T09:54:24.387Z
2014-04-03T09:54:24.387Z
Marc Bury
<p>I have been having a great deal of difficulty finding a reference that gives simple and straightforward explanation of the following:</p>

<p>Suppose we have $n$ random variables $Y_1, \dots, Y_n$, each of $b$-bits long. (I.e. with values in $\{0, \dots, 2^b-1 \}$). We want a probability space where each $Y_i$ is unbiased (takes on each value with probability exactly $2^{-b}$), and has $k$-independence. That is, for any $i_1 &lt; \dots &lt; i_k$ and any $y_1, \dots, y_k$ we have
$$
P(Y_{i_1} = y_1 \wedge \dots \wedge Y_{i_k} = y_k) = 2^{-k b}
$$</p>

<p>When $b = 1$ you can always get a probability space of size $n^{k}$ and sometimes you can get $n^{k/2}$ -- is there any clear statement about when these are possible?</p>

<p>Can someone point me to references about what happens when $b &gt; 1$?</p>

<p>Thanks</p>

CC BY-SA 3.0
2014-04-03T06:15:58.543Z
I'm not sure what the reference is, but the construction I know is: choose a random polynomial over $GF(2^{\max\{b,\lceil \log_2 n \rceil\}})$ of degree at most $k-1$ and evaluate it at $n$ points. This gives a sample space of size $\max\{2^{kb}, n^k\}$. Is this the kind of result you're looking for?
Thomas Steinke
CC BY-SA 3.0
2014-04-03T16:13:03.537Z
There is a good survey on the topic by Salil Vadhan; it is available online: http://people.seas.harvard.edu/~salil/pseudorandomness/ . Chapter 3 covers $k$-wise independent random variables.
Yury
<pr.probability><limited-independence>
$k$-wise independent probability spaces
David Harris
# $k$-wise independent probability spaces

(Asked by: username_0 on 2014-04-02)

I have been having a great deal of difficulty finding a reference that gives simple and straightforward explanation of the following:

Suppose we have $n$ random variables $Y\_1, \dots, Y\_n$, each of $b$-bits long. (I.e. with values in $\{0, \dots, 2^b-1 \}$). We want a probability space where each $Y\_i$ is unbiased (takes on each value with probability exactly $2^{-b}$), and has $k$-independence. That is, for any $i\_1 < \dots < i\_k$ and any $y\_1, \dots, y\_k$ we have
$$
P(Y\_{i\_1} = y\_1 \wedge \dots \wedge Y\_{i\_k} = y\_k) = 2^{-k b}
$$

When $b = 1$ you can always get a probability space of size $n^{k}$ and sometimes you can get $n^{k/2}$ -- is there any clear statement about when these are possible?

Can someone point me to references about what happens when $b > 1$?

Thanks

**Tags:** pr.probability, limited-independence

> **Comments:**
> **username_1**: I'm not sure what the reference is, but the construction I know is: choose a random polynomial over $GF(2^{\max\{b,\lceil \log_2 n \rceil\}})$ of degree at most $k-1$ and evaluate it at $n$ points. This gives a sample space of size $\max\{2^{kb}, n^k\}$. Is this the kind of result you're looking for?  
> **username_2**: There is a good survey on the topic by Salil Vadhan; it is available online: http://people.seas.harvard.edu/~salil/pseudorandomness/ . Chapter 3 covers $k$-wise independent random variables.  

---

## 1 answers

### Answer by username_3 on 2014-04-03. Score: 5 | Accepted answer

For arbitrary $b$, [Alon, Babai and Itai](http://www.sciencedirect.com/science/article/pii/0196677486900192) showed a lower bound on the probability space size of $m(n,\lfloor k/2 \rfloor)$ where
$$ m(n,k) = \sum\limits\_{i=0}^k \binom{n}{i}$$

which is $\Omega(n^{k/2})$ for constant $k$.

They also gave a construction of size $O(n^{k/2})$ in the case of $b = 1$.

For $b=1$ there is a paper by [Karloff and Mansour](http://dl.acm.org/citation.cfm?id=195409) which shows lower bounds and upper bounds for arbitrary probabilities, i.e., for $p\_1,\ldots,p\_n$ with $p\_i = P(Y\_i = 1)$. E.g., there are probabilities $p\_1,\ldots,p\_n$ such that the probability space size is at least $m(n,k)$. They also say that $m(n,k)$ is also a upper bound for arbitrary probabilities.

I don't known any construction with a better upper bound than $O(n^k)$ which is given by the construction (see [here](http://projecteuclid.org/euclid.aop/1176996762)) mentioned by Thomas as a comment.


---

