<blockquote>
  <p><span class="math-container">$$s = \Theta( k \cdot ( t + \log n ) )$$</span></p>
</blockquote>

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

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

<p>To characterize the required seed length up to constants, all that remains is to prove a lower bound of <span class="math-container">$s\ge \Omega(k \log n)$</span> bits in the setting of <span class="math-container">$t \le o(\log n)$</span>. Assume for simplicity that <span class="math-container">$k$</span> is even.</p>

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

<p>Define <span class="math-container">$Y = \sum_{i=1}^n \mathbb{I}[X_i \ne x_i]$</span>. Then <span class="math-container">$X=x \iff Y=0$</span> and <span class="math-container">$\mu:=\mathbb{E}[Y] \ge n \cdot 2^{-t}$</span>. Thus, by Markov's inequality and a Bernstein moment bound (e.g., Eq. 10 in <a href="http://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf" rel="nofollow noreferrer">SSS06</a> or <a href="https://mathoverflow.net/a/147239/54233">this answer</a>), <span class="math-container">$$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}.$$</span>
This rearranges to <span class="math-container">$s \ge \frac12 k \cdot \left( \log_2 n - t -\log_2 k - O(1) \right)$</span>. If <span class="math-container">$t=o(\log n)$</span> and <span class="math-container">$k=n^{o(1)}$</span>, this is the desired lower bound.</p>

<p>In summary,</p>

<blockquote>
  <p><span class="math-container">$$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\}.$$</span></p>
</blockquote>

<p>The only room for improvement on this bound is in the constants (or the regime where replacing <span class="math-container">$n$</span> with <span class="math-container">$n/k$</span> 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). </p>

CC BY-SA 4.0
2019-03-11T19:29:14.167Z
2019-03-11T21:56:56.930Z
2019-03-11T21:56:56.930Z
Thomas Steinke
<p>Let <span class="math-container">$k\geq 2$</span> be a constant (in my case, <span class="math-container">$k=4$</span>), and <span class="math-container">$n,t \geq 0$</span> be integers such that <span class="math-container">$2^t \leq n$</span>.</p>

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

<p>This is not the same as this (related) <a href="https://cstheory.stackexchange.com/questions/21898/k-wise-independent-probability-spaces">question</a>, since I don't want to generate uniform marginals in <span class="math-container">$\{1,\dots,2^t\}$</span> <em>(which would be one way to simulate the <span class="math-container">$1/2^t$</span>-biased coins, but one that feels very wasteful)</em>.</p>

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

<blockquote>
  <p>Is the general trade-off as a function of <span class="math-container">$t,n,k$</span> known?</p>
</blockquote>

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

<p><em>I am not specifically looking for explicit constructions.</em></p>

<hr>

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

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

CC BY-SA 4.0
2019-03-11T08:58:38.083Z
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.
Thomas Steinke
CC BY-SA 4.0
2019-03-11T09:17:45.177Z
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.
Thomas Steinke
CC BY-SA 4.0
2019-03-11T14:57:35.250Z
@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).
Clement C.
CC BY-SA 4.0
2019-03-11T15:54:18.453Z
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?
Thomas Steinke
CC BY-SA 4.0
2019-03-11T16:12:36.070Z
@Thomas I reckon it then boils down to the constant in front of the $k \log n$ and $kt$, but yes... I'd be interested in the full range.
Clement C.
CC BY-SA 4.0
2019-03-11T16:54:09.513Z
Cstheory.se is the wrong place to ask about constants. :p
Thomas Steinke
CC BY-SA 4.0
2019-03-11T16:55:01.043Z
@Thomas I beg to differ. Phrased as the size of the sample space, I am asking about the constant *in the exponent*. :)
Clement C.
<reference-request><randomness><derandomization><k-wise-independence>
Optimal bounds for $k$-wise non-uniform random bits
Clement C.
# Optimal bounds for $k$-wise non-uniform random bits

(Asked by: username_0 on 2019-03-11)

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](https://cstheory.stackexchange.com/questions/21898/k-wise-independent-probability-spaces), 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.

**Tags:** reference-request, randomness, derandomization, k-wise-independence

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: @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).  
> **username_1**: 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?  
> **username_0**: @Thomas I reckon it then boils down to the constant in front of the $k \log n$ and $kt$, but yes... I'd be interested in the full range.  
> **username_1**: Cstheory.se is the wrong place to ask about constants. :p  
> **username_0**: @Thomas I beg to differ. Phrased as the size of the sample space, I am asking about the constant *in the exponent*. :)  

---

## 1 answers

### Answer by username_1 on 2019-03-11. Score: 3 | Accepted answer

> $$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](http://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf) or [this answer](https://mathoverflow.net/a/147239/54233)), $$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).


---

