My RSS reader tells me today that the Atlanta Falcons won a three-team coin toss for the third overall draft pick next year. While this is cause for celebration (because my Falcons never win anything), it got me wondering: How do you do a three-way coin toss?
The only method I can think of is to do two flips. In advance, each team calls the two flips in order, for example:
Team 1: H H
Team 2: H T
Team 3: T H
Then you do the two flips, and if it comes up T T, you nullify that one and start over, doing both flips again. But this, to my not-statistically-trained eye, seems like an inelegant solution, and I’m wondering if there’s another way to do it that gets rid of the null-option.
If I figure correctly (which is a big “if”), no multiple of three is going to be a power of two, so I don’t see another way to work this out. Anyone?
Or did they actually draw straws or something, and the “coin toss” thing is just a metaphor?
How about this. Take two teams, someone calls it, if they get it right, they do a flip with the remaining team, if they get it wrong, the other guys flip with the remaining team.
But that way the third team only has to win once, and the other two have to win twice. The third team is essentially getting a first-round bye, which gives them an unfair advantage; they would have a 50% chance of winning, while the first two teams would have 25% each.
I like brossa’s idea, but I’d still like to find a way that doesn’t involve the possibility of a null result and a do-over.
Okay, here is the story on nfl.com. (Exciting actual video footage of the coin flip included!) It is still a little confusing, but the Raiders had already clinched a two way tiebreaker over the Chiefs because the Chiefs finished “ahead” of them in the AFC West because of better common opponent record.
So the only people involved in the actual coin flip were the Raiders and the Falcons, and so there only a single coin flip was necessary. Had the Raiders won the flip, the Chiefs would have drafted fourth and the Falcons fifth.
The question remains, though: Is there an elegant way to have a three-party coin toss, with no “do over” provision?
I’m wondering if this might be one of those things that seem tantalizingly simple, but turn out to be unsolvable, like trisecting an angle with only a ruler and compass.
Yes. Toss the coin repeatedly to spell out a real number in [0, 1] in binary notation. As long as the result isn’t 1/3 or 2/3 (and with probability 1 it won’t be), you will, after some finite number of tosses, see that the number is in [0, 1/3), (1/3, 2/3), or (2/3, 1], and each of those will occur with probability 1/3, thus giving you your final equiprobable distribution on three possibilities.
Or, to put it in ordinary language: Keep tossing the coin until two tosses in a row come out the same way. If they both come up heads and the first toss was a heads, then the output is 1. If they both come up tails and the first toss was a tails, then the output is 2. Otherwise, the output is 3.
Indistinguishable, you sound like someone who knows what he/she is talking about, but doesn’t that give Option 3 a 50% chance, and the other two 25% each?
(First Toss : First Matching Pair : Winner)
H : HH : 1
T : TT : 2
H : TT : 3
T : HH : 3
Or am I missing something important about this system?
What you’re missing is that the probabilities of H:TT and T:HH, in your notation, are significantly lower than those of H:HH and T:TT.
To see this, let’s calculate the probability x that the first double will match the first toss. Well, there’s precisely two ways this can happen: either the second toss matches the first, or the second toss doesn’t match the first but the first double (which comes later) doesn’t match the second. This tells us that x = 1/2 + 1/2 * (1-x). Thus, we get that x = 2/3.
Therefore, P(H:HH) + P(T:TT) = 2/3, giving each of those probability 1/3 (by symmetry considerations), and giving each of H:TT and T:HH probability 1/6.
This establishes that you can’t do it with a fixed finite upper bound on the number of flips required. My method does it (with probability 1 of producing an answer), and does so more efficiently than the “Flip twice; if TT, then toss out and retry” method (nothing is ever tossed out, discarding information), but can still take arbitrarily long.
It’s interesting to note that, though the method I gave has probability 1 of eventually giving an answer, it’s impossible to design a method for doing this which is guaranteed to eventually give an answer. Why is that? Because of Koenig’s lemma and the point you give, essentially, but I’ll spell it out:
Clearly, no fixed finite number of flips will suffice, since 3 doesn’t divide evenly into 2^n for any n. Thus, no matter what method we are using, there must exist arbitrarily long finite flip sequences which have not yet resolved into definite answers. Let’s call this being in a situation of unbounded ambiguity. Note that, whenever we are in a situation of unbounded ambiguity, either flipping H or flipping T must leave us in a situation of unbounded ambiguity. From this, we can readily construct an infinite sequence of Hs and Ts which never leaves unbounded ambiguity, which is to say, there is a possible coin-flipping sequence which never produces an answer. Since we assumed nothing special about the method being used, this shows that no method for solving this problem can guarantee an eventual output; the best that can be done is probability 1 of eventual output.
Ohhhh, now I get it. I think. So the very first toss can be, but is not necessarily, part of the first matching pair? In other words:
Team 1 wins with tosses of [H H] or [H T H H] (and others, of course)
Team 2 wins with [T T] or [T H T T]
Team 3 wins with [T H H] or [H T T] or [H T H T T] or [T H T H H]
And so on. Is that right? I’ll take your word for it that the eventual probabilities work out to 1/3 apiece.
And the infinitely long series that would never give an answer would be [H T H T H T H T] etc., right?
Thanks for indulging me; I’m fascinated by math and probability, but don’t have nearly as much education in it as I’d like.
I want to re-emphasize that the OP’s “Toss twice; discard TT and retry” method also solves the problem with probability 1 of eventually producing an output. The advantage of the method I gave is that it’s more efficient by never discarding any previously generated randomness.
This efficiency is particularly illustrated by the ready generalization of my method to the optimally efficient way to generate a stream of outputs, rather than just a single one. Specifically, you toss the coin repeatedly to get a number in [0, 1] in binary notation, then convert this into trinary notation. This conversion can be done “along the way”, rather than requiring you to wait for the whole number to be pinned down first. (There are problem cases if the number being generated is of the form a/3^b for integers a and b, but these happen with probability 0).
Ah, but he also asks about a toss, singular. A three-way coin toss is not possible without a three-sided coin – which is not possible by definition, I’d say. If every other suggestion relies on multiple tosses, I’d say relying on an altogether separate item is within bounds.
I see your point; I was insufficiently specific in the OP. What I was looking for was a mathematical way to chose one option from three possibilities using only a randomly generated series (more than one flip permitted, as in the rather sloppy method I proposed in the OP) of binary numbers.
I was approaching it as a hypothetical question, rather than looking for an actual problem-solving method. For actual use, the best option would probably be a six-sided die or a lottery or some such.
It’s impossible unless you are willing to discard some of the tosses. What you want is to find a number of possible outcomes of flipping n coins (or 1 coin n times) which is divisible by 3. But there is no such n, since the number of outcomes is 2n, and you need a number of outcomes with a factor of 3 - and 2n has no such factors. So you’re stuck with your original solution, and hope you don’t get too many TTs.