24
$\begingroup$

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)

$\endgroup$
  • 5
    $\begingroup$ See also: math.stackexchange.com/questions/1333/… $\endgroup$ – Isaac Aug 13 '10 at 15:55
  • 4
    $\begingroup$ @Isaac: Your link is an exact duplicate. Why wasn't this question closed? $\endgroup$ – Casebash Aug 13 '10 at 23:39
  • $\begingroup$ Meta discussion here: meta.math.stackexchange.com/questions/619/… $\endgroup$ – Tom Boardman Aug 14 '10 at 0:08
  • $\begingroup$ find a coin with a large edge, so that the probability it falls on the edge is 1/3. now you only need one toss :) $\endgroup$ – user20963 Dec 10 '11 at 6:05
  • $\begingroup$ @Nico: Or just flip a coin in a world where 2 = 3... not very useful answer. $\endgroup$ – The Chaz 2.0 Dec 10 '11 at 10:11
20
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Can't you count tails-heads as the same as heads-tails? $\endgroup$ – Tyler Hilton Aug 13 '10 at 15:26
  • 6
    $\begingroup$ @Affan, it would not be fair as that possibility would occur with the same probability as the other two combined. $\endgroup$ – Joshua Shane Liberman Aug 13 '10 at 15:35
  • $\begingroup$ Oh I get ya, thanks! $\endgroup$ – Tyler Hilton Aug 13 '10 at 17:15
  • $\begingroup$ I think what Rasmus meant (in the second part) is that you would always toss in pairs and take into account the order of the two tosses: only if the first toss (of a pair) is tails and the second toss is heads toss the coin another two times. $\endgroup$ – Andre Holzner Aug 19 '10 at 18:58
11
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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".)

$\endgroup$
4
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Hm. I've been thinking about such a 'clean' generalisation that's easy to interpret in a real setting with a minimum of pre-computation. If I have a unbiased coin and want to produce a rational probability (say $p/(p+q)=1/3$), I can give two parties $p,q$ tokens and repeatedly pit them all-in against each other, the outcomes being decided by the coin. This method relies on (A) the first party's winning with chance $p/(p+q)$ contingent upon the game's terminating, and (B) the game's terminating with probability 1 (since, e.g., any string of $\lceil \log_2(p+q) \rceil$ flips in a single $\endgroup$ – Vandermonde Nov 25 '18 at 21:55
  • $\begingroup$ party's favour is decisive). (Then a $(1/3,1/3,1/3)$ distribution can easily be done iteratively by taking players two at a time, winner of last round vs. a new player. Possibly doable with a 3-sided coin and side pots, but I don't want to think about it.) If the desired probabilities are incommensurable then (B) still feels true despite not being so obvious (a player may survive arbitrarily close to ruin so in principle many doublings might be needed to end it). Maybe I'll post a question. $\endgroup$ – Vandermonde Nov 25 '18 at 21:55
2
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Well, from the philosophically view-point, I think it's inadvisable to use random experiments for decision making anyway. $\endgroup$ – Rasmus Aug 13 '10 at 15:57
  • $\begingroup$ True, true. But if at all someone does a random experiment for decision making, better do one that will get done in the shortest time! So your third method is more time-saving compared to the other two. $\endgroup$ – user1119 Aug 13 '10 at 16:02
  • 6
    $\begingroup$ @Rasmus: From a game-theory viewpoint, it often is advisable to use a random method to make decisions. :) $\endgroup$ – Larry Wang Aug 13 '10 at 16:40
  • $\begingroup$ @Kaestur Hakarl: Well... Touché! :) $\endgroup$ – Rasmus Aug 13 '10 at 16:53
  • 3
    $\begingroup$ One of Piet Hein's grooks comes to mind: A PSYCHOLOGICAL TIP Whenever you're called on to make up your mind, and you're hampered by not having any, the best way to solve the dilemma, you'll find, is simply by spinning a penny. No -- not so that chance shall decide the affair while you're passively standing there moping; but the moment the penny is up in the air, you suddenly know what you're hoping. $\endgroup$ – Bob Durrant Sep 15 '10 at 20:49
2
$\begingroup$

I think I have a pretty good idea where you don't have to redo at all.

flip the coin to decide a side for the first two possibilities. if heads come up, its heads for option 1 and tails for option 2 or vice versa flip again to decide a side for option 3. hence, we have 3 outcomes of a coin for 3 possibilities, and all three are not the same. example: H for 1, T for 2 and T for 3, but not H or T for all 3 options.

now flip again. if the coin lands on heads, and heads is only on say, option 1, then option 1 wins. if H is on 2 options, select those 2, keep heads for 1 and tails for the other, flip again and decide. the same is applicable if it lands on tails.

I hope you understand how it works and how each option has an equal chance of getting selected.

you don't have to redo your flips anywhere here. (there is a definite answer).

$\endgroup$
  • $\begingroup$ An interesting idea, but I don't think it works. Option 3 is guaranteed to match one of the first two options. It will never be the lone-H or lone-T, and thus will never be selected by the first flip. Option 1 or Option 2 are thus more likely to be selected. $\endgroup$ – Nathan Kurz Mar 22 '14 at 17:46
2
$\begingroup$

