One puzzle was how to get a uniform distribution of heads and tails (or 1s and 0s) from a coin with a known bias. The example I used was a coin that comes up heads 1/3 of the time and tails 2/3 of the time. There are many algorithms that could be applied to solve this puzzle. One way to generate a uniform distribution is to “chunk” together multiple tosses. In this case, throw the coin twice. If it comes up heads both times, throw over. If both tosses are tails, record a tail. If one is a head and one a tail, record a head. The rationale behind this method is that given the conditions, with two throws, both will be heads 1/9 of the time. The other two possibilities will each occur 4/9 of the time, or equally.

If the coin is biased to come up heads only 1/4 of the time, this method requires throwing the coin three times. If two or more of the throws are heads, then discard and throw over. If one is heads, the call the answer heads. If they are all tails, then call the answer tails.

Do you see the underlying pattern why this works?

With a finite number of tosses, methods such as this can be generalized to any coin biased by a rational number, but this method would require an infinite number of the tosses for each result if the coin is biased by an irrational number.

Is there a way to solve the problem with an irrational bias in a finite number of throws?

Now here is a surprising twist. The coin has no memory. Each throw is unrelated to any other. Therefore we need not throw the coin multiple times for each reading. We simply need to throw it and record the sequence of head and tails as they occur. Then use adjacent overlapping sequences to derive the output of evenly distributed heads and tails. At first you might think this is wrong and will not result in an unbiased distribution because a single coin toss might be used more than once. But each toss is independent. Even more wild is the fact that you don’t need to use the sequence in order. Given the sequence of biased results, you can pick the results of tosses at random and apply the same algorithm. Of course if you had an unbiased way to select the tosses to use, then you wouldn’t need this algorithm-or would you?

The second part of the problem was to do the inverse and create a biased distribution from an evenly distributed one. This was a bit of a cheat since it is really the same problem. The issue really is to generate an output of 1s and 0s with a desired average distribution given an input sequence with a known distribution.

The last problem used cubical dice: What are the most likely numbers to be generated by throwing N normally-marked cubical dice? What is the probability of getting a total value of (N+1)? For extra credit, what is the probability of throwing the most likely number if N is even?

We’ll let the extra credit go for a while because I know some people are still working on it. However, the most likely number thrown can be shown to be 3.5N if N is even. If N is odd then the answer is almost the same. In that case, two numbers are equally likely to come up and both are more probable than any other. These numbers are obtained by rounding both up and down the same 3.5N.

The probability of the total being N+1 is simply N/(6 exp N). Obviously the probability of the total being N is 1/(6 exp N). That is, a 1 must come up on every single die. The probability of that happening is (1/6)(1/6)…

Just by looking at the increase in probability going from a total N to (N+1) along with the decreasing probability of throwing either as N increases should indicate that the probability of throwing the most likely number becomes much higher as N increases. In fact for very large values of N, one almost always throws the same number within a very small range.

For those who wish to delve further into decision theory without wading through a lot of equations, I have posted a tutorial on elementary decision theory. It shows examples of faulty physicians’ diagnoses (important for those considering surgery) and how to evaluate anti-terrorist activities (important for everyone). That tutorial can be found here.