Here’s a problem I ran across on the CompSci Stack Exchange. Suppose you have a biased coin that comes up heads with probability p. You don’t know what p is, but assume it is neither 0 nor 1. How can you use the coin to simulate a fair coin, i.e. one that produces heads with probability very close to 1/2?

The procedure is surprisingly simple. To produce one “fair” toss, you toss the biased coin n times, and count the number of heads. If the count is even, the result is heads, if odd, tails. The value of n needed will depend on the bias of the coin, but typically something like n=20 will suffice.

Lazy sequences provide a simple and elegant way to build probabilistic models of coin tossing.

As seen above, eyeballing a few tosses is not going to suffice to distinguish fair coins from unfair. We’ll need to collect some statistics.

Here’s how we use repeated tosses to simulate a fairer coin.

Notice the oscillation in the sequence of sample means. To understand where it’s coming from, imagine flipping a coin that always comes up heads, an evil coin. The parity of the number of heads observed is exactly correlated to the parity of the blocksize n in our *unbias* function. This causes our scheme to fail miserably for evil coins, as below.

With a highly biased (but not evil) coin we see much the same oscillation for small blocksize n. If we track the sample means over a contiguous range of blocksizes n, high sample means alternate with low sample means. Regardless of these oscillations, as n grows, the sample means does converge to 1/2. Can we prove it?

It is convenient to the coin as a random variable X which assumes values 1 and -1 with probabilities p and q=1-p respectively. Flipping the coin repeatedly results in a sequence of independent, identically distributed random variables

Consider the random variable defined as:

Notice that takes on values 0 and 1, depending on the parity of the number of heads seen in n coin tosses, exactly as in *unbias* function.

The expected value of is:

Because the are statistically independent, we can exchange the order of product and expectation:

Since |p-q| < 1, the term (p-q)^n converges to zero as n increases, and done. I'll close by pointing out a couple of potential pitfalls of using lazy sequences to model coin tossing. Both are easily avoided. Here's the first. A given coin is a fixed sequence. Each time I look at the first 10 elements they are the same. Make new coins as required.

Don’t do this: The sequence *fair* is now a million elements long and won’t be garbage collected as long as you hold a reference to its head. If you must name a coin, try to do it inside a let block so that it will be garbage collected when the let block falls out of scope.

Neat solution, and a nice illustration of it.

Your definition of make-coins is a nice example of building a lazy seq by hand (which I gather is part of the purpose of this post), but it’s worth noting that a more succinct definition could use repeatedly, which returns a lazy seq:

(defn make-coins [prob-heads]

(repeatedly #(if (< (rand) prob-heads) 1 0)))

Also – the notation in your proof shows the markup and not the actual rendering. Think that's a deficiency on my side, or is something else missing?

September 30, 2010 @ 12:45 pm

I like your suggestion of using

repeatedlyto definemake-coins. It is more idiomatic Clojure than my version, both shorter and clearer. It’s funny, I have used therepeatedlyfunction often enough that I should have thought to use it here. But old habits can get ingrained so deeply that sometimes you don’t see them. I think the explicit use of cons was a scheme habit of thought popping through. Thanks for the heads-up.Re not seeing the actual rendering, I definitely see the TeX rendered. Out of curiosity I checked my site with various browsers, from linux using FF and Chrome, and from a Windows box using FF, Chrome, and IE. The TeX rendered nicely in all of them. My best guess is your browser may be missing some math fonts. Try a google search for something like “${your_browser} TeX MathML font”, and see what pops up.

September 30, 2010 @ 6:47 pm