## Throwing dice with Clojure

October 16, 2010 at 8:56 pm | Posted in Clojure, Programming | 9 CommentsRecently 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:

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:

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:

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

### Leave a Reply

Create a free website or blog at WordPress.com.

Entries and comments feeds.

[…] 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 […]

Pingback by Tweets that mention Throwing dice with Clojure « Maurits thinks aloud -- Topsy.com— October 16, 2010 #

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

Comment by uhrm— October 17, 2010 #

Great suggestion. Thanks!

Comment by maurits— October 17, 2010 #

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

Comment by Wilfred Springer— October 19, 2010 #

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 😉

Comment by maurits— October 19, 2010 #

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

Comment by Wilfred Springer— October 19, 2010 #

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.

Comment by Wilfred Springer— October 19, 2010 #

I’ll bite here.

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

Comment by Kroma— October 19, 2010 #

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

Comment by Kroma— October 19, 2010 #