4
$\begingroup$

Which bit is retained in the Von Neumann debiasing algorithm? 00 and 11 are discarded and 10, 01 are retained but is the first or the second bit retained or does it matter?

In other words:

first: 10 -> 1 , 01 -> 0

second: 10 -> 0 , 01 -> 1

Original Paper (appears to be first but could be interpreted either way):

https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf

Examples (first digit accept):

https://en.wikipedia.org/wiki/Hardware_random_number_generator#Software_whitening

https://en.wikipedia.org/wiki/Randomness_extractor

http://pit-claudel.fr/clement/blog/generating-uniformly-random-data-from-skewed-input-biased-coins-loaded-dice-skew-correction-and-the-von-neumann-extractor/#more-410

https://people.seas.harvard.edu/~salil/pseudorandomness/extractors.pdf

Examples (second digit accept):

https://www.researchgate.net/publication/38359648_Iterating_Von_Neumann's_Procedure_for_Extracting_Random_Bits

https://www.esat.kuleuven.be/cosic/publications/article-2628.pdf

Examples of the second are present in papers regarding an Iterated Von Neumann algorithm.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Does it matter? Hint: Write down the assumptions, and compute from the assumptions the probability distributions of the outcomes of both alternatives. $\endgroup$
    – Squeamish Ossifrage
    Apr 25 '19 at 23:22
  • $\begingroup$ Why pick one when you can alternate? $\endgroup$
    – Nat
    Apr 26 '19 at 1:50
4
$\begingroup$

It doesn't matter at all, since both $01$ and $10$ have the same probability $p(1-p).$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Furthermore, using the second bit instead of the first (or vice versa) just has the effect of inverting the output. And a uniformly random bitstream is still uniform even if inverted. $\endgroup$
    – Ilmari Karonen
    Apr 25 '19 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.