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.

► An exact computation of the output rate of Peresʼs algorithm is reported. ► We present a recursive formula for total output on equiprobable inputs. ► The exact rate is compared with another asymptotically optimal algorithm by Elias.