2

I based this on a problem from a mathematics presentation, adding a small twist. I did not readily find it here.

Your friend comes to dinner and you know he loves to drink Beaujolais. You have 'Cote de Brouilly', 'Régnié' and 'Morgon' in your cellar. The same winehouse, same quality, same year. Your wife likes 'Cote de Brouilly' so, taking advantage of the presence of your guest, you want to get 'Régnié' or 'Morgon' from your cellar this time as variation.

You take with you a fair coin to chose which one of the two with equal probability. But when you arrive in the cellar and overlook the wines, you change your mind and want to get 'Cote de Brouilly', 'Régnié' or 'Morgon'. How do you choose which one of the three with equal probability using the only tool you took with you: a fair coin?

Is one method perhaps more efficient than another method?

Peter Mortensen
  • 146
  • 5
FirstName LastName
  • 559
  • 3
  • 18

2 Answers2

4

Toss the coin twice...

...yielding four equally likely outcomes.

  • HH: wine 1
  • HT: wine 2
  • TH: wine 3
  • TT: failed, so toss twice again

Each trial succeeds with probability $3/4$, so expect $4/3$ trials ($8/3$ tosses) to get the first success (geometric random variable).

RobPratt
  • 13,685
  • 1
  • 29
  • 56
  • Nice ... other idea was to binary break up $[0,1]$. Notice $\frac{1}{3}=0.0101010...$ and $\frac{2}{3} = 0.1010101...$ So first throw would decide to go below or above $1/2$, Then keep throwing until you mismatch $\frac{1}{3}$ or $\frac{2}{3}$. Depending on the mismatch (smaller of bigger than target), you end up in $]0,\frac{1}{3}[$ or $]\frac{1}{3},\frac{2}{3}[$ or $]\frac{2}{3},1[$ corresponding to wines 1 2 3. However, expected trials is $3 > \frac{8}{3}$. – FirstName LastName Apr 08 '22 at 22:18
  • The mathematics presentation was about simulating event with probability $p$ for any real number $p$ in $[0,1]$ using a fair coin by targeting $p$'s binary expansion sequence. – FirstName LastName Apr 08 '22 at 22:30
  • 2
    That sounds like this: https://puzzling.stackexchange.com/questions/110154/simulating-a-biased-coin-with-an-unbiased-one – RobPratt Apr 08 '22 at 22:45
  • FYI: I am actually happy you explicitely gave expected trials too. I knew this solution but, somehow, (wrongly) intuitively, I assumed expected trials $>=4$. Because throwing away those TT failures seemed to be a decent waste of information to me. On the other hand: the binary elimination does not 'waste' information. But: it plays the game too rough at the beginning edge by halving potential of all possible further scenarios. So ... it turns out intuition (at least mine) is not always a good guide :-) Thanks for the lesson (also for the link)! – FirstName LastName Apr 08 '22 at 23:34
  • along similar lines I recently posted https://math.stackexchange.com/questions/4418115/ – FirstName LastName Apr 09 '22 at 00:42
  • 1
    @FirstNameLastName throwing away TT on this answer is similar (not completely the same, but intuitively the same) as throwing away 10 in your answer. After you got 10, then if next is 0, it's below 2/3, if it's 11, it's above 2/3, if it's 10, throw it away and toss again. The lesson here is, TT is not wasted, it's simply a prefix of a longer sequence. – justhalf Apr 09 '22 at 13:13
0

RobPratt's solution works, but it requires an unbounded number of coin throws in the worst case, potentially causing you to miss dinner!

I claim that there is no solution that only requires a finite number of coin throws:

Assume that there is a solution $S$ requiring only a fixed number $n$ of coin tosses. Note that there are exactly $2^n$ possible sequences of $n$ coin tosses:

HHH...HHH
HHH...HHT
HHH...HTH
...

Now we map to each sequence the wine selection result produced by solution $S$, e.g.

HHH...HHH -> Wine 1
HHH...HHT -> Wine 1
HHH...HTH -> Wine 2
...

(If $S$ allows you to "finish early" in some cases (e.g., HT -> Wine 2), we just map all sequences starting with this prefix to that wine. This transforms our "finish early" algorithm into a "don't finish early" algorithm without changing the probabilities.)

To be fair, there must be an equal number of sequences mapping to Wine 1, to Wine 2 and to Wine 3, i.e., each wine must appear exactly $2^n/3$ times in our list. However, all prime factors of $2^n$ are $2$, which means that $2^n$ is not divisible by $3$. Hence, the selection is not fair.

RobPratt
  • 13,685
  • 1
  • 29
  • 56
Heinzi
  • 451
  • 3
  • 7
  • there is no finite number tossing solution indeed, but the expected value of such number is very low and in practice I did not miss any dinner :-) – FirstName LastName Apr 09 '22 at 16:50