2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Mar 11 at 8:58
  • $\begingroup$ 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. $\endgroup$ – Thomas Mar 11 at 9:17
  • $\begingroup$ @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). $\endgroup$ – Clement C. Mar 11 at 14:57
  • $\begingroup$ 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? $\endgroup$ – Thomas Mar 11 at 15:54
  • 1
    $\begingroup$ @Thomas I beg to differ. Phrased as the size of the sample space, I am asking about the constant in the exponent. :) $\endgroup$ – Clement C. Mar 11 at 16:55
2
$\begingroup$

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

$\endgroup$

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.