Throwing dice with Clojure

October 16, 2010 at 8:56 pm | Posted in Clojure, Programming | 9 Comments

Recently I needed a mathematical expression for the expected value for the minimum out of n draws from a normal distribution. For example when you take only 1 sample (n = 1) every time, the minimum is the value itself. So the expected value (if I repeat this an infinite amount of times) is the average of the normal distribution, being 0.

If I sample an infinite number (n = ∞) of times, the minimum of all those samples is going to be -∞. I didn’t find an expression for n>1 samples and wasn’t able to derive it myself easily.

I decided to tackle an easier problem first: what is the expected minimum when I throw n (6 sided) dice? When you throw 1 dice at a time, the solution is easy. Each side has an equal chance. The distribution looks like this:

Possible outcomes with 1 dice

And the expected value is (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.5

For 2 dice it is still easy to calculate the expected value for the minimum. There are 11 combinations for which the minimum is 1, 9 combinations for which the minimum is 2 and so on. There is only 1 combination for which the minimum is 6: you have to throw 2 sixes. When you plot the chances it looks like this:

Possible outcomes with 2 dice
For three it becomes already quite boring to write out all (216) combinations just to calculate the minimum and actually I didn’t The graph however looks like this:

Possible outcomes with 2 dice

As you can see the chance of having a lower value (1 or 2) as minimum quickly increases. Calculating all combinations on paper starts to get boring pretty fast, so I thought of writing a Clojure program that would do that for me. However I soon realized that the combination space this program had to walk becomes pretty huge when you take a larger number of dice. For 10 dice we are already talking 6^10 possible combinations. My next step was to capture this in a neat formula first. Remembering some of my statistics classes from university I came up with the following formula to calculate the possible number of combinations where x (1 <= x <= 6)  is the outcome for the minimum:

The expected value now simply becomes:

 

I took this formula as the basis for the following implementation in Clojure:

(defn ! [x] (if (= x 0) 1 (* x (! (dec x)))))

(defn m-over-n [m n] (/ (! m) (* (! (- m n)) (! n))))

(defn pow [x y] (Math/pow x y))

(defn term [x m n] (* (m-over-n m n) (pow (- 6 x) (- m n))))

(defn comb [d x] (reduce + (map #(term x d %) (range 1 (inc d)))))

(defn e-min-seq [n] (map #(* (comb n %) %) (range 1 7)))

(defn e-min [n] (/ (reduce + (e-min-seq n)) (pow 6 n)))

It turns out that most of my Clojure code is a collection of one-liners. Line 1 defines the exclamation mark (!) as a function that calculates the factorial of a number. This is a straightforward definition that doesn’t use tail recursion so it will run out of stack space for large values of x. For our goal it is sufficient. Line 3 defines the binomial coefficient. Again there are more efficient ways to calculate this. Line 9 and 13 both use reduce to calculate the two sums as seen in our formula.

Although this code gave me the expected result I still wasn’t completely happy with it. I stepped back to the drawing board in order to get a simpler formula. Our formula can be rewritten as:

Which in turn can be further simplified as:

and finally:

This final formula is coded in Clojure as:

(defn sum [n] (reduce + (map #(pow % n) (range 7))))

(defn e-min [n] (/ (sum n) (pow 6 n)))

The graph of the expected minimum now looks like this:

 

This whole solution now could fit into a one-liner. This exercises proofs two things to me: 1) it really helps to think about your solution before starting to code and 2) every Clojure solution always fits in one single tweet🙂

9 Comments »

RSS feed for comments on this post. TrackBack URI

  1. […] This post was mentioned on Twitter by Brofski Tech, Planet Clojure and Yvonne van der Laak, Maurits Rijk. Maurits Rijk said: Posted blog about throwing dice in Clojure: http://bit.ly/aDpCXE Derived formula to calculate expected minimum when throwing n dice […]

  2. You might be interested in http://www.applet-magic.com/samplemax3.htm.

    • Great suggestion. Thanks!

  3. The Scala solution:

    def sum(n: Int) = (0 to 6) map(pow(_,n)) reduceLeft(_+_)
    def emin(n: Int) = sum(n) / pow(6, n)

    … that is, if I leave out the import, as you did.😉

    import scala.math.pow

    • In Clojure the standard Java libraries are loaded implicitly. This makes the Clojure solution 2 lines, while the Scala solution is 3 lines. This conclusively proofs that all Clojure code is one third smaller than Scala code😉

      • Grrrr – at the other hand, your code doesn’t work in my Clojure repl without typing Math/pow

      • O, and it’s not even 20%. And I notice you used Math.pow and not something that works on BigInteger. In that case, your Clojure code would grow significantly.

      • I’ll bite here.

        The Scala code is typesafe whereas the Clojure code is not.😛

    • You can replace `reduceLeft(_ + _)` by `sum`, and `scala.math` by just `math`.🙂


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: