Bernoulli Process - Randomness Extraction

Randomness Extraction

From any Bernoulli process one may derive a Bernoulli process with p = 1/2 by the von Neumann extractor, the earliest randomness extractor, which actually extracts uniform randomness.

Represent the observed process as a sequence of zeroes and ones, or bits, and group that input stream in non-overlapping pairs of successive bits, such as (11)(00)(10)... . Then for each pair,

• if the bits are equal, discard;
• if the bits are not equal, output the first bit.

This table summarizes the computation.

In the output stream 0 and 1 are equally likely, as 10 and 01 are equally likely in the original, both having probability pq = qp. This extraction of uniform randomness does not require the input trials to be independent, only uncorrelated. More generally, it works for any exchangeable sequence of bits: all sequences that are finite rearrangements are equally likely.

The Von Neumann extractor uses two input bits to produce either zero or one output bits, so the output is shorter than the input by a factor of at least 2. On average the computation discards proportion p2 + (1 − p)2 of the input pairs, or proportion p2 + q2, which is near one when p is near zero or one.

The discard of input pairs is at least proportion 1/2, the minimum which occurs where p = 1/2 for the original process. In that case the output stream is 1/4 the length of the input on average.