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.
I did some related things like implementing stratified sampling for RNG used in Monte Carlo simulations, so I understand some of the concepts here, but I still don't have a good intuition for how jitter and shuffling affects the outcome set, or whether it could replicate manually preventing repetitions in results from happening. However, you provided enough information that I think I can figure it out now.
Tell me if I'm understanding this correctly:
- You generate a sequence of uniform random numbers using stratified sampling. This increases variation by ensuring the [0, 1) space is sampled more-less evenly, while not breaking the uniformness of resulting distribution.
- With strata size set to the lowest probability in the desired outcome set, we can ensure even the lowest probability outcome will happen n times (with n = samples per stratum). This allows the low probability events to be observed like a naive expectation would suggest, while still not breaking the overall distribution.
- Alias map is used to translate the stratified uniform sequence to desired distribution (is this the discrete equivalent of rejection sampling?).
- Shuffling is applied to the stratified uniform sequence, and ensures events don't happen in order of decreasing probabilities (modulo shuffling introduced by alias map breaking probabilities into pieces).
- Jitter lets us add additional slight unpredictability, while still not breaking the desired distribution (because jitter is uniformly distributed, so it averages out).
Do I understand this correctly?