A group of 3 friends cannot agree on where to eat. Each person prefers a different restaurant and no one is willing to compromise.

Eventually they agree it would be fair to choose the restaurant at random. How can they use a coin to decide, making sure each restaurant is picked with equal chance?

What if the coin is biased, but they don’t know if it produces more heads or tails?

**Extension:** how can you use a coin to choose between *n* items equally? What if the coin is biased?

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

**Answer to choosing randomly with a coin**

If the coin is fair, there is a simple procedure for choosing between 3 items randomly. The group can flip the coin two times, and that will produce 4 events with equal probability: HH, HT, TH, and TT. Let the first three outcomes correspond to each of the three choices. If the fourth event happens (TT), then disregard it and repeat with two more flips.

In other words, flip the coin two times and then let:

HH: choice 1

HT: choice 2

TH: choice 3

TT: do-over, flip the coin 2 more times and repeat

There will be some do-overs, but mostly this procedure will result in a choice in a matter of a few tries.

As an aside, if we relabel the choices as 0, 1, 2, we can “encode” the coin flips as binary bits for a natural mapping between the flips and the choices. If we let H = 0 and T = 1, then

HH = 00 = choice 0

HT = 01 = choice 1

TH = 10 = choice 2

HH = 11 –> repeat

**What if the coin is biased?**

If heads occurs more frequently than tails, it will no longer be true that HH and HT occur with the same probability. So how can we choose between 3 items in this case?

It seems like we are stuck, but we can use a trick. Let’s first see how we can choose between 2 items. In other words, let’s make a “fair toss” from this unfair coin.

The procedure is this. Flip the coin 2 times. Let HT denote one choice and TH denote the other. If the flip is HH or TT, then disregard and repeat with two flips again.

We can prove this results in creating two events that happen with equal chance. To see why, let’s say that H occurs with probability *p* and T with probability 1 – *p*. When we flip the coin twice, we have:

HT occurs with *p*(1 – p)

TH occurs with (1 – *p*)*p*

We’ve created two events that happen with equal chance, even though the coin itself is biased. The trick was making sure to only consider outcomes where the number of H’s equals the number of T’s.

How can we generalize this for choosing between 3 items?

What we have to do is flip the coin 4 times. Now we disregard the ouctcome if the number of H’s and T’s is not equal. We are left with 6 choices in which there are 2 H’s and 2 T’s. We can label these as follows:

HHTT, HTHT: choice 1

HTTH, THHT: choice 2

THTH, TTHH: choice 3

any other result: disregard and repeat the 4 tosses again

This procedure will result in each of the three restaurants being chosen with equal chance.

(Obviously this is just one way to label the outcomes with choices. Any method that assigns 2 of the equally likely events to each of the 3 choices will be valid.)

**Generalizing to ***n*

Based on this logic we can make random choices between *n* choices using a coin. (This is not the most efficient way to do it, but it’s easy to understand which is important so everyone can agree the procedure is fair!)

*If the coin is fair:* flip the coin *k* times with 2^{k} ≥ n > 2^{k-1}. Label *n* of the equally outcomes with each of the choices 1, 2, …, *n*. For any other outcome flip the coin again until it results in one of the labeled choices.

*If the coin is not fair*: We need to flip the coin so there are at least *n* outcomes where the number of heads is equal to the number of tails. That means we should flip the coin 2*k* times such that 2*k* choose *k* ≥ n. Label *n* of the equally outcomes with each of the choices 1, 2, …, *n*. (We can make this slightly more efficient. We can actually accept *jn* of the outcomes by dividing the outcomes into *n* groups of *j* outcomes each. Recall that in the case of *n* = 3, we has 6= 2*3 outcomes that were divided into 3 groups where each choice got 2 outcomes). For any other outcome flip the coin again until it results in one of the labeled choices.