In extractor theory, a randomness merger is a function which extracts randomness out of a set of random variables, provided that at least one of them is uniformly random. Its name stems from the fact that it can be seen as a procedure which "merges" all the variables into one, preserving at least some of the entropy contained in the uniformly random variable.
Contents
Mergers are currently used in order to explicitly construct randomness extractors.
Intuition and definition
Consider a set of
The job of the merger is to output a new random variable, also distributed over
Definition (merger):
A function
In other words, by using a small uniform seed of length
Reminder: There are several notions of measuring the randomness of a distribution; the min-entropy of a random variable
Parameters
There are three parameters to optimize when building mergers:
- The output's min-entropy
m should be as high as possible, for then more bits can be extracted from it. -
ε should be as small as possible, for then after applying an extractor to the merger's output, the result will be closer to uniform. - The seed length
d should be as small as possible, for then the merger requires fewer initial truly random bits to work.
Explicit constructions for mergers are known with relatively good parameters. For example, Dvir and Wigderson's construction gives: For every
-
m = ( 1 − α ) n , -
d = O ( log ( n ) + log ( k ) ) , -
ε = O ( 1 n ⋅ k ) .
The proof is constructive and allows building such a merger in polynomial time in the given parameters.
Usage
It is possible to use mergers in order to produce randomness extractors with good parameters. Recall that an extractor is a function which takes a random variable that has high min-entropy, and returns a smaller random variable, but one that is close to uniform. An arbitrary min-entropy extractor can be obtained using the following merger-based scheme:
The essence of the scheme above is to use the merger in order to transform a string with arbitrary min-entropy into a smaller string, while not losing a lot of min-entropy in the process. This new string has very high min-entropy compared to its length, and it's then possible to use older, known, extractors which only work for those type of strings.