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.

23 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

  6. купить духи харьков…

    How can I make firefox to prompt me for what to do with a file instead of automatically downloading?…

    Trackback by купить духи харьков — April 25, 2014 @ 8:04 am

  7. Prothese: Oberschenkelprothese durch elektronisch gesteuertem Kniegelenk und Karbonfu脽 (los angeles. 25 000 dinar).
    air max 90 sale http://www.aquarix.de/billig/air-max-90-sale.html

    Comment by air max 90 sale — April 30, 2014 @ 6:27 pm

  8. amazingly; the new lion, An central source, And the administrative centre standard “gary the gadget guy, The lion was required in various poses the particular last half the particular 19th Century, and so they overlap various other, associate with sophisticated. they could be; the type of Lion uncontrolled (fighting) looking at well 1852 1865, Lion Passant (Walking) dealing with abandoned, like with the english language sterling 1855 1860, and as well,as well as the Lion Passant oriented towards dropped (one last release) including 1860 for this.
    nike free 4.0 v2 46 http://www.movelaria.arq.br/buyairmax.asp?p=3973

    Comment by nike free 4.0 v2 46 — May 1, 2014 @ 2:21 am

  9. roofing contractors augusta…

    get the best augusta contractors around…

    Trackback by roofing contractors augusta — May 4, 2014 @ 1:50 am

  10. stalbertchamber.com

    Comment by ray ban new wayfarer — May 11, 2014 @ 11:25 pm

  11. They’re undertaken for moncler along jackets matte quilted nylon and now have some chichi nylon scruff of the neck not to mention wonderful make detail.

    Comment by http://www.whichcomputer.net/%E3%82%B3%E3%82%B0%E8%85%95%E6%99%82%E8%A8%88-cogu-cogu-%E8%85%95%E6%99%82%E8%A8%88-%E3%82%B3%E3%82%B0-%E6%99%82%E8%A8%88-%E3%83%A1%E3%83%B3%E3%82%BA-%E3%83%AC%E3%83%87%E3%82%A3%E3%83%BC%E3%82%B9-%E7%94%B7%E5%A5%B3%E5%85%BC%E7 — May 17, 2014 @ 2:50 pm

  12. Elegant Belief Within a Peacoat Coat Regarding MenA coat which is secure, will keep an individual’s toasty, and also will allow you to meet a day’s projects is vital with regard to cold months.

    Comment by http://www.koshershirsts.com/clarks-%E3%82%AF%E3%83%A9%E3%83%BC%E3%82%AF%E3%82%B9/%E3%83%A1%E3%83%B3%E3%82%BA/%E3%83%93%E3%82%B8%E3%83%8D%E3%82%B9%E3%82%B7%E3%83%A5%E3%83%BC%E3%82%BA — May 17, 2014 @ 7:02 pm

  13. Major thanks David in an additional remarkable source that will assist the entire business.

    Comment by ray ban homme pas cher — May 19, 2014 @ 4:42 am

  14. The best way to Provide Heated Jackets around Buenos aires, DCPlaces to help you Contribute Hair Applications.

    Comment by http://www.paclate.com/%E3%82%B7%E3%83%A3%E3%83%8D%E3%83%AB-chanel-%E3%83%9E%E3%83%88%E3%83%A9%E3%83%83%E3%82%BB25-%E3%83%A9%E3%83%A0%E3%82%B9%E3%82%AD%E3%83%B3-%E3%83%96%E3%83%A9%E3%83%83%E3%82%AF-%E3%82%B4%E3%83%BC%E3%83%AB%E3%83%89%E9%87%91%E5%85%B7-w% — May 26, 2014 @ 1:58 pm

  15. I want to start a blog/online diary, but not sure where to start..

    Comment by cheap youtube likes — June 22, 2014 @ 11:01 am

  16. I¡¦ll immediately snatch your rss as I can’t find your e-mail subscription link or e-newsletter service. Do you’ve any? Kindly permit me recognize so that I may just subscribe. Thanks.
    Authentic louis vuitton handbags sale authentic http://e222.nforce.co.uk

    Comment by Authentic louis vuitton handbags sale authentic — June 28, 2014 @ 3:01 am

  17. nice articles

    Comment by manolo blahnik discount shoes — July 14, 2014 @ 1:43 pm

  18. space and games » Breaking the Butterfly Effect: The “Dobbins Selector” Algorithm
    aqfnmjhbqsd
    [url=http://www.g5k4rnnb4il0071b571ys0xz6dw7231ss.org/]uqfnmjhbqsd[/url]
    qfnmjhbqsd http://www.g5k4rnnb4il0071b571ys0xz6dw7231ss.org/

    Comment by qfnmjhbqsd — July 31, 2014 @ 5:28 am

  19. miumiu portafog,ミュー%e

    Comment by 千葉でトリーバーチの扱い店,名古屋 求人 クロエ,カードケース 首掛け — August 4, 2014 @ 9:59 pm

  20. uggs for sale…

    ugg boots onlinewkpugg boots onlinehtvugg outlet onlineoimugg outlet onlinezydugg boots onlineypfugg outlet onlineygsuggs for saleyerugg outlet onlineumwuggs for salennjuggs for salehseugg boots onlinebfhugg outlet onlineugrugg boots onlineobfugg boots…

    Trackback by uggs for sale — November 30, 2014 @ 8:01 pm

  21. cheap uggs…

    fake uggs boots|fake uggs boots uk|replica uggs boots|ugg boots cheap|ugg uk sale|cheap ugg boots|discount ugg boots|replica uggs uk|ugg boots uk|ugg boots outlet uk…

    Trackback by cheap uggs — December 1, 2014 @ 3:07 pm

  22. Cheap Jordans…

    http://mtregional.org/menu.aspfendi for sale…

    Trackback by Cheap Jordans — December 12, 2014 @ 3:25 am

  23. barbour store…

    moncler cheapgco canada goose cheapobo canada goose cheapgdf the north face cheapdeh moncler cheapnjn moncler cheaphpf the north face cheapddb moncler cheapfhj moncler cheapilk moncler cheaploc the north face cheapjbb canada goose cheapcdi hollister ch…

    Trackback by barbour store — December 17, 2014 @ 4:04 pm

RSS feed for comments on this post. TrackBack URI

Leave a comment

Powered by WordPress