4

I wish to give an apple to 1 of 3 children fairly using a coin flip game. Each child calls heads or tails, and I flip the coin once for each child. If exactly one child calls correctly, that child gets the apple. If there is no one who calls correctly the game repeats. If two children call correctly, the game repeats between the 2 children until only of them calls correctly.

Is this game fair; i.e., does each child have the same probability of winning? I am assuming yes intuitively.

What about a game in which I only flip the coin once, and each child calls. Is this game fair? I am assuming yes intuitively.

What is the expected number of coinflips in my original game? I recursively got 6:

Let $N_3, N_2$ be the number of flips for three and two children respectively. Then for three children: $$P(0\space correct\space calls) = 1/8 $$ $$P(1\space correct\space call) = 3/8 $$ $$P(2\space correct\space calls) = 3/8 $$ $$P(3\space correct\space calls) = 1/8 $$

Hence: $E(N_3) = \frac{3}{8} \cdot3 + \frac{2}{8}\cdot (3 + E(N_3)) + \frac{3}{8}\cdot(3 + E(N_2))$

For two children:

$$P(0\space correct\space calls) = 1/4$$ $$P(1\space correct\space call) = 2/4$$ $$P(2\space correct\space calls) = 1/4$$

Hence: $E(N_2) = \frac{1}{2}\cdot 2 + \frac{1}{2}\cdot (2 + E(N_2))$

Thus: $E(N_2) = 4$ and $E(N_3) = 6$

For the curious, I am trying to see if this "tournament game" is "isomorphic" to randomly assigning "T" to a child, then doing 3 coinflips until a permutation of {T,H,H} is achieved and hence the assigned child gets the apple, as described by Tim Crack in Heard On the Street (17e). That "assignment game" expects 8 coinflips whereas I am getting 6 in my "tournament game." I am probably misinterpreting his description of "tournament game" or incorrectly calculating 6.

Zhulu
  • 1,259
  • 1
    Instead of letting the kids call the coin flips, you should make them flip the coin themselves to choose their calls. Otherwise (1) unless the kids choose simultaneously and secretly, kid #3 has a disadvantage, since kids #1 #2 will always make the opposite choices, and then kid #3 must make the same choice as one of them, and (2) my rotten nephew will mess you up by always calling the same as one of the other kids, so the game never ends. – MJD Aug 29 '18 at 16:01
  • Come to think of it, this points the way to a simpler and better protocol. Instead of having the kids predict a coin toss, just have them each flip a coin in each round. Heads are poisonous, and a kid who flips one is eliminated from the game, except that if the current round ends with nobody left, it is spoiled and done over. Now you are immune from all conspiracies, even those involving my nephew. – MJD Aug 29 '18 at 16:06
  • Hahaha that's a good point. – Zhulu Aug 29 '18 at 16:07
  • 1
    Pointless comment: you can generate any probability with a binary random number generator (the coin in this case), so you could theoretically flip the coin until you have a binary number that, regardless of future flips, will be between 0 and 1/3, or 1/3 and 2/3 or 2/3 and 3/3. –  Aug 29 '18 at 16:10
  • Another procedure would be to have each child flip a coin. If two flips match (and one is different), declare the child with the unique flip to be the winner. If all three match, try again. (Expected number of flips is 4, assuming the coin is fair). – paw88789 Aug 29 '18 at 16:54
  • See also https://math.stackexchange.com/questions/667198/how-to-choose-between-an-odd-number-of-options-with-a-fair-coin – Mark Bennet Aug 29 '18 at 17:04
  • See also https://math.stackexchange.com/questions/3340212. – joriki Mar 29 '20 at 18:10
  • See also https://math.stackexchange.com/questions/1333/. – joriki Mar 29 '20 at 18:13

1 Answers1

2

Your method is fair by symmetry, and it has the nice property that its fairness doesn't depend on the coin being fair (though the expected number of flips does).

MJD's proposals in the comments also have this property and have the same expected number of flips.

If you want to minimize the expected number of flips and you don't mind relying on the coin being fair, you can assign one of the four patterns for two successive flips to each of the children and start again if the fourth pattern occurs. The expected number $x$ of flips then satisfies $x=2+\frac14x$, with solution $x=\frac83$, a significant improvement over $6$.

Barrycarter's suggestion of generating binary digits until you know which third of the unit interval the resulting number falls into is slightly less efficient than that. Since $\frac13=0.\overline{01}_2$ and $\frac23=0.\overline{10}_2$, you know which third the number will fall into when a digit repeats. This occurs with probability $\frac12$ for each digit except the first, so the expected number of digits you need to generate is $3$.

joriki
  • 238,052
  • Is the 6 correct? Also, could you elaborate on the "symmetry" aspect. I am thinking if I wrote out a bunch of conditional probabilities conditioned on winning in round 1, 2, 3, 4... I'd be able to prove P(child 1 wins) = P(child 2 wins) = P(child 3 wins), using symmetry somewhere along the way. – Zhulu Aug 29 '18 at 16:27
  • @Zhulu: Yes, the $6$ is correct. The method is fair simply because no child is distinguished from any other child. The symmetry is permutation symmetry; formally, your method is invariant under any permutation of the children, which directly implies that it's fair. (Otherwise any proof that it favours one child could be permuted into a proof that it disfavours that child, yielding a contradiction.) – joriki Aug 29 '18 at 16:32