### 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 P
_{1}with random bits S yields X_{1}, and running it on (P_{2}, S) yields X_{2}, and X_{2}≠ X_{1}, then P_{2}(X_{2}) / P_{2}(X_{1}) > P_{1}(X_{2}) / P_{1}(X_{1})

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.