Optimal bounds for $k$-wise non-uniform random bits

Question

Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$.

What is the smallest sample space (or, equivalent, how many true independent random bits are needed) to generate $n$ $k$-wise independent Bernoullis with parameter $p\stackrel{\rm def}{=}1/2^t$?

This is not the same as this (related) question, since I don't want to generate uniform marginals in $\{1,\dots,2^t\}$ (which would be one way to simulate the $1/2^t$-biased coins, but one that feels very wasteful).

Alon, Babai, and Itai gave a time bound of $O(n^{k/2})$ for the case $t=1$. Karloff and Mansour [Theorem 3 of 2] showed that for $2^t = \frac{n}{k}$, a space of size $\Omega(n^k)$ was necessary.

Is the general trade-off as a function of $t,n,k$ known?

In particular, a simple construction would give an upper bound of $k(\log n + t)$ bits. However, and here my intuition may be completely off, I would expect it to decrease with $t$? For $k,n$ fixed, increasing $t$ leads to more biased bits, so less entropy overall.

I am not specifically looking for explicit constructions.

---

[1] Alon, Noga, László Babai, and Alon Itai. "A fast and simple randomized parallel algorithm for the maximal independent set problem." Journal of algorithms 7.4 (1986): 567-583.

[2] Karloff, Howard, and Yishay Mansour. "On construction ofk-wise independent random variables." Combinatorica 17.1 (1997): 91-107.

Answer 1

$$s = \Theta( k \cdot ( t + \log n ) )$$

As the question mentions, there is an upper bound of $s \le k\cdot\max\{t,\lceil \log_2 n \rceil\}$ bits for the seed length. Specifically, sample a random polynomial of degree $<k$ over a field of size $2^{\max\{t,\lceil \log_2 n \rceil\}}$, and evaluate it at $n$ points. This produces $k$-wise independent field elements which can easily be turned into bits with the appropriate bias.

There is also a trivial $s \ge k \cdot t$ lower bound: Just look at the first $k$ bits of the output. These will all be $1$ with probability $2^{-k \cdot t}$. Generating an event with precisely this probability requires a seed of $k\cdot t$ bits.

To characterize the required seed length up to constants, all that remains is to prove a lower bound of $s\ge \Omega(k \log n)$ bits in the setting of $t \le o(\log n)$. Assume for simplicity that $k$ is even.

Let $X$ denote the distribution in question and let $x$ be an arbitrary point in its support. We have $\Pr[X=x]\ge 2^{-s}$ where $s$ is the seed length. Thus an upper bound on $\Pr[X=x]$ entails a lower bound on the seed length.

Define $Y = \sum_{i=1}^n \mathbb{I}[X_i \ne x_i]$. Then $X=x \iff Y=0$ and $\mu:=\mathbb{E}[Y] \ge n \cdot 2^{-t}$. Thus, by Markov's inequality and a Bernstein moment bound (e.g., Eq. 10 in SSS06 or this answer), $$2^{-s} \le \Pr[X=x] \le \Pr[|Y-\mu|\ge \mu] \le \frac{\mathbb{E}[(Y-\mu)^k]}{\mu^k} \le \frac{O(k\mu)^{k/2}}{\mu^k} = O\left(\frac{k}{\mu}\right)^{k/2} \le O\left(\frac{k}{n \cdot 2^{-t}}\right)^{k/2}.$$ This rearranges to $s \ge \frac12 k \cdot \left( \log_2 n - t -\log_2 k - O(1) \right)$. If $t=o(\log n)$ and $k=n^{o(1)}$, this is the desired lower bound.

In summary,

$$k \cdot \max\{t,\lceil \log_2 n \rceil\} \ge s \ge k \cdot \max\left\{t, \frac12 \cdot \left( \log_2 n - \log_2 k - t - O(1) \right) \right\}.$$

The only room for improvement on this bound is in the constants (or the regime where replacing $n$ with $n/k$ makes a difference). However, if we only need a distribution that approximates the requirements, then I believe we can achieve better seed length (depending on the nature of the allowed approximation).