$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 &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}
$$

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 &gt; 1$?

Thanks
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.