Consider a similar problem and answer first that happens for our gaming group: If you have a die and need a choice from 1-5, how do you do it? One way is to roll the die and re-roll if you get a six. The advantage of this method is that in a noisy group of drunken people you won't get an objection that one outcome is favored over another.

In the same vein, people are apt to readily acknowledge there are 4 possibilities for a coin flipped twice (or flip two different coins such as a sickle and a knut at once). In the case that both sickle and knut come up tails, flip both again until you have one of the other three outcomes.

$\endgroup$
1
$\begingroup$

I prefer a method based on a simple unbalanced game: the first person to throw heads wins. In this game, the person who throws first has a $\frac 23$ chance of winning, the other has a $\frac 13$ chance of winning.

To decide fairly between three outcomes, simply put two outcomes on one team in this game, so they have a $\frac 23$ chance of getting picked. If this team of outcomes wins, simply toss another coin to decide between them. If the other team wins, there is only one outcome on that team and so no further tosses are needed.

This method is equivalent to Rasmus's "alternatively" answer, and will take $2{\frac 23}$ coin tosses on average. I don't think there exists a method with fewer average coin tosses, but I have no proof of this.

$\endgroup$
1
$\begingroup$

Here's my method. Like voltrevo's method the expected number of tosses is also only $2\frac{2}{3}$.

In order to explain this easily, lets say there are three people named p1, p2 and p3. If the coin comes up heads on the first flip then p3 looses and p1 and p2 flip to decide who wins. However, if it comes up tails on the first flip then you keep flipping until you get either two tails in a row or two heads. If it's two tails then p3 wins, and if it's two heads then p1 and p2 flip to decide who wins again.

To see why this works, lets first find the probability that p3 loses. This can happen in the following ways where something like TTH represents tails followed by tails followed by heads. The probability of each case is also shown next to the case:

H = $\frac{1}{2^1}$

THH = $\frac{1}{2^3}$

THTHH = $\frac{1}{2^5}$

THTHTHH = $\frac{1}{2^7}$

THTHTHTHH = $\frac{1}{2^9}$

...

In each new case we see that two new flips must be added, and so the probability of any one of these cases happening (ie the probability that p3 looses) can be given by the following geometric sum:

$$\sum_{n=0}^{\infty}\left(\frac{1}{2}\right)^{2n+1}$$

Solving this sum:

$$\sum_{n=0}^{\infty}\left(\frac{1}{2}\right)^{2n+1}=\frac{1}{2}\sum_{n=0}^{\infty}\left(\frac{1}{2}\right)^{2n}=\frac{1}{2}\sum_{n=0}^{\infty}\left(\frac{1}{4}\right)^n=\frac{1}{2}\cdot\frac{1}{1-\frac{1}{4}}=\boxed{\frac{2}{3}}$$

From this we see that the probability of p3 losing is $\frac{2}{3}$ which means he has a $\frac{1}{3}$ chance of winning, and there is a $\frac{2}{3}$ chance of either p1 or p2 winning. So by having p1 and p2 flip an additional time whenever p3 loses they split this $\frac{2}{3}$ chance among each other giving each person a $\frac{1}{3}$ chance of winning.

Finally, we can make a probability model for the number of tosses in a given game. Here is a table which represents the number of tosses (x), the cases which yielded them and the probability of obtaining them (p(x)).

$$\boxed{ \begin{matrix} x & 1 & 2 & 3 & 4 & 5 & 6 & ...\\ Case & N/A & H,TT & N/A & THH, THTT & N/A & THTHH,THTHTT & ... \\ p(x) & 0 & \left ( \frac{1}{2^1}+\frac{1}{2^2} \right ) & 0 & \left ( \frac{1}{2^3}+\frac{1}{2^4} \right ) & 0 &\left ( \frac{1}{2^5}+\frac{1}{2^6} \right ) & ... \end{matrix} }$$

You can see that all of the even numbers have two cases and these two cases correspond to P3 loosing and P3 winning respectively. Analyzing the pattern we can make a general formula for the probability of the game ending in x flips where x is an even integer: $$p(x)=\left ( \frac{1}{2^{x-1}}+\frac{1}{2^x} \right )$$

Using this formula, we can find the expected number of tosses. $$\mathbb{E}(x)=\sum_{x=0}^{\infty}\left(2x\right)\left(\frac{1}{2^{\left(2x-1\right)}}+\frac{1}{2^{2x}}\right)=\sum_{n=0}^{100}\frac{n}{4^{n-1}}+\sum_{n=0}^{100}\frac{n}{2^{2n-1}}$$

To find the value of these sum, we will first consider the general case of the geometric series and take the derivative of both sides. $$\frac{d}{dx}\sum_{n=0}^{\infty}x^n=\frac{d}{dx}\frac{1}{1-x}$$ $$\boxed{\sum_{n=0}^{\infty}nx^{\left(n-1\right)}=\frac{1}{\left(1-x\right)^2}}$$

You can then see that the above two sums are just special cases of this formula and so we get that: $$\mathbb{E}(x)=\sum_{n=0}^{100}\frac{n}{4^{n-1}}+\sum_{n=0}^{100}\frac{n}{2^{2n-1}} = \frac{16}{9}+\frac{8}{9}=\boxed{2\frac{2}{3}}$$

So, in summary, this method should take less than 3 flips on average to evenly split a coin toss among three people.

$\endgroup$

protected by Zev Chonoles Jul 14 '15 at 0:46

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.