5 ms·
There's a probability model called the Pólya urn where you imagine an urns containing numbered balls (colored balls in a typical example, but to draw the compar
by andy_wrote 9y ago
There's a probability model called the Pólya urn where you imagine an urns containing numbered balls (colored balls in a typical example, but to draw the comparison with dice we can say they're numbered 1-6), and every time you draw a ball of a certain color, you put back more balls according to some rule. A few probability distributions can be expressed in terms of a Pólya urn, see https://en.wikipedia.org/wiki/P%C3%B3lya_urn_model https://en.wikipedia.org/wiki/P%C3%B3lya_urn_model.
A fair 6-sided die would be an equal number of balls numbered 1-6 and a rule that you simply return the ball you drew. You can get a gambler's fallacy distribution by, say, adding one of every ball that you didn't draw. I read the code as a Pólya urn starting with 1 ball 1-N and doing that on each draw plus reducing the number of balls of the drawn number to 1.
Also related, in 2d space, is the idea of randomly covering the plane in points but getting a spread-out distribution, since uniformity will result in clusters. (If you're moving a small window in any direction and you haven't seen a point in a while, you're "due" to see another one, and vice versa if you just saw a point.) Mike Bostock did a very nice visualization of that here: https://bost.ocks.org/mike/algorithms/ https://bost.ocks.org/mike/algorithms/
- xori 9y agoThank you! Sometimes the hardest thing is knowing what to google!
- duxup 9y agoI do a lot of furious googling thinking: "Oh man this has to be a thing but what could it be and how would someone describe it?... awe forget it." Then months later by accident while looking at a completely different topic: "OMG there it is, the thing!"
- CPLX 9y agoIndeed. This happened to me the other day trying to find the name for a domino joiner while googling for biscuit joiners.
- vinchuco 9y agohttps://en.wikipedia.org/wiki/True_name https://en.wikipedia.org/wiki/True_name
- Grae 9y agoToday I learned the true name of true name.
- dminor 9y agoAnother algorithm along these lines is the "shuffle bag" algorithm.
- femto113 9y agoSettlers of Catan switched to this at some point--from 2 dice to a set of numbered tiles with the same distribution that you shuffle and draw from. It definitely pared some "oh man I'm so unlucky" scenarios from the game but I'm not convinced it made it more fun.
- petschge 9y agoCovering the plane randomly but without clusters is actually quite useful in simulations. The "random" numbers that do that are often call "low-discrepancy sequence".
- thaumasiotes 9y agoAlso called "quasirandom" numbers, as I learned it from wikipedia years ago. ("Quasirandom" and "quasirandom numbers" today redirect to "low-discrepancy sequence".)
- petschge 9y agoThere is many names for it. The problem with "quasirandom" is that is sounds a lot like "pseudorandom". For the special case of points in a plane looking for "Poisson disk sampling" also brings many great resources.
- deleted 9y ago[deleted]
- brchr 9y agoIn the 1960s, the biostatistician Marvin Zelen proposed using something very much like the Pólya urn for clinical trials, calling it the "play the winner" rule [1]. This has had a major effect in causing a rethinking of the traditional randomized controlled trial, and these ideas are still making their way through the medical community today [2]. [1] https://www.jstor.org/stable/2283724 https://www.jstor.org/stable/2283724 [2] https://www.fda.gov/downloads/MedicalDevices/DeviceRegulationandGuidance/GuidanceDocuments/UCM446729.pdf https://www.fda.gov/downloads/MedicalDevices/DeviceRegulatio...
- andy_wrote 9y agoInteresting - just perusing those links, it sounds like a multi-armed bandit problem, in which you reason that if something has worked out before, you should tilt your bets more in that direction. In the context of the urn model, you'd return more balls of the same color for every successful draw. In the context of medicine, you can balance between proving or disproving a treatment effect and actually supplying that treatment to the test subjects who need them. Relatedly, there's a Bayesian interpretation to overweighting successful past draws. A model where you return one extra ball of the same color to the urn gets you a Dirichlet-multinomial distribution, which is a die-roll distribution where the weights to each face are not known for sure, but are given a probability distribution and revised with observed evidence. In other words: here's an n-sided die, I don't know its weightings, but as I observe outcomes I'll update my beliefs that the sides that come up are more favorably weighted. The number of balls in the urn you start with correspond to your priors; only 1 ball of each color means a very weak belief that it's a fair die, 1000 balls of each color means a strong belief, unequal numbers mean that you start off believing it's weighted.
- Jaruzel 9y ago> Mike Bostock did a very nice visualization of that here: https://bost.ocks.org/mike/algorithms/ https://bost.ocks.org/mike/algorithms/ Thank you for that link - a great read!