2 ms·

I'm a little skeptical about the domain of usefulness of this algorithm. The simple method that computes the CDF and uses binary search for sampling is called

by mturmon 15y ago

I'm a little skeptical about the domain of usefulness of this algorithm. The simple method that computes the CDF and uses binary search for sampling is called "Roulette wheel selection" in this writeup. The only difference at the big-O level between the "beautiful algorithm" and the above simple algorithm is, the latter takes log(n) steps for sampling versus O(1) (setup and memory usage are the same). How many problems have n large enough so const1*log(n)+const2 is significantly more than the constant in O(1) algorithm? Not many, I'll bet, especially since const1 and const2 are small due to the simplicity of the simple CDF-based algorithm. If it was O(sqrt(n)) vs. O(1), this would be a different thing, but log is different. This is not to diminish the inherent interest in the sampling arguments used, and the existence of a big-O faster algorithm.

talaketu 15y ago
Imagine a scenario in which you need to generate a large number of samples based on a discrete random variable with a large number of outcomes n. If you had a library that implemented both algorithms, which should you use? Are you skeptical that a domain for that scenario exists?
- mturmon 15y ago
  I'm just saying that n has to be very large before the O(1) asymptotics kick in, that is, for: c1 log(n) + c2 > c3 where, from what I can see, c3 >> c2 and c1 is low. And the setup time for the other algorithm is also greater (but, the same according to the O() measure). In answer to your rhetorical question: I'd benchmark both. But, I already implemented the simpler algorithm in existing code, and bottlenecks for problems of interest to me are elsewhere. Also, the more complex algorithm is more likely to have a bug -- which might be elusive, as they sometimes are with complex RNGs. I've found bugs in the published algorithms in DeVroye's book, for instance, and that book is considered authoritative. It's hard to convey just how subversive a parameter-dependent bug in a low-level RNG can be.

by mturmon 15y ago

talaketu 15y ago

Imagine a scenario in which you need to generate a large number of samples based on a discrete random variable with a large number of outcomes n. If you had a library that implemented both algorithms, which should you use? Are you skeptical that a domain for that scenario exists?

mturmon 15y ago
I'm just saying that n has to be very large before the O(1) asymptotics kick in, that is, for: c1 log(n) + c2 > c3 where, from what I can see, c3 >> c2 and c1 is low. And the setup time for the other algorithm is also greater (but, the same according to the O() measure). In answer to your rhetorical question: I'd benchmark both. But, I already implemented the simpler algorithm in existing code, and bottlenecks for problems of interest to me are elsewhere. Also, the more complex algorithm is more likely to have a bug -- which might be elusive, as they sometimes are with complex RNGs. I've found bugs in the published algorithms in DeVroye's book, for instance, and that book is considered authoritative. It's hard to convey just how subversive a parameter-dependent bug in a low-level RNG can be.