Editing Bernoulli process (section)

=== Basic von Neumann extractor ===
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.
{|
! input !! output
|-
| 00 || discard
|-
| 01 || 0
|-
| 10 || 1
|-
| 11 || discard
|}
For example, an input stream of eight bits ''10011011'' would by grouped into pairs as ''(10)(01)(10)(11)''. Then, according to the table above, these pairs are translated into the output of the procedure:
''(1)(0)(1)()'' (=''101'').

In the output stream 0 and 1 are equally likely, as 10 and 01 are equally likely in the original, both having probability ''p''(1−''p'')&nbsp;=&nbsp;(1−''p'')''p''. This extraction of uniform randomness does not require the input trials to be independent, only [[uncorrelated]]. More generally, it works for any [[exchangeable random variables|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&nbsp;2. On average the computation discards proportion ''p''<sup>2</sup>&nbsp;+&nbsp;(1&nbsp;−&nbsp;''p'')<sup>2</sup> of the input pairs(00 and 11), which is near one when ''p'' is near zero or one, and is minimized at 1/4 when ''p''&nbsp;=&nbsp;1/2 for the original process (in which case the output stream is 1/4 the length of the input stream on average).

Von Neumann (classical) main operation [[pseudocode]]:
<syntaxhighlight lang="text">
if (Bit1 ≠ Bit2) {
   output(Bit1)
}
</syntaxhighlight>