Is there a possibility to choose fairly from three items when every choice can only have 2 options

Question

Me and my wife are often not knowing which DVD to watch. If we have two options we have a simple solution, I put one DVD in one hand behind my back and the other DVD in the other hand. She will randomly choose a hand and the DVD I have in that hand will be the one to watch.

This procedure is easy to expand to any power of 2. If we have 4 DVD's I hold 2 in one hand, 2 in the other. When a pair of DVD's is chosen, I split them out to two hands and she choses again.

The question is, what can we do when we have 3 DVD's. The assumptions we make are:

• I am not impartial. If I can influence the result somehow I will try to do that
• My wife really choses randomly a side every-time, independent of what she chose earlier.
• I don't have any other place to hide the DVD's, so every DVD is either visible or in one of the two hands.

As requirement we have that it must be a procedure with a predetermined number of steps. Not more, not less. If this is not possible, a solution that guarantees to finish with an upperbound, this is a good second choice. Off course the DVD we choose must be really random!

Answer 1

Nice question. Firstly, there's no solution which will always take a fixed number of steps each time: after n independent random trials (choosing a hand), there are 2ⁿ possible choices, and 2ⁿ is never divisible by 3. (Equivalently: 1/3 does not have a terminating representation in base 2.)

But you can come up with solutions that terminate within a fixed number of steps with high probability. Note that you need at least 2 trials, since log₂(3) > 1. Here's one simple method:

1. Hold 2 DVDs in one hand and 1 DVD in other (your wife doesn't know which is which).

2. If the hand with 2 DVDs is chosen: play them against each other.
   Else: If the 1 DVD is chosen: play it against an empty hand.

Each of the 3 DVDs has equal probability 1/4 of being chosen, and with probability 1/4, you have to repeat from scratch. This solution takes 2 trials with probabilty 3/4, 4 trials with probability (1/4)(3/4), 6 trials with probability (1/4)²(3/4) and so on, so takes an expected number of 8/3 (≈ 2.66) trials. (See geometric distribution.)

I believe this is optimal (famous last words?) if you just have to choose out of 3 DVDs once. Probably, if you're going to choose from 3 DVDs many times, you can do better in the long run (amortised) and achieve the lower bound of log₂ 3 ≈ 1.58 trials on average, by "caching" some random choices from last time. (But will you remember them? :-)) At least you can do something similar when generating random numbers (see also this mildly related Stack Overflow thread), but in this case with game-theoretic fairness complications I'm not so sure.

Answer 2

In 1976, Knuth and Yao proved a result that may help you choose a DVD out of 5, 6, etc. (I couldn't find a good reference online.) Consider the following problem: You have a fair coin and you must write an algorithm that outputs 1 with probability p1, outputs 2 with probability p2, ..., and outputs n with probability pn. (p1+p2+...+pn=1) Note that any possible algorithm can be described in terms of certain (possibly infinite) binary trees: A node that has two children means "throw a coin and pick one of the children according to the result"; a leaf is tagged with one of the numbers 1, 2, ..., n and means "output that number".

An optimal tree that solves the problem has one leaf k on level m if and only if the m-th bit of pk is 1. Otherwise there are zero such leafs.

"Optimal" here means not only that the average runtime is as good as possible, but the stronger guarantee that the probability of running more than m steps is not worse than that of any other algorithm that solves the problem correctly.

In your case, p1=p2=p3=0.01010101... The digit just before dot corresponds to the root (level 0) and and the subsequent digits to subsequent levels. So a tree that has no leaf on levels 0 and 1, has leafs (1, 2, and 3) on level 2, has no leaf on level 3, ... is optimal. This is exactly the solution given by ShreevatsaR. Such a tree is fairly easy to find once you know what leafs you need to put on each level.

As another example, if p1=...=p6=1/6=0.00101010101..., then you should have leafs (one of each 1, 2, 3, 4, 5, 6) on levels 3, 5, 7, and so on. If you draw a symmetric tree that obeys this you'll find how to choose one DVD out of 6: First grab three with each hand, then do what ShreevatsaR said for three. You are also guaranteed that it's optimal.

Now you can mock me and my friends for using a suboptimal algorithm for allocating hotel rooms.

Answer 3

There is no such procedure which has an upperbound on number of steps. Here is proof. Let there is such procedure with no more then $N$ steps. On each step you basicly generate random integer between $1$ and $2$. Consider all possible sequences of no more than $N$ generated numbers. Every such sequence has probability of form $\frac{x}{2^N}$.

Consider sequences for which the procedure says "1" (the result is equal to $1$). The sum of theirs probabilities is $\frac{x_1}{2_N}$. It also must be equal to $\frac{1}{3}$. But $\frac{x_1}{2_N}$ can't be equal to $\frac{1}{3}$.

Answer 4

A method suggested here to choose between three options is to first flip a coin twice (or ask your wife to randomly pick a side twice, I suppose), getting four possible outcomes. Three of those outcomes are assigned to the three options. If the fourth outcome happens, restart. In expectation, this requires $\frac83$ coin flips.

We can prove that $\frac83$ is optimal: no method for choosing between three options by flipping a coin can take fewer than $\frac83$ coin flips in expectation!

Let $\mathbf X$ be the number of coin flips required by some scheme to choose from $3$ options. Then we can put a lower bound on the probability that $\mathbf X>k$, depending on $k$:

• When $k$ is odd, the $2^k$ possible results for the first $k$ coin flips can be split into three groups of $\frac{2^k-2}{3}$ with $2$ left over. Therefore at most $2^k-2$ of those results can be assigned to an option. With probability at least $\frac{2}{2^k}$, we have $\mathbf X>k$.
• When $k$ is even, the $2^k$ possible results for the first $k$ coin flips can be split into three groups of $\frac{2^k-1}{3}$ with $1$ left over. Therefore at most $2^k-1$ of those results can be assigned to an option. With probability at least $\frac{1}{2^k}$, we have $\mathbf X>k$.

One expression for the expected value $\mathbb E[\mathbf X]$ is $$ \mathbb E[\mathbf X] = \Pr[\mathbf X > 0] + \Pr[\mathbf X > 1] + \Pr[\mathbf X > 2] + \Pr[\mathbf X > 3] + \cdots $$ since we can see that $\Pr[\mathbf X=k]$ is counted in exactly $k$ of the terms on the right. By the observations above, we have $$ \mathbb E[\mathbf X] \ge \frac{1}{2^0} + \frac{2}{2^1} + \frac{1}{2^2} + \frac{2}{2^3} + \frac1{2^4} + \frac2{2^5} + \cdots $$ By grouping the terms two at a time, we get a geometric series $2 + \frac12 + \frac18 + \frac1{32} + \cdots$ which simplifies to $\frac{2}{1-\frac14} = \frac83$. Therefore any scheme we can come up with requires at least $\frac83$ coin flips on average.

Answer 5

I will answer to the letter of your question. DVDs A, B, C.

1. Hold A & B behind back. Wife chooses (say A). Drop B.
2. Hold chosen (A) & C behind back. Wife chooses.
3. If it is the other (C), a) then hold C and B behind back. Wife gets to pick (as always): Voila. b) else go bed.

