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

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.

• Would you be satisfied with a distribution that is approximately k-wise independent in some sense? My intuition is that, since there is still a small probability of getting a lot of ones, the seed length does not decrease with the bias. Mar 11, 2019 at 8:58
• To make my intuition more concrete: For $k=n$, I need seed length $tn$, becase I must output all ones with probability $2^{-tn}$. But, if I allow an approximation in, say, TV distance, then I can get arbitrarily close to the entropy. So bias hurts for exact but helps for approximate. Mar 11, 2019 at 9:17
• @Thomas I see your point. Still, I'd rather understand the behavior for exact first, before adding the extra layer of approximate $k$-wise independence to this... (Actually, something related to $k$-wise independence is also good for me, and then the bias does seem to help, but I don't know what name it has: namely, preserving the $k$-wise marginals of the distribution where one partitions $[n]$ u.a.r. in $n/2^t$ parts of size $2^t$. But that'd be another question, I reckon). Mar 11, 2019 at 14:57
• I suspect $k(t+\log n)$ is tight for the exact case. There is a lower bound of $kt$ on the seed length by looking at the first $k$ bits and applying the argument from my previous comment. Are you interested in the $t=o(\log n)$ regime? Mar 11, 2019 at 15:54
• @Thomas I beg to differ. Phrased as the size of the sample space, I am asking about the constant in the exponent. :) Mar 11, 2019 at 16:55

$$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 $$ 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).