eigenclass - Warm fuzzy things for random simulations

MAIN Index Search Changes PageRank Login

Let's talk about random experiments. The simplest one is tossing a coin, with outcomes "heads" and "tails". It's so elementary that we fully understand it intuitively once we're told that the coin is not loaded. There are three basic problems of interest:

How to simulate the experiment with a computer and obtain results undistinguishable from the real thing?
If we're given an outcome, can we compute its probability?
Can we enumerate all possible outcomes and their probabilities?

In our first experiment, the answers are "rand 2" (if take e.g. "heads" = 0, "tails" = 1), "1/2" and "heads, tails, both with probability 1/2". Easy indeed. Now on to something harder: rolling a fair die. The answers are now "1 + rand(6)", "1/6", and "1..6, all with probability 1/6". Still trivial. Let's aim for the stars! What about rolling three dice? The outcomes are clearly 3..18, but what are the probabilities?

Intuition doesn't help much here --- we "can see" the possible outcomes, but most people cannot give the precise probabilities intuitively (I certainly can't; I can at most draw an approximate graph, but that's because I am used to convolutions). The first problem was how to simulate the experiment; this is by far the easiest one. This is what our dice rolling simulation looks like in Ruby:

  def roll_3d6
    d1 = rand(6)
    d2 = rand(6) 
    d3 = rand(6)
    1 + d1 + 1 + d2 + 1 + d3
  end

We can now simulate the experiment easily, but this doesn't help us with the harder problems: giving the probability of an outcome and doing so for all possible outcomes. Clearly, the above snippet has got all the information we need about this random simulation; it's indeed a precise definition. Wouldn't it be nice to have the computer solve the three problems of interest (simulation, distribution and expectation) for us if we give it the specification of the simulation? It turns out this can be done with a little code massaging:

  def roll_3d6(m)
    m.rand(6).in do |d1|
      m.rand(6).in do |d2|
        m.rand(6).in do |d3|
          m.ret(1+d1 + 1+d2 + 1+d3)
        end
      end
    end
  end

Given suitable Simulation, Distribution and Expectation classes, we can solve all three problems with the above code.

Simulating the experiment:

 p roll_3d6(Simulation.init).run    
 #  >> 9

All the possible outcomes and their probabilities:

 p roll_3d6(Distribution.init).run  
 # >>  
 # [[3, 0.00462962962962963], [4, 0.0138888888888889], [5, 0.0277777777777778], 
 # [6, 0.0462962962962963], [7, 0.0694444444444444], [8, 0.0972222222222222], 
 # [9, 0.115740740740741], [10, 0.125], [11, 0.125], [12, 0.115740740740741],
 # [13, 0.0972222222222222], [14, 0.0694444444444444], [15, 0.0462962962962963],
 # [16, 0.0277777777777778], [17, 0.0138888888888889], [18, 0.00462962962962963]]

Getting the probability given an outcome:

 (1..21).each{|n| p roll_3d6(Expectation.init).run(n) }
 # >>
 # 0.0
 # 0.0
 # 0.00462962962962963
 # 0.0138888888888889
 # ...

What's really nice is that Simulation, Expectation and Distribution can be reused for other random experiments. Say you get an extra roll if any of the first 3 dice gave a 6:

  def roll_3d6_b(m)
    m.rand(6).in do |d1|
      m.rand(6).in do |d2|
        m.rand(6).in do |d3|
          if [d1, d2, d3].include?(5)
            m.rand(6).in{|d4| m.ret(1+d1 + 1+d2 + 1+d3 + 1+d4) }
          else
            m.ret(1+d1 + 1+d2 + 1+d3)
          end
        end
      end
    end
  end

Here's the distribution we get with roll_3d6_b(Distribution.init).run:

The code for Simulation, Expectation and Distribution is tricky, and I'll make no attempt to explain it now (you are welcome to read it, of course: fuzzy-warm-simulations.rb). The important thing is that these fuzzy warm things only have to be written once, they can be reused, and they allow to interpret the same code (the "random experiment specification") in three different ways, giving the answer to three related problems with one piece of code.