All conditions met. 3 steps.

Answer 6

Here's a table of n 2^n m 3^m and p(fail) where 3^m is the largest value < 2^m. The first row represents the standard algorithm.

If you care about the near-worst-case performance, the n=65 row suggests an interesting possibility: take a random 65-bit number, reject if if it's too large (1.14% of cases), then use repeated div/mod to get 41 1-in-3 choices. This algorithm is 99% efficient with the input entropy vs. 59% for the standard algorithm.

On 64-bit hardware you can have two cases depending on the 65'th bit being 0 or 1.

2 4 1 3 25.00
3 8 1 3 62.50
4 16 2 9 43.75
5 32 3 27 15.62
6 64 3 27 57.81
7 128 4 81 36.72
8 256 5 243 5.08
9 512 5 243 52.54
10 1024 6 729 28.81
11 2048 6 729 64.40
12 4096 7 2187 46.61
13 8192 8 6561 19.91
14 16384 8 6561 59.95
15 32768 9 19683 39.93
16 65536 10 59049 9.90
17 131072 10 59049 54.95
18 262144 11 177147 32.42
19 524288 11 177147 66.21
20 1048576 12 531441 49.32
21 2097152 13 1594323 23.98
22 4194304 13 1594323 61.99
23 8388608 14 4782969 42.98
24 16777216 15 14348907 14.47
25 33554432 15 14348907 57.24
26 67108864 16 43046721 35.86
27 134217728 17 129140163 3.78
28 268435456 17 129140163 51.89
29 536870912 18 387420489 27.84
30 1073741824 18 387420489 63.92
31 2147483648 19 1162261467 45.88
32 4294967296 20 3486784401 18.82
33 8589934592 20 3486784401 59.41
34 17179869184 21 10460353203 39.11
35 34359738368 22 31381059609 8.67
36 68719476736 22 31381059609 54.33
37 137438953472 23 94143178827 31.50
38 274877906944 23 94143178827 65.75
39 549755813888 24 282429536481 48.63
40 1099511627776 25 847288609443 22.94
41 2199023255552 25 847288609443 61.47
42 4398046511104 26 2541865828329 42.20
43 8796093022208 27 7625597484987 13.31
44 17592186044416 27 7625597484987 56.65
45 35184372088832 28 22876792454961 34.98
46 70368744177664 29 68630377364883 2.47
47 140737488355328 29 68630377364883 51.24
48 281474976710656 30 205891132094649 26.85
49 562949953421312 30 205891132094649 63.43
50 1125899906842624 31 617673396283947 45.14
51 2251799813685248 32 1853020188851841 17.71
52 4503599627370496 32 1853020188851841 58.85
53 9007199254740992 33 5559060566555523 38.28
54 18014398509481984 34 16677181699666569 7.42
55 36028797018963968 34 16677181699666569 53.71
56 72057594037927936 35 50031545098999707 30.57
57 144115188075855872 35 50031545098999707 65.28
58 288230376151711744 36 150094635296999121 47.93
59 576460752303423488 37 450283905890997363 21.89
60 1152921504606846976 37 450283905890997363 60.94
61 2305843009213693952 38 1350851717672992089 41.42
62 4611686018427387904 39 4052555153018976267 12.12
63 9223372036854775808 39 4052555153018976267 56.06
64 18446744073709551616 40 12157665459056928801 34.09
65 36893488147419103232 41 36472996377170786403 1.14 ***
66 73786976294838206464 41 36472996377170786403 50.57
67 147573952589676412928 42 109418989131512359209 25.85
68 295147905179352825856 42 109418989131512359209 62.93
69 590295810358705651712 43 328256967394537077627 44.39
70 1180591620717411303424 44 984770902183611232881 16.59
71 2361183241434822606848 44 984770902183611232881 58.29
72 4722366482869645213696 45 2954312706550833698643 37.44
73 9444732965739290427392 46 8862938119652501095929 6.16
74 18889465931478580854784 46 8862938119652501095929 53.08
75 37778931862957161709568 47 26588814358957503287787 29.62
76 75557863725914323419136 47 26588814358957503287787 64.81
77 151115727451828646838272 48 79766443076872509863361 47.21
78 302231454903657293676544 49 239299329230617529590083 20.82
79 604462909807314587353088 49 239299329230617529590083 60.41
80 1208925819614629174706176 50 717897987691852588770249 40.62
81 2417851639229258349412352 51 2153693963075557766310747 10.93
82 4835703278458516698824704 51 2153693963075557766310747 55.46
83 9671406556917033397649408 52 6461081889226673298932241 33.19
84 19342813113834066795298816 52 6461081889226673298932241 66.60
85 38685626227668133590597632 53 19383245667680019896796723 49.90
86 77371252455336267181195264 54 58149737003040059690390169 24.84
87 154742504910672534362390528 54 58149737003040059690390169 62.42
88 309485009821345068724781056 55 174449211009120179071170507 43.63
89 618970019642690137449562112 56 523347633027360537213511521 15.45
90 1237940039285380274899124224 56 523347633027360537213511521 57.72
91 2475880078570760549798248448 57 1570042899082081611640534563 36.59
92 4951760157141521099596496896 58 4710128697246244834921603689 4.88
93 9903520314283042199192993792 58 4710128697246244834921603689 52.44
94 19807040628566084398385987584 59 14130386091738734504764811067 28.66
95 39614081257132168796771975168 59 14130386091738734504764811067 64.33
96 79228162514264337593543950336 60 42391158275216203514294433201 46.49
97 158456325028528675187087900672 61 127173474825648610542883299603 19.74
98 316912650057057350374175801344 61 127173474825648610542883299603 59.87
99 633825300114114700748351602688 62 381520424476945831628649898809 39.81
100 1267650600228229401496703205376 63 1144561273430837494885949696427 9.71
101 2535301200456458802993406410752 63 1144561273430837494885949696427 54.86
102 5070602400912917605986812821504 64 3433683820292512484657849089281 32.28
103 10141204801825835211973625643008 64 3433683820292512484657849089281 66.14
104 20282409603651670423947251286016 65 10301051460877537453973547267843 49.21
105 40564819207303340847894502572032 66 30903154382632612361920641803529 23.82
106 81129638414606681695789005144064 66 30903154382632612361920641803529 61.91
107 162259276829213363391578010288128 67 92709463147897837085761925410587 42.86
108 324518553658426726783156020576256 68 278128389443693511257285776231761 14.30
109 649037107316853453566312041152512 68 278128389443693511257285776231761 57.15
110 1298074214633706907132624082305024 69 834385168331080533771857328695283 35.72
111 2596148429267413814265248164610048 70 2503155504993241601315571986085849 3.58
112 5192296858534827628530496329220096 70 2503155504993241601315571986085849 51.79
113 10384593717069655257060992658440192 71 7509466514979724803946715958257547 27.69
114 20769187434139310514121985316880384 71 7509466514979724803946715958257547 63.84
115 41538374868278621028243970633760768 72 22528399544939174411840147874772641 45.76
116 83076749736557242056487941267521536 73 67585198634817523235520443624317923 18.65
117 166153499473114484112975882535043072 73 67585198634817523235520443624317923 59.32
118 332306998946228968225951765070086144 74 202755595904452569706561330872953769 38.99
119 664613997892457936451903530140172288 75 608266787713357709119683992618861307 8.48
120 1329227995784915872903807060280344576 75 608266787713357709119683992618861307 54.24
121 2658455991569831745807614120560689152 76 1824800363140073127359051977856583921 31.36
122 5316911983139663491615228241121378304 76 1824800363140073127359051977856583921 65.68
123 10633823966279326983230456482242756608 77 5474401089420219382077155933569751763 48.52
124 21267647932558653966460912964485513216 78 16423203268260658146231467800709255289 22.78
125 42535295865117307932921825928971026432 78 16423203268260658146231467800709255289 61.39
126 85070591730234615865843651857942052864 79 49269609804781974438694403402127765867 42.08
127 170141183460469231731687303715884105728 80 147808829414345923316083210206383297601 13.13