CODEWITHSUNDEEP
randomprobability
Pierre21
Pierre21

Reputation: 143

Sampling from Geometric distribution in constant time

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.

Upvotes: 3

Views: 442

Answers (1)

Peter O.
Peter O.

Reputation: 32878

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, 2k), call it m, then with probability (1− px /py)m, return d*2k+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).

Upvotes: 4

Related Questions