# $k$-wise independent probability spaces

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

• 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 Apr 3 '14 at 6:15
• There is a good survey on the topic by Salil Vadhan; it is available online: people.seas.harvard.edu/~salil/pseudorandomness . Chapter 3 covers $k$-wise independent random variables. – Yury Apr 3 '14 at 16:13

For arbitrary $b$, Alon, Babai and Itai 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 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) mentioned by Thomas as a comment.