Proc. Int. Computing & Combinatorics Conf. (COCOON'98),
August 1998, Taipei, Taiwan, pp. 117-126 .
Ömer Egecioglu and Marcus Peinado
Algorithms for Almost-uniform Generation
with a Random Binary Source
Abstract.
We consider the problem of
uniform generation of random integers in the range [1 , n]
given only a binary source.
Standard models of randomized algorithms (e.g. probabilistic
Turing machines) assume the availability of a random
binary source that can
generate independent random bits in unit time with uniform
probability. This makes the task trivial if n is a power of 2.
However, exact uniform generation algorithms with bounded run time
do not exist if n is not a power of 2.
We analyze several almost-uniform generation algorithms and
discuss the tradeoff between the distance of the generated
distribution from the uniform distribution, and the number of
operations required per random number generated.
In particular, we present a new algorithm which is based on a circulant,
symmetric, rapidly mixing Markov chain.
For a given positive integer N, the
algorithm produces an integer i in the range [1,n] with
probability p_i= p_i(N) using O(Nlog n ) bit operations such that
| p_i - 1/n | < c \beta^N ,
for some constant c, where
$ \beta = \frac{2^{\frac{1}{4}} }{\pi}
( \sqrt{2\sqrt{2} - \sqrt{5- \sqrt{5}}} )
\approx 0.4087$.
omer@cs.ucsb.edu