Saturday, May 05, 2018

[dayxephk] 1/x samples infinity

Sample uniformly between 0 and 1, excluding zero but including 1.  (NB: this behavior regarding endpoints is the opposite of what most standard random number generators do, so do 1-x if necessary.)  Compute 1/x to non-uniformly sample between 1 and infinity.  Subtract 1 if desired to sample between 0 and infinity (because infinity minus 1 is still infinity). Floor to sample a random integer.

This is an approximation to the Zipf distribution with exponent 2.  Previously, on approximating the Zipf distribution with the more common exponent 1.  We can also consider exponents between 1 and 2 but things are probably not so elegant.

We could start with a different distribution between 0 and 1, perhaps heavily weighted toward zero to generate larger numbers more frequently: I think 1/(1-x)^a.  The transformation function could also be something like b^(1/x-1).

No comments :