Basic probability I suspect, but I’m not too sure of how to go about it. How to toss a coin to choose one out of three possibilities (x,y, and z).
My initial solution doesn’t work. Toss the coin twice:
heads–x
tails–y
one head and one tail–z #3 actually has a 2 in 4 chance of occuring, while the others each have only a 1 in 4 chance.
So, I’ve come up with the following potential solution: Toss the coin twice. Once to choose between x and y, and a second toss to choose between the winner of the first toss and z.
Does this work? Also, how would I do this for 5 or more options (I think my initial flawed solution works for 4)?
I believe what you’re asking is this: (correct me if I’m wrong)
you want to randomly choose between three different choices. So if you had a 3-sided coin, you’d be all set.
However, all you have is a two-sided coin. How can you use a 2-sided coin to randomly choose between 3 things?
If that is in fact your question, it’s easily answerable.
First of all, let’s figure out how to choose between FOUR choices. That’s easy. Flip the coin twice. There are 4 possible outcomes: HH, TT, HT, TH. They are equally likely. To reduce ourselves to only three possibilities, we choose any three of those. If we get the 4th, we ignore it and try again.
So, it would be like this:
TT-x
TH-y
HT-z
HH-try again
The quickest solution would be to simply assign one of the four possible results as a non-result, meaning you flip the coin again. This would work for any number of possibilities you want.
If you need five possible results, then you could flip the coin three times, giving eight possible results, of which three are non-results.
Without getting into any other complications, that would seem to be the fastest method.
If I may, I’ll expand on the other answers. There’s no ‘perfect’ answer (even with more coins). The only possibilities involve unequal probabilities, or a ‘try again’ option. [It’s fairly obvious, I can prove on request.]
That said, the ‘try again’ option is pretty good. For instance, the probability of having to flip more than 5 times is about 1000 to 1. This is probably as good as coins get anyway.
Or, more or less equivalently, you can do something with 10 coins, or 5 tosses of two coins, that gives almost equal probabilities plus/minus 0.001. (The trick is to find lots of 1/2^? that add up to nearly 1/3. In binary 1/3=0.010101 or something, so you can get as close as you like.)
Much the same method can be used for anything else that isn’t a multiple of two. Eg. for 30 choices, toss 5 coins, and try again if the last two possibilities come up. (Or, if you want to get clever, divide the options into two according to which, and then go with the solution for 15)
If you’re actually doing this, you could use dice or something. But the ‘try again’ method is fine, if slightly unsatisfying.
[thread=25283]Submitted for your approval, an earlier thread[/thread]. About 10 posts in, the optimal solution had been posted; for getting a random result 1-5, there’s a more efficient method than the one hajario gave here, which I called Method Alpha, IIRC.
Thanks, I had doubts about that method as well but couldn’t quite put my finger on them.
Yep, that’s what I’m asking. Thanks.
I’d like to see the proof if you can make it understandable to someone who’s not exactly mathematically literate. I’m smarter than the average bear, but not by much.
I hope you don’t mind if I take a crack at answering before Shade gets to it.
With a coin, every toss gives you two possibilities. For each added toss , you multiply by two to get your new number of possibilities.
1 toss = 2 possible outcomes
2 tosses = 4 possible outcomes
3 tosses = 8 possible outcomes
4 tosses = 16 possible outcomes
If you’re mathematically inclined, you might notice that you’re looking at powers of two, with the number of possibilities being 2[sup]number of tosses[/sup].
So you see that you will always have an even number of possible outcomes. If you want to decide between an odd number of things using coin tosses, then you must ignore at least one of the possible sequences.
