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
$k$-wise independent probability spaces
pr.probability;limited independence
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.