The Perfect Coin
Do you ever have decision problems? Which of the two options should I use? Well, I do, and when I’m in the mood, I use a coin to decide. It’s rather funny, too. Randomize your life. But there is a problem with this approach. Sometimes, you have more than two options. Maybe three. Now, how do you decide between three options? A die comes to mind, but I don’t usually have one with me. Anyways, this is an incredibly important problem of course, hence I asked around. Yesterday, someone told me about a solution.
Psykotic of #scheme mentioned there’s a simple kind of monte carlo algorithm. You just flip a coin a number of times, and make the result be the bits of a natural number. If the number is too big, repeat. This way, you get an evenly distributed random number. And of course, you only have to flip the coin max(log2(n)) times. Nice!
So the next time I have to decide whether to walk, take the bus, or walk half the distance and take the bus the other half, I know what to do—I just take out my perfect coin and… Hey wait. Perfect coin, yes? Another problem. Luckily, Psykotic knew a solution to this problem as well. Assuming your coin is biased towards one side, and doesn’t change its mind every other minute, and of course isn’t completely biased—it should land on either side at least some of the time—it’s possible to use this coin to fake a perfect coin.
You throw it twice, and use the second result as the result of the perfect coin, but only if the first result was different. If not, repeat. Let p be the chance of a head result, so 1-p is the chance of a tail result. The probability of head, tail is p(1-p) and that of tail, head is (1-p)p, which is of course equal, so we got a perfect coin.
Not only does this solve my indecision problems, it also means I always a perfect coin with me! Thanks, psykotic!
