Exact output rate of Peres's algorithm for random number generation
An exact computation of the output rate of Peres's algorithm is reported. The algorithm, recursively defined, converts independent flips of a biased coin into unbiased coin flips at rates that approach the information-theoretic upper bound, as the input size and the recursion depth tend to infinity. However, only the limiting rate with respect to the input size is known for each recursion depth. We compute the exact output rate for each fixed-length input and compare it with another asymptotically optimal method by Elias. (C) 2013 Elsevier B.V. All rights reserved.
random number generation analysis of algorithms von neumann's method peres's method elias's method