I can drop the m-bomb now. Simulation, Expectation and Distribution are monads. Leave (static) types, monadic laws and category theory aside; this is one of the things monads can do for you even in a dynamically typed, impure language like Ruby: give multiple, non-trivial interpretations to a piece of code to solve several problems at once.

Opening paragraph - Egg Syntax (2008-03-11 (Tue) 08:16:20)

While I appreciate the article and find it well-written in general, your fourth sentence seems to make no sense. There's no previous use of the word "everything," so it's unclear what you're referring to.

mfp 2008-03-11 (Tue) 08:28:22

This is what happens when you do last-minute corrections in the browser. Thanks.

that's a painful way to do this. - Stephen Waits (2008-03-11 (Tue) 14:32:31)

You're dealing with such a small set of possibilities that you'd be much better off just enumerating them all..

So, when rolling three dice, you have an equal probability of rolling any of the following:

 [[1,1,1], [1,1,2], [1,1,3], ... [6,6,4], [6,6,5], [6,6,6]]

--Steve

mfp 2008-03-11 (Tue) 15:14:39

You're of course right: enumerating all the possibilities of the first experiment is trivial, and so is getting the distribution. It is only a bit harder in the second case (not much, admittedly).

At some point, though, you end up reimplementing Distribution for each random experiment, and even before that happens, you have to write different methods for (a) simulating the experiment, (b) obtaining the distribution, and (c) calculating the probability of a given outcome ((c) can always be reduced to (b), of course). So instead of writing ad-hoc code to enumerate all the possible outcomes and generate one, you can reuse the generic Simulation, Distribution and Expectation monads, and solve (a), (b) and (c) with the same piece of code, which acts as the specification of the random experiment and is as clear as it gets modulo the syntax (which I might address later).

Stephen Waits 2008-03-12 (Wed) 12:22:45

Right.. but what I think would be more interesting would be using the same technique you've used here, but using the full enumeration of the population instead.

Solve that problem elegantly and I think you're onto something.

No Title - e (2008-03-12 (Wed) 01:02:21)

Good idea. It would probably be trivial to extent it to be a general statistics package, so it could provide more statistics, tests, etc.

Graphs? - JF (2008-03-12 (Wed) 09:26:49)

What did you use to generate the graphs from those plot/dat outputs?

CPM 2008-03-12 (Wed) 16:12:18

The graphs were generated using gnuplot. http://www.gnuplot.info/faq/

random things - gamelover 911 (2008-04-07 (Mon) 12:53:22)

i just lay in hoping somthing good will happen to me

Last modified:2008/03/11 04:32:58
Keyword(s):[blog] [frontpage] [ruby] [simulation] [distribution] [expectation] [monad]
References:

Referer

Warm fuzzy things for random simulations

Opening paragraph - Egg Syntax (2008-03-11 (Tue) 08:16:20)

mfp 2008-03-11 (Tue) 08:28:22

that's a painful way to do this. - Stephen Waits (2008-03-11 (Tue) 14:32:31)

mfp 2008-03-11 (Tue) 15:14:39

Stephen Waits 2008-03-12 (Wed) 12:22:45

No Title - e (2008-03-12 (Wed) 01:02:21)

Graphs? - JF (2008-03-12 (Wed) 09:26:49)

CPM 2008-03-12 (Wed) 16:12:18

random things - gamelover 911 (2008-04-07 (Mon) 12:53:22)

fybQUCBiSIcm - Bridgestone (2008-05-07 (Wed) 20:46:46)

aDIFaSKNNGhVqvLIq - Fence (2008-05-07 (Wed) 20:46:54)

XEYwFazpgp - Carpet (2008-05-07 (Wed) 20:46:57)

xsoeWlrOXJBAxKnXJPv - Clothes (2008-05-07 (Wed) 20:47:02)

BdBLwUkoxqML - Cookware (2008-05-07 (Wed) 20:47:11)

mdQfcsKSXUItZN - Handbags (2008-05-07 (Wed) 20:47:16)

oEHUWNOVDfW - Michelin (2008-05-07 (Wed) 20:47:19)

PeHwFteszLChz - Shoes (2008-05-07 (Wed) 20:47:26)

DlVTYOnYLkWUC - Xbox (2008-05-07 (Wed) 20:47:32)

Recent

Popular