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$?


  • $\begingroup$ 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? $\endgroup$ – Thomas Apr 3 '14 at 6:15
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.