In a recent work, Bernardini and Rinaldo generalize and attempt to improve upon Elias method to obtain unbiased random bits from a geometric distribution resulted from a Poisson process. As a response, we analyse the output rates of their method and compare with the original binary Elias method applied on a Bernoulli process resulted from the same Poisson process, which turns out to be much simpler to implement and to have a higher output rate.
BernardiniR. and RinaldoR., Unbiased random sequences from measurements of poisson processes, in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)2014, pp. 8188–8192.
2.
CoverT.M. and ThomasJ.A., Elements of information theory, (2. ed.), Wiley, 2006.
3.
DijkstraE.W., Making a fair roulette from a possibly biased coin, Information Processing Letters36 (1990), 193.
4.
EliasP., The efficient construction of an unbiased random sequence, The Annals of Mathematical Statistics43(3) (1972), 865–870.
5.
JuelsA., JakobssonM., ShriverE. and HillyerB.K., How to turn loaded dice into fair coins, IEEE Transactions on Information Theory46(3) (2000), 911–921.
6.
KnuthD.E., The Art of Computer Programming, Combinatorial Algorithms, Part 1, volume 4A. Addison-Wesley, 2011.
7.
KnuthD.E. and YaoA.C.-C., The complexity of nonuniform random number generation. In JosephF. Traub, editor, Algorithms and Complexity: New Directions and Recent Results. Proceedings of a Symposium, NewYork, NY, 1976, pp. 357–428. Carnegie-Mellon University, Computer Science Department, Academic Press. Reprinted in Knuth’s Selected Papers on Analysis of Algorithms (CSLI, 2000).
8.
PaeS., Exact output rate of Peres’s algorithm for random number generation, Inf Process Lett113(5-6) (2013), 160–164.
9.
PaeS., A generalization of Peres’s algorithm for generating random bits from loaded dice, IEEE Transactions on Information Theory61(2) (2015).
10.
PaeS., Binarizations in random number generation, In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 2016, pp. 2923–2927.
11.
PaeS. and LouiM.C., Optimal random number generation from a biased coin, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005) pp. 1079–1088.
12.
PaeS. and LouiM.C., Randomizing functions: Simulation of discrete probability distribution using a source of unknown distribution, IEEE Transactions on Information Theory52(11) (2006), 4965–4976.
13.
PeresY., Iterating von Neumann’s procedure for extracting random bits, Annals of Statistics20(1) (1992), 590–597.
14.
RyabkoB.Y. and MatchikinaE., Fast and efficient construction of an unbiased random sequence, IEEE Transactions on Information Theory46(3) (2000), 1090–1093.
15.
SamuelsonP.A., Constructing an unbiased random sequence, Journal of American Statistical Sociaety63(324) (1968).
16.
ShannonC.E., WarrenW., The Mathematical Theory of Communication, The University of Illinois Press, Urbana. 1964.
17.
SteinC., CormenT.H., RivestR.L., LeisersonC.E., Introduction to Algorithms, MIT Press, 2nd edition, 2001.
18.
StoutQ.F. and WarrenB., Tree algorithms for unbiased coin tossing with a biased coin, Annals of Probability12(1) (1984), 212–222.
19.
von NeumannJ., Various techniques for use in connection with random digits. Notes by ForsytheG.E.. In Monte Carlo Method, Applied Mathematics Series, volume 12, pp. 36–38. U.S. National Bureau of Standards, Washington D.C., 1951. Reprinted in von Neumann’s, Collected Works5 (Pergammon Press, 1963), pp. 768–770.
