Randomness merger

Summarize Timeline Top Qs Fact Check

Consider a set of ${\displaystyle k}$ random variables, ${\displaystyle X_{1},\ldots ,X_{k}}$, each distributed over ${\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 ${\displaystyle n}$ bits of entropy.

The job of the merger is to output a new random variable, also distributed over ${\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 ${\displaystyle X_{1}=X_{2}}$, and both of them are uniformly distributed, then the method would not work.

Definition (merger):

A function ${\displaystyle M:(\{0,1\}^{n})^{k}\times \{0,1\}^{d}\rightarrow \{0,1\}^{n}}$ is called an ${\displaystyle (m,\varepsilon )}$-merger if for every set of random variables ${\displaystyle (X_{1},\ldots ,X_{k})}$ distributed over ${\displaystyle \{0,1\}^{n}}$, at least one of which is uniform, the distribution of ${\displaystyle Z=M(X_{1},\ldots ,X_{k},U_{d})}$ has smooth min-entropy ${\displaystyle H_{\infty }^{\varepsilon }(Z)\geq m}$. The variable ${\displaystyle U_{d}}$ denotes the uniform distribution over ${\displaystyle d}$ bits, and represents a truly random seed.

In other words, by using a small uniform seed of length ${\displaystyle d}$, the merger returns a string which is ${\displaystyle \varepsilon }$-close to having at least ${\displaystyle m}$ min-entropy; this means that its statistical distance from a string with ${\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 ${\displaystyle Z}$ is defined as the largest ${\displaystyle k}$ such that the most probable value of ${\displaystyle Z}$ occurs with probability no more than ${\displaystyle 2^{-k}}$. The min-entropy of a string is an upper bound to the amount of randomness that can be extracted from it. ^[1]

There are three parameters to optimize when building mergers:

1. The output's min-entropy ${\displaystyle m}$ should be as high as possible, for then more bits can be extracted from it.
2. ${\displaystyle \varepsilon }$ should be as small as possible, for then after applying an extractor to the merger's output, the result will be closer to uniform.
3. The seed length ${\displaystyle 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:^[2] For every ${\displaystyle \alpha >0}$ and integer ${\displaystyle n}$, if ${\displaystyle k\leq 2^{o(n)}}$, there exists an explicit ${\displaystyle (m,\varepsilon )}$-merger ${\displaystyle M:(\{0,1\}^{n})^{k}\times \{0,1\}^{d}\rightarrow \{0,1\}^{n}}$ such that:

1. ${\displaystyle m=(1-\alpha )n,}$
2. ${\displaystyle d=O(\log(n)+\log(k)),}$
3. ${\displaystyle \varepsilon =O\left({\frac {1}{n\cdot k}}\right).}$

The proof is constructive and allows building such a merger in polynomial time in the given parameters.