<p>Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$. </p>

<p>In contrast, <a href="https://en.wikipedia.org/wiki/Small-bias_sample_space#Constructions_of_small_epsilon-biased_sets" rel="nofollow noreferrer">the best worst-case $\varepsilon$-biased spaces</a> on $n$ bits have size $\tilde\Theta(n/\varepsilon^2)$. So you save a factor of about $n/\varepsilon$ by going from worst-case to average-case.</p>

<p>Unfortunately, as you will see, the construction is a bit silly. This explains why this primitive has not been studied.</p>

<p>Let $m=\lceil \log_2(1/\varepsilon) \rceil$. Let $S = \{0,1\}^m \times \{0\}^{n-m} \subset \{0,1\}^n$. That is, a random $x \in S$ consists of $m$ uniformly random bits, followed by $n-m$ zeros.</p>

<p>We have $|S| = 2^m = 2^{\lceil \log_2 (1/\varepsilon) \rceil} \ge 2^{\log_2(1/\varepsilon)} = \frac{1}{\varepsilon}$ and, similarly, $|S| 
 &lt; 2^{\log_2(1/\varepsilon)+1} = \frac{2}{\varepsilon}$.</p>

<p>Now let's analyse the average bias of $S$: $$\underset{\alpha \in \{0,1\}^n}{\mathbb{E}}\left[\left|\underset{x \in S}{\mathbb{E}}\left[(-1)^{\langle x , \alpha \rangle}\right]\right|\right] = \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{E}}\left[\left|\underset{x_0 \in \{0,1\}^m}{\mathbb{E}}\left[(-1)^{\langle x_0 , \alpha_0 \rangle}\right]\right|\right] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\le \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha_0 = (0,0,\cdots,0) \right] \cdot 1 + \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha_0 \ne (0,0,\cdots,0) \right] \cdot 0\\= 2^{-m} + 0 \le \varepsilon~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$
The first line uses the fact that only the first $m$ bits are relevant and the second line uses the fact that $x_0$ is uniform.</p>

<p>Furthermore, we can show that $|S| \ge 1/\varepsilon$ is necessary -- a nearly matching lower bound. See <a href="https://cstheory.stackexchange.com/a/19491/2022">this answer</a> for the proof idea.</p>

CC BY-SA 4.0
2018-07-20T18:27:48.527Z
2018-07-22T00:29:11.807Z
2018-07-22T00:29:11.807Z
Thomas Steinke
<p>Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that <em>for every non-zero linear test</em> $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}_{x \in S} [ (-1)^{&lt;x,\alpha&gt;} ] | \leq \epsilon$$
is small. Distributions over such subsets $\epsilon$-fool <em>all</em> linear tests, so if we can make $|S|$ as small as possible, we have a good deranomization primitive.</p>

<p>Is an average case analogue of such a construction studied anywhere, and is it useful? More precisely, suppose we take a subset $S \subset \{0,1\}^n$ such that 
$$\mathbb{E}_{\alpha}| \mathbb{E}_{x \in S} [ (-1)^{&lt;x,\alpha&gt;} ] | \leq \epsilon$$
This is, of course, weaker than $\epsilon$-fooling all linear tests. My question is: is there a natural approach to constructing such a set $S$ of small size?</p>

<p>A method used to construct $\epsilon$-bias sets is to interpret it as the vectors of the parity-check matrix of an $\epsilon$-balanced linear code, and so the aim becomes to design such a code with as high rate as possible. Would such an approach work for the average-case too? I am unclear on the correspondence though. </p>

<cc.complexity-theory><co.combinatorics><boolean-functions><fourier-analysis><pseudorandomness>
Average-case analogue of Small-bias Spaces
BharatRam
# Average-case analogue of Small-bias Spaces

(Asked by: username_0 on 2018-07-20)

Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that *for every non-zero linear test* $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}\_{x \in S} [ (-1)^{} ] | \leq \epsilon$$
is small. Distributions over such subsets $\epsilon$-fool *all* linear tests, so if we can make $|S|$ as small as possible, we have a good deranomization primitive.

Is an average case analogue of such a construction studied anywhere, and is it useful? More precisely, suppose we take a subset $S \subset \{0,1\}^n$ such that
$$\mathbb{E}\_{\alpha}| \mathbb{E}\_{x \in S} [ (-1)^{} ] | \leq \epsilon$$
This is, of course, weaker than $\epsilon$-fooling all linear tests. My question is: is there a natural approach to constructing such a set $S$ of small size?

A method used to construct $\epsilon$-bias sets is to interpret it as the vectors of the parity-check matrix of an $\epsilon$-balanced linear code, and so the aim becomes to design such a code with as high rate as possible. Would such an approach work for the average-case too? I am unclear on the correspondence though.

**Tags:** cc.complexity-theory, co.combinatorics, boolean-functions, fourier-analysis, pseudorandomness


---

## 1 answers

### Answer by username_1 on 2018-07-20. Score: 8

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$.

In contrast, [the best worst-case $\varepsilon$-biased spaces](https://en.wikipedia.org/wiki/Small-bias_sample_space#Constructions_of_small_epsilon-biased_sets) on $n$ bits have size $\tilde\Theta(n/\varepsilon^2)$. So you save a factor of about $n/\varepsilon$ by going from worst-case to average-case.

Unfortunately, as you will see, the construction is a bit silly. This explains why this primitive has not been studied.

Let $m=\lceil \log\_2(1/\varepsilon) \rceil$. Let $S = \{0,1\}^m \times \{0\}^{n-m} \subset \{0,1\}^n$. That is, a random $x \in S$ consists of $m$ uniformly random bits, followed by $n-m$ zeros.

We have $|S| = 2^m = 2^{\lceil \log\_2 (1/\varepsilon) \rceil} \ge 2^{\log\_2(1/\varepsilon)} = \frac{1}{\varepsilon}$ and, similarly, $|S|
< 2^{\log\_2(1/\varepsilon)+1} = \frac{2}{\varepsilon}$.

Now let's analyse the average bias of $S$: $$\underset{\alpha \in \{0,1\}^n}{\mathbb{E}}\left[\left|\underset{x \in S}{\mathbb{E}}\left[(-1)^{\langle x , \alpha \rangle}\right]\right|\right] = \underset{\alpha\_0 \in \{0,1\}^m}{\mathbb{E}}\left[\left|\underset{x\_0 \in \{0,1\}^m}{\mathbb{E}}\left[(-1)^{\langle x\_0 , \alpha\_0 \rangle}\right]\right|\right] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\le \underset{\alpha\_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha\_0 = (0,0,\cdots,0) \right] \cdot 1 + \underset{\alpha\_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha\_0 \ne (0,0,\cdots,0) \right] \cdot 0\\= 2^{-m} + 0 \le \varepsilon~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$
The first line uses the fact that only the first $m$ bits are relevant and the second line uses the fact that $x\_0$ is uniform.

Furthermore, we can show that $|S| \ge 1/\varepsilon$ is necessary -- a nearly matching lower bound. See [this answer](https://cstheory.stackexchange.com/a/19491/2022) for the proof idea.


---

