Fair Chance: Three Things, One Coin to Flip

Date: 03/12/2003 at 09:51:47
From: Marco
Subject: Coin flipping

How can I choose with equity (p = 1/3) among 3 things (door, person,
etc.) having only a (perfect) coin and not infinite time?

Or: How can I generate an event with probability p = 1/3 with one 
perfect coin in a finite number of tosses?

Date: 03/13/2003 at 12:03:14
From: Doctor Achilles
Subject: Re: Coin flipping

Hi Marco,

Thanks for writing to Dr. Math.

Here's my solution (I am pretty sure this is the only way to actually 
do it, but there may be a more elegant solution possible):

You need to flip your coin twice.  The possible outcomes are:

  HH
  HT
  TH
  TT

If you get HH, take the first option. If you get HT, take the second, 
if you get TH, take the third. If you get TT, repeat the process from 
the start.

In this strategy, the probabilities for each of the outcomes are 
equal. You have a 1/4 chance of having to repeat once, a 1/16 chance 
of having to repeat twice, a 1/64 chance of having to repeat 3 times, 
etc.

I cannot guarantee that this strategy will terminate in a finite 
amount of time, but in reality it should terminate fairly quickly.  
Most importantly, you do have exactly a 1/3 chance of each outcome 
when you do reach a termination point.

Hope this helps. If you have other questions or you'd like to talk 
about this some more, please write back.

- Doctor Achilles, The Math Forum
  http://mathforum.org/dr.math/