Tuesday, October 11, 2005
Saturday, October 08, 2005
You have three items (call them 'a', 'b' and 'c') that you want to choose any one from without bias. If you had a fair three sided die, you could assign an item to each side of the die, then simply toss the die once and pick the item that it lands on.
However, you don't have such a fair three sided die. Instead, you have a fair two sided coin. Note: 'fair' means 'there is an equal chance of coming up heads or tails'. Can you come up with an algorithm that uses said coin in order to pick any one of those items with equal probability?