Subscribe via feed.

King Coin Flips the Third, of ToM

Posted by Karl Sharman on May 6, 2014 – 3:27 am

Two players play the following game with a fair (!) coin.
Player 1 chooses and announces a sequence of 3 heads and tails (HHH, HHT, HTH, HTT, THH, THT, TTH, or TTT) that might result from three successive tosses of the coin.
Player 2 then chooses a different sequence of three.
The players toss the coin until one of the two named ‘triplets’ appears. The ‘triplets’ may appear in any three consecutive tosses: (1st, 2nd, 3rd), (2nd, 3rd, 4th), and so on. The winner is the player whose triplet appears first.

a. What is the optimal strategy for each player? With best play, who is most likely to win?
b. Suppose the triplets were chosen in secret? What then would be the optimal strategy?
c. What would be the optimal strategy against a randomly selected triplet?

Tags:
This post is under “Tom” and has 8 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

8 Responds so far- Add one»

  1. 1. Wizard of Oz Said:

    I’ll cast the first stone . . .

    No triplet is more likely than any other, so there can be no optimal strategy whether selected, in secret or random.

  2. 2. Chris Said:

    Frayed knot Wiz. See “Unfair Coin”, on this site.

  3. 3. Karl Sharman Said:

    I presume you have an answer for this one already, Chris?

    I have this, to start with, in response to Wiz’s assumption that they are all equally likely:-

    Given that each triplet is equally likely, it may initially seem that each is equally likely to appear first. However, if you consider HHH and THH, the only way for HHH to appear before THH is if the first three tosses come up heads. Any other result will allow THH to block HHH. Therefore, the probability that HHH appears before THH is 12.5%. If this assumption is wrong, I’m going down in flames…..again!

  4. 4. Zorglub Said:

    Here is an informal thought:

    I would go with HHT – HTH – THH simply because that out of the 32 possible outcomes of 5 consecutive tosses, these three sequences appear 3 times

    HHTHH
    HTHHT
    THHTH

    Only the symmetrical one (with the H and T permuted) has the same frequency.

  5. 5. Chris Said:

    Hi Karl. Please don’t post a solution yet. I’ve only just got around to seriously thinking about this one. I thought that there would be too many pairs to examine, so didn’t really fancy calculating them all. But I now suspect that there is a shortcut to the solutions.

  6. 6. Karl Sharman Said:

    Hi Chris. I am still working on my answer….. that should fill you with confidence!

  7. 7. Zorglub Said:

    Ignore my previous post, I had misunderstood the question.

    Let p and q be the probabilities that player I and player II wins, respectively.
    Both are nonnegative and p+q = 1.

    Without any loss in generality, player I announces YZH where both Y and Z are in { H, T } (i.e., his third predicted toss is H).

    Claim : 1/8 <= p <= 7/8 and 1/8 <= q <= 7/8
    Proof: This is obvious because the probability that the three first tosses are YZH is 1/8

    Observation : if player II reacts with XYZ for some X in {H,T}, then once X is played, both player will wait for YZ, and player II wins.

    There are four cases to consider

    Case 1 YZH = HHH
    —————————————
    If player II calls THH then p=1/8 and q = 7/8 . This is optimal for player II.

    Case 2 YZH = HTH
    —————————————
    If player II calls THT then by symmetry p = q = 1/2 .
    If player II calls HHT then both players wait for an H. Player 2 wins if the next one is an H, and player I wins half of the time otherwise. Therefore q = 2p and p= 1/3 and q = 2/3 .

    Case 3 YZH = THH
    —————————————
    If player II calls TTH then p= 1/3 and q = 2/3 (same reasoning as above).
    If player II calls HTH then p = q = 1/2.

    Case 4 YZH = TTH
    —————————————
    If player II calls HTT then player I wins if the two first tosses are T (because an H will eventually be tossed). Player II wins otherwise because an H is played, and both player will wait for a pair of T’s. Thus p=1/4 and q=3/4.
    If player II calls TTT then by symmetry p = q = 1/2 .

    Conclusion:
    a) The best strategy fro Player I would be HTH or THH, and player II should react by HHT or TTH, respectively.
    This way player II will win with probability 2/3.

    b) and c) I see no other way than brining in tools such as Nash equilibria from game theory. I am looking forward to a simpler approach.

  8. 8. Karl Sharman Said:

    Following on from Post 3…
    The probabilities for each pair can be calculated in a similar manner. ie HTT vs HHT – the probability HTT appears first is the mean of that probability over the four possibilities for the first two coin tosses. Let, for example, p(HT) be the probability HTT appears first following HT.
    Suppose the first two throws are HH. Then the third throw can be either H or T. If it’s H, then we are back in the same position: the preceding two throws are HH. But if it’s T, then HHT has won! So the probability of HTT winning in this case is 0.
    Putting the two possibilities for the third throw together, as a weighted mean, the probability that HTT wins following HH is: p(HH) = ½×p(HH) + ½×0 = p(HH)/2.
    Now suppose the first two throws are HT. If the third throw is H, then neither player has won, and the probability HTT will ultimately win is (by definition) p(TH). (The last two throws were TH.) On the other hand, if the third throw is T, then HTT has won!
    So this time the weighted mean for the probability that HTT wins, following HT is: p(HT) = ½×p(TH) + ½×1 = p(TH)/2 + 1/2.
    Continuing in this way, we obtain the results below:
    (1) p(HH) = p(HH)/2
    (2) p(HT) = p(TH)/2 + 1/2
    (3) p(TH) = p(HH)/2 + p(HT)/2
    (4) p(TT) = p(TH)/2 + p(TT)/2
    (1) p(HH) = 0. (Intuitively, HTT can avoid losing only by hoping for an infinite string of heads!)
    (3) p(TH) = p(HT)/2
    (2) p(HT) = p(HT)/4 + 1/2 p(HT) = 2/3
    (3) p(TH) = 1/3
    (4) p(TT) = p(TH) p(TT) = 1/3
    The mean of these four results gives us: probability of HTT appearing before HHT = 1/3.

    Here is the full table. Notice the surprising non-transitivity. Example: HHT beats HTT beats TTH beats THH beats HHT.

    Coin triplet probabilities
    2\1 HHH HHT HTH HTT THH THT TTH TTT
    HHH 1/2 2/5 2/5 1/8 5/12 3/10 1/2
    HHT 1/2 2/3 2/3 1/4 5/8 1/2 7/10
    HTH 3/5 1/3 1/2 1/2 1/2 3/8 7/12
    HTT 3/5 1/3 1/2 1/2 1/2 3/4 7/8
    THH 7/8 3/4 1/2 1/2 1/2 1/3 3/5
    THT 7/12 3/8 1/2 1/2 1/2 1/3 3/5
    TTH 7/10 1/2 5/8 1/4 2/3 2/3 1/2
    TTT 1/2 3/10 5/12 1/8 2/5 2/5 1/2

    I am guessing that this won’t format very well once it is posted…..

    So, the optimal strategy, with best play, who is most likely to win?

    The table shows that, for any triplet chosen by player 1, player 2 can always select a triplet that is more likely to appear first. In particular, the best response to each play by player 1, is:
    HHH: THH wins with probability 7/8
    HHT: THH wins with probability 3/4
    HTH: HHT wins with probability 2/3
    HTT: HHT wins with probability 2/3

    Player 2 wants the final two coins of his triplet to be the first two in player 1’s, because then he blocks half the cases where player 1 could win on the next round, by winning first. Similarly, player 2 wants the first two coins in his triplet not to be the final two coins in player 1’s.

    The optimal strategy for player 1 is to choose triplet HTH or HTT, or their mirror images, THT or THH. This limits player 2’s probability of winning to 2/3, as per Zorglubs answer in Post 7.

    Over to you Chris for answers to B & C?. I have nothing for B other than a random choice of HTT or THH with a probability of 1/2 as the best strategy? I am looking into Nash’s eliquibria as per Zorglub’s post

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0