In theoretical computer science, a small-bias sample space (also known as \epsilon-biased sample space, \epsilon-biased generator, or small-bias probability space) is a probability distribution that fools parity functions. In other words, no parity function can distinguish between a small-bias sample space and the uniform distribution with high probability, and hence, small-bias sample spaces naturally give rise to pseudorandom generators for parity functions. The main useful property of small-bias sample spaces is that they need far fewer truly random bits than the uniform distribution to fool parities. Efficient constructions of small-bias sample spaces have found many applications in computer science, some of which are derandomization, error-correcting codes, and probabilistically checkable proofs. The connection with error-correcting codes is in fact very strong since \epsilon-biased sample spaces are equivalent to \epsilon-balanced error-correcting codes.

Definition

Bias

Let X be a probability distribution over {0,1}^n. The bias of X with respect to a set of indices is defined as where the sum is taken over \mathbb F_2, the finite field with two elements. In other words, the sum equals 0 if the number of ones in the sample at the positions defined by I is even, and otherwise, the sum equals 1. For I=\emptyset, the empty sum is defined to be zero, and hence.

ϵ-biased sample space

A probability distribution X over {0,1}^n is called an \epsilon-biased sample space if holds for all non-empty subsets.

ϵ-biased set

An \epsilon-biased sample space X that is generated by picking a uniform element from a multiset is called \epsilon-biased set. The size s of an \epsilon-biased set X is the size of the multiset that generates the sample space.

ϵ-biased generator

An \epsilon-biased generator is a function that maps strings of length \ell to strings of length n such that the multiset is an \epsilon-biased set. The seed length of the generator is the number \ell and is related to the size of the \epsilon-biased set X_G via the equation s=2^\ell.

Connection with epsilon-balanced error-correcting codes

There is a close connection between \epsilon-biased sets and \epsilon-balanced linear error-correcting codes. A linear code of message length n and block length s is \epsilon-balanced if the Hamming weight of every nonzero codeword C(x) is between and. Since C is a linear code, its generator matrix is an (n\times s)-matrix A over \mathbb F_2 with. Then it holds that a multiset is \epsilon-biased if and only if the linear code C_X, whose columns are exactly elements of X, is \epsilon-balanced.

Constructions of small epsilon-biased sets

Usually the goal is to find \epsilon-biased sets that have a small size s relative to the parameters n and \epsilon. This is because a smaller size s means that the amount of randomness needed to pick a random element from the set is smaller, and so the set can be used to fool parities using few random bits.

Theoretical bounds

The probabilistic method gives a non-explicit construction that achieves size. The construction is non-explicit in the sense that finding the \epsilon-biased set requires a lot of true randomness, which does not help towards the goal of reducing the overall randomness. However, this non-explicit construction is useful because it shows that these efficient codes exist. On the other hand, the best known lower bound for the size of \epsilon-biased sets is, that is, in order for a set to be \epsilon-biased, it must be at least that big.

Explicit constructions

There are many explicit, i.e., deterministic constructions of \epsilon-biased sets with various parameter settings: These bounds are mutually incomparable. In particular, none of these constructions yields the smallest \epsilon-biased sets for all settings of \epsilon and n.

Application: almost k-wise independence

An important application of small-bias sets lies in the construction of almost k-wise independent sample spaces.

k-wise independent spaces

A random variable Y over {0,1}^n is a k-wise independent space if, for all index sets of size k, the marginal distribution Y|_I is exactly equal to the uniform distribution over {0,1}^k. That is, for all such I and all strings, the distribution Y satisfies.

Constructions and bounds

k-wise independent spaces are fairly well understood.

Joffe's construction

constructs a k-wise independent space Y over the finite field with some prime number n>k of elements, i.e., Y is a distribution over. The initial k marginals of the distribution are drawn independently and uniformly at random: For each i with, the marginal distribution of Y_i is then defined as where the calculation is done in \mathbb F_n. proves that the distribution Y constructed in this way is k-wise independent as a distribution over. The distribution Y is uniform on its support, and hence, the support of Y forms a k-wise independent set. It contains all n^k strings in that have been extended to strings of length n using the deterministic rule above.

Almost k-wise independent spaces

A random variable Y over {0,1}^n is a \delta-almost k-wise independent space if, for all index sets of size k, the restricted distribution Y|_I and the uniform distribution U_k on {0,1}^k are \delta-close in 1-norm, i.e.,.

Constructions

give a general framework for combining small k-wise independent spaces with small \epsilon-biased spaces to obtain \delta-almost k-wise independent spaces of even smaller size. In particular, let be a linear mapping that generates a k-wise independent space and let be a generator of an \epsilon-biased set over {0,1}^h. That is, when given a uniformly random input, the output of G_1 is a k-wise independent space, and the output of G_2 is \epsilon-biased. Then with is a generator of an \delta-almost k-wise independent space, where. As mentioned above, construct a generator G_1 with, and construct a generator G_2 with. Hence, the concatenation G of G_1 and G_2 has seed length. In order for G to yield a \delta-almost k-wise independent space, we need to set, which leads to a seed length of and a sample space of total size.