Even Or N-Even?

A few columns ago I discussed a method to generate uniformly distributed (i.e. equally probable) random numbers from 1 – 40 from throwing two 20-sided dice. A few minutes thought will show you that the distribution of numbers obtained by simply adding the results of the two dice will not result in a uniform distribution. The game of craps is built around this non-uniform distribution of results when throwing two cubes. The number seven is more likely to come up than any other number.

But in reviewing that puzzle, I was reminded of a similar one that had been posed to me in college. Suppose you want to generate a random binary series. An easy way is to do that is to simply throw a fair coin and count a head as 1 and a tail as 0. A fair coin is one that has equal chances of coming up heads or tails.

But suppose you had an unfair coin with a known bias. That is, assume it comes up heads 1/3 of the time and tails 2/3 of the time. But you still want to generate a uniformly distributed series of 1s and 0s. How can you do it?

Will your system work for other degrees of unfairness such as 1/4 and 3/4 etc?

Can a practical system be developed that works for any degree of unfairness?

That’s the first half of the problem. The second half is probably easier. Given a fair coin, suppose you want to generate a biased binary string such that the results are 1s on the average only 1/3 of the time and the rest of the time are 0s.

Will your system work for other values of bias?

Can that system be generalized to work with any desired ratio?

Could you use a random number generator with a known distribution to perform calculations? (Hint: see previous articles.)

Finally, 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?

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.