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