space and games

April 6, 2010

Breaking the Butterfly Effect: The “Dobbins Selector” Algorithm

Filed under: Useful Statistics — Peter de Blanc @ 3:13 pm

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.

5 Comments »

  1. 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

  2. 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

  3. converges to x as the size of the sample approaches infinity. We can think of the outcome of a bet as a random variable. This law tells us that as the number of bets becomes very large the average result will get closer to the house edge.

    Comment by Perry I. Shaw — February 13, 2013 @ 10:23 pm

  4. http://couponman.in/stores/ebay-coupons/...

    I’m creating a new blog about literature ( what I’ve read, what I’m reading), but I’m having trouble thinking of a title. I like the idea of something having to do with an obsession with literature but I think bookophilia is on the average side. Wh…

    Trackback by http://couponman.in/stores/ebay-coupons/ — February 24, 2014 @ 10:52 pm

  5. Let’s say a candidate name Susan that’s currently working in a small private firm and understands some parts with the financial
    business. The companies attempt to recognize any level of frauds that could be linked with the announce ‘ there are usually any wide selection of statements that could be
    bogus. Comparing insurance quotes online makes it possible to
    quite a lot in using best decision and eliminates the
    need to provide money to a insurance agent for
    your quotes.

    Comment by high risk pool — March 18, 2014 @ 8:09 pm

RSS feed for comments on this post. TrackBack URI

Leave a comment

Powered by WordPress