I am generating k samples from a Zipf-Mandelbrot distribution (supported on {1, 2, ..., N}), and then sorting them. When k is large this gets slow, so I wondered: can I generate the samples in sequential order somehow? For example, is it possible to find a closed form for the distribution of the "deltas" between successive samples, in terms of k (assuming k << N, so the chance of repeat values is low)? Such a distribution could then be used to generate a list of deltas, then sum those to produce a sorted set of samples.

Generalized harmonic numbers show up in the moments of the Zipf distributions, so this might be tricky. Would it be easier with uniform or exponential? Is there a name for this idea?

  • $\begingroup$ Some side remarks: Uniform distribution and Exponential distribution are very easy to simulate as their CDF is very nice and easy to invert (unlike discrete distribution). The difference between the order statistics are called "spacing", and there are some very nice property for both uniform distribution and exponential distribution. I do not know if it is a efficient way for some distribution, but in general my guess is no. $\endgroup$ – BGM Jun 28 '17 at 14:17
  • $\begingroup$ "Order statistic spacing" leads me to nrbook.com/devroye/Devroye_files/chapter_five.pdf (Non-uniform random variate generation by Devroye). Section 3 looks like a discussion about exactly my question. I'll read through this. Thanks! $\endgroup$ – monguin Jun 29 '17 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.