Say you have a coin and you want to randomly select between 3 numbers (or more) with equal probability. If you just flip a coin for each pair then you are giving the survivor of the first round two chances to lose and the distribution is not uniform.
In general you have a function Random(0,1) that returns 0 with .5 probability and 1 with .5 probability. Using this function, make Random(a,b) which returns any integer in the range [a,b] with equal probability.
Any ideas?
It's easier to generate a Random(0,3) given a Random(0, 1). Random(0, 3) can be simulated by two consecutive coin tosses to generate four buckets: 00, 01, 10, 11.
In general, Random (0, 2^n-1) is trivially easy to generate given Random(0, 1) [i.e. a fair coin]. Any other Random(0, n) is going to be difficult to generate, and not truly "random" -- because you'll have to predetermine the number of results you want to consider as belonging to the "other" buckets.
You could nearly fake Random(0,2) like this (Ruby-like pseudocode):
options = ['h', 't', 'n'] # heads, tails, neither
hash = {'h' => 0, 't' => 0, 'n' => 0} # number of 'heads', 'tails', 'neither'
rand = options[random(0, 1)]
rand = 'n' if (hash[rand] % 3 == 2) # every third 'h' or 't' is an 'n'
hash[rand] ++ # update buckets
Again, this is not 'random' since every third head or tail is considered a 'neither'.
UPDATE: See the related question for a more elegant answer. Creating a random number generator from a coin toss
