1

So given a fair unbaised coin and the objective of choosing one of the three given objects with equal probability. How would you go about the task.

I would toss the coin two times and repeat it if I get two tails. I think that way I would be having 33.3333% choices of selecting one of the three objects.

user2340452
  • 951
  • See http://math.stackexchange.com/questions/667198/how-to-choose-between-an-odd-number-of-options-with-a-fair-coin. One objective is to minimise the mean number of tosses required. – Mark Bennet Sep 10 '14 at 07:46
  • You can put the three objects on a floor at a regular triangle's vertices, then drop the coin vertically onto the triangle's center. When the coin stops moving, take the object to which the coin is closest. ;) – CiaPan Sep 10 '14 at 07:47
  • Sounds like searching for a person who is $\dfrac{1}{3}$ German. No matter how you choose the person's ancestors (parents, grand parents, grand grand parents), you'll never find someone who is one third German. – barak manos Sep 10 '14 at 07:56
  • It seems it is impossible to do it with a finite number of tosses, is it possible to prove this? – flawr Sep 10 '14 at 08:17
  • @flawr Yes: one-third is not dyadic, QED. – Did Sep 10 '14 at 08:23
  • So why does this imply that you cannot come up with any system that still uses only a finite number of tosses? – flawr Sep 10 '14 at 08:40
  • 2
    Suppose your choice is made within n tosses. Each choice must result from an equal number of sequences of length $n$ (if the choice terminated earlier, count every sequence with that initial segment). Since $2^n$ is not divisible by $3$ you can't divide all such sequences into $3$ parts, so to obtain probability $\frac 13$ there must be some sequence of $n$ tosses which does not select any option. This holds for any $n$, so the sequence is not guaranteed to terminate. – Mark Bennet Sep 10 '14 at 09:03

1 Answers1

2

That way works. However there is a more general way. Consider the base two expansion of $\frac{1}{3}=0.a_1a_2a_3....$, where $a_i\in\{0,1\}$, and $$\frac{1}{3}=\sum_{i=1}^\infty \frac{a_i}{2^i}$$

Flip the coin until you get heads, suppose it takes you $i$ flips. If $a_i=1$, then say the event has occured, otherwise not. The expected number of times the event will occur per flip is then $\sum_{i=1}^\infty \frac{a_i}{2^i}=\frac{1}{3}$. Moreover the expected amount of time to flip heads is 2, so this is quite an efficient method. This also generalises to any real probability $p$.

Peter Huxford
  • 2,561