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. Mergers are currently used in order to explicitly construct randomness extractors.
Intuition and definition Consider a set of k {\displaystyle k} random variables, X 1 , … , X k {\displaystyle X_{1},\ldots ,X_{k}} , each distributed over { 0 , 1 } n {\displaystyle \{0,1\}^{n}} at least one of which is uniformly random; but it is not known which one. Furthermore, the variables may be arbitrarily correlated: they may be functions of one another, they may be constant, and so on. However, since at least one of them is uniform, the set as a whole contains at least n {\displaystyle n} bits of entropy. The job of the merger is to output a new random variable, also distributed over { 0 , 1 } n {\displaystyle \{0,1\}^{n}} , that retains as much of that entropy as possible. Ideally, if it were known which of the variables is uniform, it could be used as the output, but that information is not known. The idea behind mergers is that by using a small additional random seed, it is possible to get a good result even without knowing which one is the uniform variable. A naive idea would be to take the xor of all the variables. If one of them is uniformly distributed and independent of the other variables, then the output would be uniform. However, if suppose X 1 = X 2 {\displaystyle X_{1}=X_{2}} , and both of them are uniformly distributed, then the method would not work. Definition (merger): A function M : ( { 0 , 1 } n ) k × { 0 , 1 } d → { 0 , 1 } n {\displaystyle M:(\{0,1\}^{n})^{k}\times \{0,1\}^{d}\rightarrow \{0,1\}^{n}} is called an ( m , ε ) {\displaystyle (m,\varepsilon )} -merger if for every set of random variables ( X 1 , … , X k ) {\displaystyle (X_{1},\ldots ,X_{k})} distributed over { 0 , 1 } n {\displaystyle \{0,1\}^{n}} , at least one of which is uniform, the distribution of Z = M ( X 1 , … , X k , U d ) {\displaystyle Z=M(X_{1},\ldots ,X_{k},U_{d})} has smooth min-entropy H ∞ ε ( Z ) ≥ m {\displaystyle H_{\infty }^{\varepsilon }(Z)\geq m} . The variable U d {\displaystyle U_{d}} denotes the uniform distribution over d {\displaystyle d} bits, and represents a truly random seed. In other words, by using a small uniform seed of length d {\displaystyle d} , the merger returns a string which is ε {\displaystyle \varepsilon } -close to having at least m {\displaystyle m} min-entropy; this means that its statistical distance from a string with m {\displaystyle m} min-entropy is no larger than ε {\displaystyle \varepsilon } . Reminder: There are several notions of measuring the randomness of a distribution; the min-entropy of a random variable Z {\displaystyle Z} is defined as the largest k {\displaystyle k} such that the most probable value of Z {\displaystyle Z} occurs with probability no more than 2 − k {\displaystyle 2^{-k}} . The min-entropy of a string is an upper bound to the amount of randomness that can be extracted from it.
Parameters There are three parameters to optimize when building mergers:
The output's min-entropy m {\displaystyle m} should be as high as possible, for then more bits can be extracted from it.
… excerpt ends here. Continue reading the full article.
