Sampling from Geometric distribution in constant time

Question

I would like to know if there is any method to sample form the Geometric distribution in constant time without using log which can be hard to approximate. Thanks.

Answer 1

Without relying on logarithms, there is no algorithm to sample from a geometric(p) distribution in constant expected time. Rather, on a realistic computing model, such an algorithm's expected running time must grow at least as fast as 1 + log(1/p)/w, where w is the word size of the computer in bits (Bringmann and Friedrich 2013). The following algorithm, which is equivalent to one in the Bringmann paper, generates a geometric(px/py) random number without relying on logarithms, and when px/py is very small, the algorithm is considerably faster than the trivial algorithm of generating trials until a success:

1. Set pn to px, k to 0, and d to 0.
2. While pn*2 <= py, add 1 to k and multiply pn by 2.
3. With probability (1− px /py)^2k, add 1 to d and repeat this step.
4. Generate a uniform random integer in [0, 2^k), call it m, then with probability (1− px /py)^m, return d*2^k+m. Otherwise, repeat this step.

(The actual algorithm described in the Bringmann paper is in fact much more involved than this; see my note "On a Geometric Sampler".)

REFERENCES:

• Bringmann, K., and Friedrich, T., 2013, July. Exact and efficient generation of geometric random variates and random graphs, in International Colloquium on Automata, Languages, and Programming (pp. 267-278).