Von Neumann extractor
The Von Neumann extractor is a simple example of a randomness extractor: given a stream of “imperfectly random” bits, it extracts the entropy, and outputs a “perfectly random” stream.
As input, the Von Neumann extractor expects a stream of independent (uncorrelated) bits, i.e. the result of a Bernoulli process, where each bit is with probability , and with probability . Crucially, does not need to be ; there may be a bias.
The extractor will output a uniformly random stream with . Given input bits , it achieves this by looking at the bits in pairs , , etc. Then:
- If , it discards both bits.
- If , it keeps the first bit , and discards .
Evidently, the first case occurs with the following probabilities:
Meanwhile, the second case occurs with probabilities given by:
Crucially, they are equal; . Therefore, if the extractor encounters an input pair satisfying , the first bit is or with a 50-50 probability, regardless of . Since the extractor only keeps those bits, its output is guaranteed to be “perfectly random”.
Clearly, because it discards many of the bits, the output stream will have a length . The exact value of is as follows, where is the probability that we keep a bit, and the factor is due to us discarding half of the pair even in that case:
The key assumption that allows the Von Neumann extractor to work is that there is no correlation at all between the bits. In practice, this may be difficult to achieve, in which case a more complex randomness extraction scheme is needed.
- J.B. Brask, Quantum information: lecture notes, 2021, unpublished.