|
When flipping a coin to make important decisions in life you can flip once to choose between 2 possible outcomes. (Heads I eat cake, Tails I eat chocolate!) You can also flip twice to choose between 4 outcomes. (Heads-Heads, Tails-Tails, Heads-Tails, Tails-Heads) Can you use a coin to choose evenly between three possible choices? If so how? (Ignoring slight abnormalities in weight) |
|||||||||||||||
|
|
If you throw your coin $n$ times you have $2^n$ outcomes, the probability of each of which is $\frac{1}{2^n}$. The larger $n$ is, the better you can divide $2^n$ into three approximately equal parts: Just define $a_n=[2^n/3]$ and $b_n=[2\cdot 2^n/3]$, where $[\cdot]$ denotes rounding off (or on). Since $\frac{a_n}{2^n}\to\frac{1}{3}$ and $\frac{b_n}{2^n}\to\frac{2}{3}$ as $n\to\infty$, each of the three outcomes "the number of Heads is between $0$ and $a_n$", "the number of Heads is between $a_n$ and $b_n$", and "the number of Heads is between $b_n$ and $2^n$" has approximately the probability $\frac{1}{3}$. Alternatively, you could apply your procedure to get four outcomes with the same probability (Heads-Heads, Tails-Tails, Heads-Tails, Tails-Heads) to your problem in the following way: Associate the three outcomes Heads-Heads, Tails-Tails, Heads-Tails with your three possible choices. In the case that Tails-Heads occurs, just repeat the experiment. Sooner or later you will find an outcome different from Tails-Heads. Indeed, by symmetry, the probability for first Heads-Heads, first Tails-Tails, or first Heads-Tails is $\frac{1}{3}$, respectively. (Alternatively, you could of course throw a die and select your first choice if the outcome is 1 or 2, select your second choice if the outcome is 3 or 4, and select your third choice if the outcome is 5 or 6.) |
|||||||||||
|
|
A simple (practical, low-computation) approach to choosing among three options with equal probability exploits the fact that in a run of independent flips of an unbiased coin, the chance of encountering THT before TTH occurs is 1/3. So: Flip a coin repeatedly, keeping track of the last three outcomes. (Save time, if you like, by assuming the first flip was T and proceeding from there.) Stop whenever the last three are THT or TTH. If the last three were THT, select option 1. Otherwise flip the coin one more time, choosing option 2 upon seeing T and option 3 otherwise. |
|||
|
|
|
EDIT Oh dear, Rasmus has extended his answer and rendered this one obsolete! In fact, stop reading this right now and go see what he has done. I interpret what you are asking as trying to find a way to decide without introducing bias (as would be introduced by counting tails-heads as the same as heads-tails). Rasmus's suggestion of repeating the experiment for a certain configuration seems the best choice. I drew a little tree and tried to group outcomes into three "equally-likely" sets and then realized this is impossible because $3$ does not divide $2^n$ for any $n$. (The quantity $2^n$ being the number of unique outcomes after $n$ "flips".) |
|||
|
|
|
Here's another method: consider H to be 0 and T to be 1. Consider the results that you get from your coins as successive bits (after the binary point) in a binary number. Assign numbers in the interval [0, 1/3) to the first choice; [1/3, 2/3) to the second choice; [2/3, 1) to the third choice. Flip coins until you know, no matter what happens on the remaining flips, in which of these intervals the resulting real number in [0, 1) will lie. More concretely, this means that if you flip two coins and observe HH, make the first choice; no matter what happens the result will be between .0000... = 0 and .001111... = 1/4. Similarly if you observe TT, make the third choice; the result will be between 3/4 and 1. If you observe HT, you can't commit to a choice yet; the result will be between 1/4 and 1/2, which overlaps two of the intervals. Something similar is true for TH. In either case flip a third time. HTT corresponds to the interval [3/8, 1/2) which lies entirely in [1/3, 2/3), so HTT corresponds to the second choice; similarly for THH. If you see HTH you're still undecided between the first and second choices; THT is still undecided between the second and third. Continuing in this way, HTHH corresponds to the first choice, HTHT and THTH are still undecided, THTT corresponds to the third choice. In general, for the cut-points 1/3 and 2/3, you flip coins until you get either two heads or two tails in a row. If you first get two heads in a row, this corresponds to the first choice if the initial flip was a head, the second if the initial flip was a tail. If you first get two tails in a row, this corresponds to the second choice if the initial flip was a head, the third choice if the initial flip was a tail. You might wonder how many flips this takes, on average, to give a result. With probability 1/2 you get a result on the second flip; with probability 1/4, on the third flip; with probability 1/8, on the fourth flip, and in general with probability $1/2^{n-1}$ for $n \ge 2$. The sum $\sum_{n \ge 2} n/2^{n-1}$ has value 3, so on average this method takes three flips. This is a bit slower on average than the method Rasmus suggested, which takes on average 8/3 flips. However, the same method works even if the three choices are not equally likely! (It won't have such a clean way of being expressed as "flip until you get two in a row", though.) |
|||
|
|
|
If you are at a crossroads in life requiring you to choose one of three options, then coin tossing is not the correct thing to do. Rather, pick up a dice and roll it. Go for first option if the diece turns up 1 or 2. Go for second option if the dice turns up 3 or 4. Go for the third option if the dice turns up 5 or 6. Edit: Oops, I saw that Rasmus already gave this option. Anyway I strongly suggest that you prefer this one to the other two methods given by him. |
|||||||||||||||||
|
