mercredi 2 février 2022

von Neumann random number extractor

Von Neumann suggested (1951) to extract random numbers from biased coin throws by generating a one if a two-coin throw is 1-0, generating a zero if the two-coin throw is 0-1, and ignoring the 0-0 and 1-1. He then writes “The resulting process is rigorously unbiased, although the amended process is at most 25% as efficient as ordinary coin tossing.” (“Various techniques Used in Connection With Random Digits”, J. Res. Nat. Bur. Stand. Appl. Math. Series 3, 36-38 (1951).

Should it not be “…at most 50% as efficient…”?

After all, the second toss of a two-toss can be used as the first toss of the next two-toss, since the tosses are independent.




Aucun commentaire:

Enregistrer un commentaire