ON CONSTRUCTION OF K-WISE INDEPENDENT RANDOM-VARIABLES

A 0-1 probability space is a probability space (Omega, 2(Omega), P), w here the sample space Omega subset of or equal to {0, 1}(n) for some n . A probability space is k-wise independent if, when Y-i is defined to be the ith coordinate of the random n-vector, then any subset of k of the Y-i's is (mutually) independent, and it is said to be a probabili ty space for p(1), p(2), ..., p(n) if P[Y-i = 1] = p(i). We study cons tructions of k-wise independent 0-1 probability spaces in which the p( i)'s are arbitrary. It was known that for any p(1), p(2), ..., p(n), a k-wise independent probability space of size m(n, k) = ((k) (n)) + (( k-1) (n)) + ((k-2) (n)) + ... + ((0) (n)) always exists. We prove that for some p(1), p(2), ..., p(n) is an element of [0, 1], m(n, k) is a lower bound on the size of any Ic-wise independent 0-1 probability spa ce. For each fixed k, we prove that every k-wise independent 0-1 proba bility space when each p(i) = k/n has size Omega(n(k)). For a very lar ge degree of independence - k = [alpha n], for alpha > 1/2 - and all p (i) = 1/2, we prove a lower bound on the size of 2(n)(1 - 1/2 alpha). We also give explicit constructions of k-wise independent 0-1 probabil ity spaces.