Algorithms for Almost-uniform Generation with an Unbiased BinarySource

We consider the problem of uniform generation of random integers in the range$[1 , n]$ given only a binary source of randomness. Standard models ofrandomized algorithms (e.g. probabilistic Turing machines) assume theavailability of a random binary source that can generate independent randombits in unit time with uniform probability. This makes the task trivial if $n$is a power of $2$. However, exact uniform generation algorithms with boundedrun time do not exist if $n$ is not a power of $2$.We analyze several {\\em almost-uniform} generation algorithms and discuss thetradeoff between the distance of the generated distribution from the uniformdistribution, and the number of operations required per random numbergenerated. In particular, we present a new algorithm which is based on acirculant, symmetric, rapidly mixing Markov chain. For a given positiveinteger $N$, the algorithm produces an integer $i$ in the range $[1,n]$ withprobability $p_i= p_i(N)$ using $O(N \\log n )$ bit operations such that $| p_i- 1/n | c \\beta^N$, for some constant $c$, where\\[ \\beta = \\frac{2^{\\frac{1}{4}} }{\\pi} \\left( \\sqrt{2\\sqrt{2} - \\sqrt{5- \\sqrt{5}}} ~\\right) \\approx 0.4087.\\]This rate of convergence is superior to the estimates obtainable by commonlyused methods of bounding the mixing rate of Markov chains such as conductance,direct canonical paths, and couplings.