Sung-il Pae
Michael C. Loui
ABSTRACT
We study the optimal generation of random numbers using a biased coin in two cases: first, when the bias is unknown, and second, when the bias is known. In the first case, we characterize the functions that use a discrete random source of unknown distribution to simulate a target discrete random variable with a given rational distribution. We identify the functions that minimize the ratio of source inputs to target outputs. We show that these optimal functions are efficiently computable. In the second case, we prove that it is impossible to construct an optimal tree algorithm recursively, using a model based on the algebraic decision tree. Our model of computation is sufficiently general to encompass virtually all previously known algorithms for this problem.
Recommendations
Bit-Wise Behavior of Random Number Generators
In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...
Von Neumann's Biased Coin Revisited
LICS '12: Proceedings of the 2012 27th Annual IEEE/ACM Symposium on Logic in Computer ScienceSuppose you want to generate a random sequence of zeros and ones and all you have at your disposal is a coin which you suspect to be biased (but do not know the bias). Can "perfect" randomness be produced with this coin? The answer is positive, thanks ...
Comments