Five Choices – The Prisoner's Dilemma

D16. Five Choices

Contributed by Michael Levitan, Villanova University

You are at a crossroads with five roads leading away from it, and you don’t know which direction to go. You would like to choose randomly, with equal probability for each road. If your only way of making random choices is to flip a fair coin (one that could come up heads or tails with equal probability), you could assign one of the roads to each of the sequences HHH, HHT, HTH, HTT, and THH. Those outcomes are all equally likely, so you know that if you flip three times and choose the corresponding option, each one of them will have an equal chance. The problem is that there are three outcomes that are not assigned to any road, so if one of those three comes up you will have to try again. Therefore, it could take you arbitrarily long to make your decision, if you are unlucky and keep getting one of the unassigned outcomes.

You don’t have all day to stand around, so you’d like a better method. But it turns out that people have proved there is no process with a single fair coin that is guaranteed to finish in a finite amount of time and choose one of five options with equal probability.

Suppose you could have a single unfair coin that would come up heads with probability $p \neq 1 / 2$ (and tails with probability $1 - p$ ). Is there a $p$ you can select and a procedure for using this unfair coin to choose one of the roads, each equally likely, that is guaranteed to complete in a finite number of flips?
If so, can you determine the smallest number $n$ of flips that could be used, and what probability $p$ you want the coin to have to be able to decide in $n$ flips?
Now suppose you are allowed to have more than one coin, each one marked with the probability that it comes up heads. What’s the fewest flips you would need to choose your direction? How many coins do you need, and what’s a set of probabilities for the coins that lets you do it in that minimal number of flips? If your set contains $1 / 2$ , that’s OK; but is there also a way to achieve that minimum with all unfair coins?

This problem originally appeared in the Prisoner’s Dilemma in the 2023 Fall issue of the PMP Newsletter. Solutions are no longer being accepted for this Dilemma.

Show solution?

Solution.

We heard from Chris Bistryski (PMP), Robert Noll (PMP), and Randy Schwartz (Schoolcraft College) on this one. The first construction below, of a single coin that works in six flips, was submitted by Chris.

Note that it is just the number of heads and tails in a given sequence that determines the probability of that sequence, not their order. In other words, all sequences of six heads and tails with the same number of heads have the same probability, regardless of the value of $p$ . Counting, there is just one sequence with six heads, six with five heads, 15 with four heads, 20 with three heads, 15 with two heads, six with one occurrence of heads, and one with none. Therefore, we can make four disjoint collections of sequences, each of which contains one with five heads, three with four heads, five with three heads, three with two heads, and one with a single occurrence of heads. Regardless of $p$ , each of these collections will have the same probability of occurring.

Calculating, this probability is

$p^{5} (1 - p) + 3 p^{4} (1 - p)^{2} + 5 p^{3} (1 - p)^{3} + 3 p^{2} (1 - p)^{4} + p (1 - p)^{5} .$

By simplifying this expression into a sixth-degree polynomial, you can find that there is a unique value of $p < 1 / 2$ such that this probability comes out to exactly $1 / 5$ ; it can be approximated numerically as $p \approx 0.4326366$ . It turns out also to be possible to find an exact expression for this $p$ in terms of square roots and cube roots, for example using symbolic mathematics software; in case you are curious, it is

$p = \frac{1}{2} (1 - \sqrt{1 + \frac{4}{3} (- 1 - \sqrt[3]{\frac{20}{2 + 3 \sqrt{6}}} + \sqrt[3]{\frac{4 + 6 \sqrt{6}}{5}})}) .$

Therefore, if you have a coin with this value of $p$ , you can assign one of the five roads to each of these four equally likely collections of outcomes of six flips, and the remaining road to all of the other outcomes. Since each of the first four has a probability of $1 / 5$ , the remaining outcome must have whatever probability is left over, i.e. 1 – $4 (1 / 5) = 1 / 5$ as well. Hence, each of the five options will be chosen with equal probability.

As for the second part, the Problem Warden is not aware of any solution that works with fewer than six flips, and suspects that six is the minimum possible, but does not have a complete proof for that statement. Chris was able to successfully argue that his scheme could not work with five or fewer flips, because no four sets of outcomes that are equally likely regardless of the value of $p$ can each have probability higher than 19%. However, that argument does not establish definitively that there can’t be some particular value of $p$ for which there just happen to be five sets of outcomes that are equally likely — sets that might not correspond with each other in terms of the numbers of heads in different sequences as the ones in Chris’s strategy do. If anyone discovers such a configuration or a proof that it can’t exist for five of fewer flips, please send it in!

We are able, however, to show that it can’t be done with just three flips of any unfair coin: there are only eight outcomes from three flips, so two of the groups of outcomes that are assigned to roads must consist of just a single outcome. However, assuming by symmetry that $p < 1 / 2$ , the outcome TTT has the unique largest probability. Hence it can’t be one of the single outcomes with probability $1 / 5$ , since no other outcome has equal probability. But therefore its probability is larger than $1 / 5$ , which means it can’t be part of any group, so no assignment is possible.

That leaves us with the third part. No matter what coins you have, you’ll always have to make at least three flips, because there are only four different outcomes for two flips (HH, HT, TH, and TT), and you can’t choose among five options with only four possibilities. On the other hand, Randy points out that with one fair coin and one coin with a probability of heads equal to $1 / 5$ , you can make a fair choice in only three flips: assign one road to heads on the unfair coin and flip that first; if it comes up tails, use the fair coin twice to choose fairly among the other four roads.

But we can’t make a fair choice among five roads with one flip each of all unfair coins with heads probabilities $p, q, r < 1 / 2$ , by the same argument as in the single-coin case. In this situation, TTT is still the outcome with the unique largest probability, leading to the same obstacle as before. That might seem to establish that you can’t choose in three flips with only unfair coins, but actually you can!

The secret is to have more than three types of coins available, and choose which coin to use based on the outcomes of the earlier flips. For example, you can do it using coins with heads probabilities $2 / 5$ , $\sqrt{1 / 2}$ , $5 / 12$ , $1 / 5$ , and $3 / 7$ , as follows. First flip the $2 / 5$ coin. If it comes up heads, use the $\sqrt{1 / 2}$ coin to choose one of two roads fairly (since such a coin comes up HH exactly half of the time, and some other way the the other half of the time). If it comes up tails, we have to choose one of the other three roads fairly; call them $R$ , $S$ , and $T$ . Flip the $5 / 12$ coin. If it comes up heads, flip the $1 / 5$ coin and choose $R$ on heads and $S$ on tails. If the $5 / 12$ coin came up tails (a $7 / 12$ chance), flip the $3 / 7$ coin, but this time choose $R$ on heads and $T$ on tails. For these two flips, you will choose road $R$ exactly $\frac{5}{12} \cdot \frac{1}{5} + \frac{7}{12} \cdot \frac{3}{7} = \frac{1}{3}$ of the time, and similarly for roads $S$ and $T$ . If you find a method to choose fairly among five roads in only three flips with fewer different probabilities of coins, send that in, too.

Incidentally, Robert Noll constructed a set of just three unfair coins with which the choice can be made in four flips: The heads probabilities are $2 / 5$ , $1 / 3$ , and $\sqrt{1 / 2}$ . You start the same way as in the previous construction: if the $2 / 5$ coin comes up heads, choose between two of the roads using the $\sqrt{1 / 2}$ coin twice. If the $2 / 5$ coin comes up tails, flip the $1 / 3$ coin. If it comes up heads, that corresponds to one of the remaining three roads; if tails, you choose fairly between the other two with two flips of the $\sqrt{1 / 2}$ coin.

November 15, 2023

Main Maker