Throwing dice with ClojureOctober 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:
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:
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 🙂