Rejection-inversion to generate variates from monotone discrete distributions

For discrete distributions a variant of reject from a continuous hat function is presented. The main advantage of the new method, called rejection-inversion , is that no extra uniform random number to decide between acceptance and rejection is required, which means that the expected number of uniform variates required is halved. Using rejection-inversion and a squeeze, a simple universal method for a large class of monotone discrete distributions is developed. It can be used to generate variates from the tails of most standard discrete distributions. Rejection-inversion applied to the Zipf (or zeta) distribution results in algorithms that are short and simple and at least twice as fast as the fastest methods suggested in the literature.