Breaking the Butterfly Effect: The “Dobbins Selector” Algorithm
Challenge: Design an algorithm that:
- takes a discrete probability distribution and a source of random bits, and returns a sample from the probability distribution.
- if running the algorithm on distribution P1 with random bits S yields X1, and running it on (P2, S) yields X2, and X2 ≠ X1, then P2(X2) / P2(X1) > P1(X2) / P1(X1)
I ran into this problem in the context of a computer game I’m developing. Rather than storing every detail of the game world in the map file, I store a random seed that is used to generate most map features. I found that every time I tweaked certain parameters in my code, old map files became unrecognizable.
Thus, we would like a random sampling algorithm that is unlikely to change its output when we make a small change to the underlying probability distribution (assuming we keep our original random seed). In particular, if we increase the probability of one outcome and renormalize the others, then the only way the outcome should change is if it changes to the outcome whose probability we increased.
If you want to solve the problem yourself, this would be a good time to stop reading.
I shared this problem with Michael Dobbins and he solved it for me.
Mike’s method is to associate each face of a simplex with one of the outcomes. We pick a random point inside the simplex, and measure the distance from that point to each of the faces, then divide that distance by the probability of the associated outcome. The lowest number wins.
I understand the solution, but not the original problem. How did generating different random values make old map files unreadable?
Also, this won’t help if you change the code to generate one more or less random number somewhere.
Comment by Phil Goetz — May 2, 2010 @ 10:42 am
Old map files were still readable; they just didn’t unfold into the same maps as they did before. And they were not just a little different, but very different.
Also, there are plenty of ways to avoid the latter problem. For instance, instead of generating random seeds in sequence, you can have each subroutine generate its own seed by XORing a global random seed with some predefined value of its own.
Comment by Peter de Blanc — May 2, 2010 @ 11:47 am