Re:A New Algorithm for Controlled Randomness
by dahart on Sunday September 01, 2019 @02:45PM
(#20853953)
Yes, spot on, I think that describes it exactly.
And yes, the alias map serves a very similar function to rejection sampling of a discrete distribution, except that you don’t have to waste any samples. And the alias map serves as a deterministic mapping function; the same input will always yield the same output.
There’s another method for discrete distribution sampling that is closer to alias mapping, and better preserves stratification than the alias method but costs O(log n) per sample: compute the discrete CDF, and then invert it by picking a uniform sample and using that to binary search on the (sorted by definition) CDF to recover the choice, which will be then distributed according to your original discrete PDF array. For sample set size that is known in advance, you can avoid the binary search, and do this in O(1) time per sample.
The method in the article feels similar-ish to the binary search method, maybe it’s equivalent, but I’m not sure.
And yes, the alias map serves a very similar function to rejection sampling of a discrete distribution, except that you don’t have to waste any samples. And the alias map serves as a deterministic mapping function; the same input will always yield the same output.
There’s another method for discrete distribution sampling that is closer to alias mapping, and better preserves stratification than the alias method but costs O(log n) per sample: compute the discrete CDF, and then invert it by picking a uniform sample and using that to binary search on the (sorted by definition) CDF to recover the choice, which will be then distributed according to your original discrete PDF array. For sample set size that is known in advance, you can avoid the binary search, and do this in O(1) time per sample.
The method in the article feels similar-ish to the binary search method, maybe it’s equivalent, but I’m not sure.