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 X_i.

Consider the random variable Y_n defined as:
Y_n = \frac 12 + \frac 12 \left(\prod_{i=1}^n X_i\right)

Notice that Y_n 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 Y_n is:
E\left(Y_n\right) = E\left(\frac 12 + \frac 12 \left(\prod_{i=1}^n X_i\right)\right) = \frac 12 + \frac 12 \,E\left(\prod_{i=1}^n X_i\right)

Because the X_i. are statistically independent, we can exchange the order of product and expectation:
E\left(\prod_{i=1}^n X_i\right) = \prod_{i=1}^n E\left(X_i\right) = \prod_{i=1}^n (p-q) = (p-q)^n

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.