# Selecting randomly from five options, using only a coin

Suppose you have five options out of which you need to select one at random. Each is to have the same probability of being picked–i.e., one in five. The only means of randomization you have on hand is one which selects between two equally probable options–say, a coin.

I’ve been trying to figure out a way to do this. I think I did figure out a way, but its a little complicated, and involves a process which runs an (incredibly miniscule, but non-zero) chance of never coming to a conclusive end. (Hard to explain.)

I was wondering if there’s a relatively simple method which I’m overlooking, and also whether there’s one guaranteed to end in a conclusive decision after a finite number of steps.

-FrL-

(The method I came up with is:

Flip the coin ten times, recording the flips. Label each option with a letter, A through E. Now number A through D 1 through 4. Use the first two flips to decide between one of these 4. Now lable A through C 1 through 3, and lable E 4. Use the second two flips to decide between one of these 4. Now label them 1 through 4, this time skipping C. Decide between the 4. Now skip B, and decide. Now skip A, and decide. Now count up how many times each of A through E was selected. If any was selected more than all the others, then end the process–that one is your final selectee. Otherwise, there was a tie. It happens that the only possible ties inthis situation are 2-way and 5-way. If it was 5-way, strt over. If it was 2-way, flip the coin once more to decide between those two.

That gives each possibility an equal probability, I think. But its minutely possible for the process to take a very long time.)

Flip your coin four times. If if comes up all heads, start over. Otherwise:

HHHT, HHTH, HHTT = option 1
HTHH, HTHT, HTTH = option 2
HTTT, THHH, THHT = option 3
THTH, THTT, TTHH = option 4
TTHT, TTTH, TTTT = option 5

There’s still some minimal chance of continuously flipping all heads for ever and ever, but I’m not so worried about it.

My friends and I do this sort of thing sometimes when we need to choose one of us to do something. I’ll explain how it’s run in that context.

First, you give each of the five people a different number, 0 through 4.
Then you convert those numbers into binary - 000, 001, 010, 011, and 100. (yes, several of us are computer science majors, why do you ask? )
Then we assign a digit, 1 or 0, to each side of the coin. Heads is generally 1.
Someone flips the coin three times and records the results.
If your number comes up, you’re it.
If we get 101, 110, or 111, we have to do it over.

This can be easily adapted for any number of people, but it works best for powers of two or numbers slightly less than powers of two. Otherwise, your chances of having to do it over get annoyingly high. In this case, you have a 3/8 = 37.5% chance of having to run a second round, a 14.0625% chance of having to run a third, an 8.4375% chance of having to run a fourth, etc.

It’s faster if you use multiple coins (say, a dime, a nickel, and a penny) and designate which digit they represent so that you can flip all three at once.

Yes, we are big nerds.

A very simple method is to label each of the five things with different outcomes of three coin flips. HHT TTH HTH THT TTT for example. It is like a lottery but there are only 8 possible outcomes and 5 “tickets”. Flip the coin in groups of three until one wins. There is a probability that none will win for many trials but the probability becomes mannishly small very fast.

A very simple method is to label each of the five things with different outcomes of three coin flips. HHT TTH HTH THT TTT for example. It is like a lottery but there are only 8 possible outcomes and 5 “tickets”. Flip the coin in groups of three until one wins. There is a probability that none will win for many trials but the probability becomes very small very fast.

You could express your five choices as binary numbers: 000, 001, 010, 011, 100. Then you could flip the coin three times, assigning, say, heads =1, tails=0. Then if you get TTT, you pick the first. TTH, the second… HTT means the last.

Now, since three binary digits can give 8 possible outcomes, you have to ignore the times when you get HTH, HHT, or HHH. If that happens, you just flip again three times.

Leave it to me to encomplicatify that which is in actuality quite unencomplicateficatory.

Thanks guys!

-FrL-

As I understand it, the fact that there’s no solution that doesn’t have a possibility of infinite coin flips required to reach a decision boils down to the fact that 1/5 is not a terminating binary fraction.

You’d reach the same kind of issues, I think, trying to decide from three options, having only a ten-sided die.

The moral - always try to have as large a number of possible different randomizers on hand as possible.

Oh, and in case you’re wondering, while zut’s method is quite good at cutting down on the chance that you’ll have to do it over, you still can’t entirely eliminate that risk in this way. (why? Because no multiple of 5 is also a power of 2 - powers of two always end in the digits 2, 4, 8, or 6.)

Geek → English translation: I need to buy more of those pretty, shiny polyhedral dice.
… Not that I’d know anything about that.

Or carry around coins with more than two sides. I can’t help it if your pitiful HU-MON universe is only three-dimensional.

Toss the coin once for each option. If you get 5 heads or 5 tails - no decision. 4 heads/tails and 1 of the other it is the selected option. 3 heads/tails and 2 of the other just a simple “heads you win…”

I really like Elfbabe’s reply.

Replies.

(pretty polyhedrons)

Do they make icosahedral dice? That would be perfect for those 5-way decisions.

I have bought 4, 6, 8, 12 and 20 sided dice.

I have seen a 30 and a 100 sided die advertised.

So the guaranteed one-off solution is to use the coin to buy a d20 (and allocate 4 numbers to each choice).

Which would seem to indicate that the smallest number of solutions for which no pre-existing dice we know of would work evenly is… seven. Hmm…

Would it be possible to make a decent 14-sided die as a spindle, like the Ten-sided die

I would do this. Call the choices A thru E. I would flip one coin to determine A’s fate. If heads, A moves on. If tails, A is eliminated. Do the same for B-E. If all five are elimnated or all five move on, repeat. Otherwise, you get this:

If four are left, make a tournament bracket for the survivors, single elimination.

If three are left (say 1, 2, and 3) do a flip-off 1v2, 2v3, and 1v3. The choice that is 2-0 wins.

If two are left, then flip to see which wins.

If one is left, then you’re done.

If I’ve done my math correctly (which admittedly, I may not have), with the three coin method, you would expect to flip 4.8 coins total. With four, you would expect to flip 4.2667 coins total. You could do the same procedure with more coins, but you’d clearly get an even larger expected number of flips, so four seems optimum.

Flip the coin once for each object, tails it’s out, head’s it’s still in.

Repeat till one object is left or a easier way of flipping comes up (i.e. if 3 were out, and only 2 were still in after the first flipping, you could do heads for one tails of the other)

It may take more flips, but it is easy to do and no complex flipping plans developed ahead of time.