Editing Bernoulli process (section)

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