On construction of \(k\)-wise independent random variables (Q1375059)

The paper is concerned with probability spaces consisting of \(n\)-long bit strings in which any subset of \(k\) bits in a random string is mutually independent and for each \(i = 1, \ldots, n\), the probability that the \(i\)-th bit in a random string is 1 is equal to \(p_i\). In particular, the paper is investigating the lower bounds for the size of such a probability space. It is shown that there exists \(p_1, \ldots, p_n \in (0,1)\) such that the size of any space with the above properties is \({n \choose k} + {n \choose k-1} \ldots {n \choose 0}\) (and this matches the upper bound). When all \(p_i\) are equal to \(n/k\), the size of any such space is \(\Omega(n^k)\), for fixed \(k\). If \(k = \lfloor \alpha n \rfloor\) for \(1/2 < \alpha \leq 1\), the size of any such space is \(2^n(1 - 1/(2\alpha))\).