Tuesday, August 18, 2009

Flipping Coins with Clojure

So... there was a question on Reddit today regarding flipping a series of coins. Quite a bit of dispute arose about the actual phrasing of the question, so rather than plagiarize one of the many suggested variations, I'll spell it out here in plain english.

Bob has a serious problem affecting dozens around the U.S. today. He's a habitual coin flipper. You see... Bob's life fell apart a few years ago after his wife Janet left him, and now he sits around his house flipping coins and writing down how they land. Let's take a peek into Bob's journal for a couple days and see how things have been.

Day 1, Monday:

Woke up today and put some more vaseline on the tip of my thumb. All this flipping has been good, but there's some things that go along with it. Damned blisters keep flaring, and my thumbnail is cracked. Oh well, time to pour us up a drink and see what's what. Today I'll be flipping just to see what the big man upstairs has in store. I'm gonna flip until the sun sets and write it down everytime the coins go head-tails-head.

Day 2, Tuesday:

Well, shit, yesterday was a good time, but all this flippin' just makes me wanna flip more. Time to pour us up a drink and see what ol' mister flipper has ready for me. I'm gonna flip till my flipper-flapper is all tuckered out and write it down everytime the coins go head-tails-tails.

If Bob only knew what Clojure could do for him, he could get his old life back, and Janet and the kids would come home, but I digress... Let's explore Bob's habit and try to answer the following question: "In an infinite sequence of coin flips, which pattern will occur more often: HTH or HTT?" (ok... so I plagiarized a little).

We'll start off by defining the patterns we're looking for and the number of samples we want to take. In this case, we'll be representing a head as zero and a tail as one.
(def head-tail-head [0 1 0])
(def head-tail-tail [0 1 1])
(def num-samples 100000)
Next we'll need a function to flip the coin and calculate the average number of tries before Bob cracks the champagne.
(defn flip-coin []
  (rand-int 2))

(defn avg [coll]
  (/ (apply + coll) (count coll)))
Super easy so far, right? If only Bob knew... Now for something slightly more advanced, our main worker function, which I'll break down in pieces.
(defn num-flips-to-match-pattern [pattern]
  (let [coin-flips (repeatedly flip-coin)]
    (loop [x 0]
      (if (= pattern (nth-flip-sequence x coin-flips))
        (+ 3 x)
        (recur (inc x))))))
This function takes a given pattern and returns the number of flips required to match the pattern. The flipping is obviously random, but with a large enough sample size, some pattern should emerge. Side note: I add three to the return result because it takes a minimum number of three flips to get a valid result and we're starting with zero (offset math FTW).

To make sure we have enough coin flips at our disposal, we'll generate them from an infinite lazy sequence (on line #2). Clojure makes these kinds of infinite sets trivial to define, and they can be very convenient when you're not sure how much data you'll need.

Next up you'll see a yet to be defined function, nth-flip-sequence. I would have defined it up above, but it makes better sense in context, so I'll define it now.
(defn nth-flip-sequence [x coin-flips]
  (nth (partition 3 1 coin-flips) x))
The nth-flip-sequence function takes an offset and an infinite sequence (in this case a sequence of coin flips). From here, it uses partition to grab three elements with a step of one. As an example, it would break up a dataset as follows.
(def coin-flips [0 1 1 0 0 1 1 1])
(nth (partition 3 1 coin-flips) 0)
(0 1 1)
(nth (partition 3 1 coin-flips) 1)
(1 1 0)
(nth (partition 3 1 coin-flips) 2)
(1 0 0)
As usual, Clojure has some powerful batteries included to do most of the work for us. With the hard part out of the way, we write a function to average the number of flips required to match a given pattern for a specified number of samples.
(defn take-samples [pattern num-samples]
  (float (avg (for [x (range num-samples)]
                   (num-flips-to-match-pattern pattern)))))
We'll go ahead and define Bob's two incredibly fulfilling days.
(def monday (future (take-samples head-tail-head num-samples)))
(def tuesday (take-samples head-tail-tail num-samples))
If you noticed the future function above, good eye. Bob likes to get things done fast, so this is a trivial way to calculate both days in parallel. We are using Clojure afterall...

After this, we simply print the results and cleanup the thread pool (since we used future).
(println "mon: " @monday)
(println "tue: " tuesday)
(shutdown-agents)
A sample run confirms that the reasoning in the original article is sound and hopefully brings Bob some peace.

mon:  10.03817 # avg num of coin flips to hit head-tails-head
tue:  8.00416 # avg num of coin flips to hit head-tails-tails

16 comments:

  1. Very nice, it was interesting to see a seq based approch to this.

    I gave it a go too using a simple recursive method.

    http://paste.lisp.org/display/85722

    James

    ReplyDelete
  2. @James - Functional programming at it's best! I love the simplicity and speed of your solution. Thanks for swinging by and contributing.

    ReplyDelete
  3. I've noticed that you take overlapping groups for patterns whereas James takes groups which are not overlapping.
    Oh well, I guess in an infinte sequence this wouldn't affect much

    ReplyDelete
  4. This particular papers fabulous, and My spouse and i enjoy each of the perform that you have placed into this. I’m sure that you will be making a really useful place. I has been additionally pleased. Good perform! http://myspinfree.com

    ReplyDelete
  5. Thank you because you have been willing to share information with us. we will always appreciate all you have done here because I know you are very concerned with our. victariosacuity

    ReplyDelete
  6. Really I enjoy your site with effective and useful information. It is included very nice post with a lot of our resources.thanks for share. i enjoy this post. astramentis

    ReplyDelete
  7. I haven’t any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us. victariosacuity

    ReplyDelete
  8. I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. nightshold

    ReplyDelete
  9. This particular is usually apparently essential and moreover outstanding truth along with for sure fair-minded and moreover admittedly useful My business is looking to find in advance designed for this specific useful stuffs… padkrapaw

    ReplyDelete
  10. This is my first visit to your web journal! We are a group of volunteers and new activities in the same specialty. Website gave us helpful data to work. http://pestadomino.com

    ReplyDelete
  11. This is my first time visit to your blog and I am very interested in the articles that you serve. Provide enough knowledge for me. Thank you for sharing useful and don't forget, keep sharing useful info: https://cmcpoker.bid

    ReplyDelete
  12. This is my first visit to your web journal! We are a group of volunteers and new activities in the same specialty. Website gave us helpful data to work. http://cmcpkr.org

    ReplyDelete
  13. I like your post. It is good to see you verbalize from the heart and clarity on this important subject can be easily observed... https://cmcpkr.net/

    ReplyDelete
  14. This is my first visit to your web journal! We are a group of volunteers and new activities in the same specialty. Website gave us helpful data to work. https://iturajaqq.club

    ReplyDelete
  15. Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.Thanks https://rajaqqpro.cc

    ReplyDelete
  16. You there, this is really good post here. Thanks for taking the time to post such valuable information. Quality content is what always gets the visitors coming. slot live22

    ReplyDelete