The shuffle and jitter are the things that control randomness. Shuffle controls the order of events, and jitter controls which events are chosen. Using both you can have different outcomes each time through the N samples.
Regular sampling would give you the same set of events, where jittering will change which events are chosen depending on your parameter choices. But! Jitter will only change the number of each event chosen by a limited amount that you control.
The choices for the blending knob and the number N of uniform samples, along with your goal distribution, let you control how often and by how much the events change. For example, by picking an N that gives you uniform strata that are the same size as the smallest item in the goal distribution, you can guarantee that you get at least one choice from each item in the goal distribution. I think this would also ensure that adding jitter changes the number of choices for each goal bucket by at most 1. It might be by at most 2, due to the alias map’s splitting of large buckets, and this cap might need strata that are half the size of the smallest bucket. I’m not sure of the exact details without trying it, but I am pretty sure this gives you control over the amount of variation; the number of events you can possibly have above or below the expected value.
That’s the idea though - choosing N and using the knob allows you to decide how much variation you want on top of the guarantee that you never get sequences that feel wholly improbable.
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?
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.
That said, I'm having trouble understanding the solution you described. I can understand how the alias method can help me efficiently sample an arbitrary discrete probability distribution, but I can't see how adding jitter helps with the problem from TFA - namely, to generate samples that conform to a given distribution long-term, but avoid hitting "annoying" low-probability outcomes like strings of consecutive lower-probability options. Could you please clarify / expand on your explanation?