5 ms·
> Together we came up with a solution that solves this with O(n) memory usage where n is the number of choices, and O(log n) CPU cost. And it allows you to deci
by dahart 7y ago
> Together we came up with a solution that solves this with O(n) memory usage where n is the number of choices, and O(log n) CPU cost. And it allows you to decide if you want to be more random or more deterministic.
I think you can do the same thing and solve all the same problems in O(1) time per sample using the alias method plus shuffling while blending between regular uniform samples and jittered uniform samples.
- Build your alias map of M buckets, the distribution you want to sample
- Take a set of N uniform samples, and use a knob to blend between regular and jittered. It looks like:
r=lerp(knob, 0.5, rand())/N
- Shuffle the uniform samples, e.g. std::random_shuffle(). This can be done incrementally, per sample (https://en.wikipedia.org/wiki/Fisher–Yates_shuffle https://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
- Plug the uniform sample into the alias map to find your sampled choice.
- Repeat when you run out of the N uniform samples.
https://en.wikipedia.org/wiki/Alias_method https://en.wikipedia.org/wiki/Alias_method
http://www.keithschwarz.com/darts-dice-coins/ http://www.keithschwarz.com/darts-dice-coins/
- ribrars 7y agoNice, seems like a great solution especially in the use case where this service is needed by a game server and good performance is a requirement.
- Strilanc 7y agoFor some reason alias sampling is not well known, even though it strictly dominates using a search tree when generating randomness (it's faster, it uses less memory, and IMO it's easier to code). It even works better when generalized to the case of preparing superpositions on quantum computers ( https://algassert.com/post/1805 https://algassert.com/post/1805 ).
- ur-whale 7y agoAlias sampling is a really beautiful algorithm, but implementing it correctly and efficiently isn't as easy as you seem to imply. I would also very much like to know what a generalization of this algorithm to continuous distribution would look like.
- Strilanc 7y agoYou make a list of below-average bars and a list of above-average bars. Iteratively pop the top of both, donate from the larger to the smaller until the smaller is average, then put the larger back into the appropriate list based on its new value. Stop when there's no too-large bars left. Compared to writing a red black tree it's trivial.
- ur-whale 7y agoA correct implementation wrt probabilities being exact given a frequency table (the "average" can be a very large rational number), as well as efficient when constructing the data structure to be sampled from during sampling phase is IMO not as trivial as you seem to imply. I have asked people to implement this algorithm during engineering interviews on a regular basis for the better part of five years, and I can promise you, strictly none of the candidate who were subjected to it would describe their experience as "I was asked a trivial question". But then everyone has their own bar for the word "trivial". I know for example that I have my own bar for the word "arrogance".
- dahart 7y agoOh wow, how do you prompt the interviewees? Do you tell them about the average value threshold or the guarantee you only need 2N buckets? If not, I’d guess this is probably way too hard of an interview question, even though a decent implementation really isn’t that difficult. Is this like a bonus difficult question for someone who aces all your other questions? The implementation isn’t hard once you’ve read the Vose paper or the Keith Schwarz link I posted. There’s only one tricky part about handling rounding that is pretty easy to fix. I would never expect anyone who hasn’t heard of the idea to be able to implement it on the spot without being more or less given a recipe for the math and how to use it. If you ever find someone who can, hire them immediately! This is one of those problems that only feels somewhat easy in retrospect, but almost nobody could derive any of it on their own. The alias method is extremely clever, and not at all trivial.
- 7y ago
- TeMPOraL 7y agoThanks for the links. The last one is long, but made it easy to understand how and why alias method works (and it's awesome for providing mathematical proofs along with algorithms). 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?
- dahart 7y agoSure, my thinking is that N stratified uniform samples plugged into the alias map is the part that prevents the annoying low-probability sequences. This is very similar to the simpler and more common technique of picking from a shuffled list of outcomes, but plugging it into the alias map allows the outcomes to have arbitrary probabilities not quantized by the number of choices. 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.