Editing Bernoulli process (section)

==Randomness extraction==
{{Main article|Randomness extractor}}
From any Bernoulli process one may derive a Bernoulli process with ''p''&nbsp;=&nbsp;1/2 by the [[von Neumann extractor]], the earliest [[randomness extractor]], which actually extracts uniform randomness.

=== 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>

=== Iterated von Neumann extractor ===
{{Cite check|section|date=January 2014|talk=Iterated Von Neumann extractor}}
This decrease in efficiency, or waste of randomness present in the input stream, can be mitigated by iterating the algorithm over the input data. This way the output can be made to be "arbitrarily close to the entropy bound".<ref name=Peres>{{cite journal|last=Peres|first=Yuval|title=Iterating Von Neumann's Procedure for Extracting Random Bits|journal=The Annals of Statistics|date=March 1992|volume=20|issue=1|pages=590–597|doi=10.1214/aos/1176348543|doi-access=free}}</ref> 

The iterated version of the von Neumann algorithm, also known as advanced multi-level strategy (AMLS),<ref>{{cite web |url=http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf |archive-url=https://web.archive.org/web/20100331021838/http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf |archive-date=2010-03-31 |url-status=live |title=Tossing a Biased Coin |publisher=eecs.harvard.edu |access-date=2018-07-28}}</ref> was introduced by Yuval Peres in 1992.<ref name=Peres/> It works recursively, recycling "wasted randomness" from two sources: the sequence of discard-non-discard, and the values of discarded pairs (0 for 00, and 1 for 11). It relies on the fact that, given the sequence already generated, both of those sources are still exchangeable sequences of bits, and thus eligible for another round of extraction. While such generation of additional sequences can be iterated infinitely to extract all available entropy, an infinite amount of computational resources is required, therefore the number of iterations is typically fixed to a low value – this value either fixed in advance, or calculated at runtime.

More concretely, on an input sequence, the algorithm consumes the input bits in pairs, generating output together with two new sequences, () gives AMLS paper notation:

{|
! input !! output !! new sequence 1(A) !! new sequence 2(1)
|-
| 00 || ''none'' || 0 || 0
|-
| 01 || 0 || 1 || ''none''
|-
| 10 || 1 || 1 || ''none''
|-
| 11 || ''none'' || 0 || 1
|}

(If the length of the input is odd, the last bit is completely discarded.) Then the algorithm is applied recursively to each of the two new sequences, until the input is empty.

Example: The input stream from the AMLS paper, ''11001011101110'' using 1 for H and 0 for T, is processed this way:
{|
! step number !! input !! output !! new sequence 1(A) !! new sequence 2(1)
|-
| 0 || (11)(00)(10)(11)(10)(11)(10) || ()()(1)()(1)()(1) || (1)(1)(0)(1)(0)(1)(0) || (1)(0)()(1)()(1)()
|-
| 1 || (10)(11)(11)(01)(01)() || (1)()()(0)(0) || (0)(1)(1)(0)(0) || ()(1)(1)()()
|-
| 2 || (11)(01)(10)() || ()(0)(1) || (0)(1)(1) || (1)()()
|-
| 3 || (10)(11) || (1) || (1)(0) || ()(1)
|-
| 4 || (11)() || () || (0) || (1)
|-
| 5 || (10) || (1) || (1) || ()
|-
| 6 || () || () || () || ()
|}



Starting from step 1, the input is a concatenation of sequence 2 and sequence 1 from the previous step (the order is arbitrary but should be fixed). The final output is ''()()(1)()(1)()(1)(1)()()(0)(0)()(0)(1)(1)()(1)'' (=''1111000111''), so from 14 bits of input 10 bits of output were generated, as opposed to 3 bits through the von Neumann algorithm alone. The constant output of exactly 2 bits per round per bit pair (compared with a variable none to 1 bit in classical VN) also allows for constant-time implementations which are resistant to [[Timing attack|timing attacks]].

Von Neumann–Peres (iterated) main operation pseudocode:
<syntaxhighlight lang="text">
if (Bit1 ≠ Bit2) {
   output(1, Sequence1)
   output(Bit1)
} else {
   output(0, Sequence1)
   output(Bit1, Sequence2)
}
</syntaxhighlight>
Another tweak was presented in 2016, based on the observation that the Sequence2 channel doesn't provide much throughput, and a hardware implementation with a finite number of levels can benefit from discarding it earlier in exchange for processing more levels of Sequence1.<ref>{{cite conference |url=https://www.esat.kuleuven.be/cosic/publications/article-2628.pdf |archive-url=https://web.archive.org/web/20190212011337/https://www.esat.kuleuven.be/cosic/publications/article-2628.pdf |archive-date=2019-02-12 |url-status=live |title=Iterating Von Neumann's post-processing under hardware constraints |last1=Rožić |first1=Vladimir |last2=Yang |first2=Bohan |last3=Dehaene |first3=Wim |last4=Verbauwhede |first4=Ingrid |date=3–5 May 2016 |place=Maclean, VA, USA |conference=2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST) |doi=10.1109/HST.2016.7495553 }}</ref>