A coin-tossing game...

[Gengulphus]

Something I've been reminded of by the "Alice and Bob toss coins" thread, and which I think deserves a thread of its own...

I offer to play a game with you, in which you name a sequence of three coin tosses, e.g. "tails, tails, heads". Then I name a different sequence of three coin tosses, e.g. "heads, heads, heads", and we toss a fair coin repeatedly until the last three tosses are either your sequence or mine. If they're your sequence, you win; if they're mine, I win. The loser pays the winner £1.

Do you wish to play?

Gengulphus

[chas49]

Probably only if I get to name my sequence second

(I think that gives me an advantage??)

[Gengulphus]

Probably only if I get to name my sequence second

No, you don't get to change the game from the one I'm offering!

(I think that gives me an advantage??)

Well, the question is whether it gives me an advantage... ;-)

Gengulphus

[chas49]

No thanks then

The sequence you chose gives you an advantage

I can't explain why though.

[UncleEbenezer]

No thanks then

The sequence you chose gives you an advantage

I can't explain why though.

You are of course right. The odds are between 2:1 and 7:1 in Gengulphus's favour, depending on your initial choice. I'm not going to try and explain, either. At least, not unless well-boozed-up.

But, one for Gengulphus. Take the same game with three, four, five, six, seven or eight players. In each case, what position do you want your choice to be?

[jfgw]

No thanks then

The sequence you chose gives you an advantage

I can't explain why though.

You are of course right. The odds are between 2:1 and 7:1 in Gengulphus's favour, depending on your initial choice...

Assuming Gengulphus chooses wisely of course, otherwise the odds could be 1:7.

If I did play, I wouldn't choose HHH as Gengulphus would choose THH so, unless I won with the first three tosses, I would definitely lose. Likewise with TTT. The ratio would be 1:7.

Similarly for other permutations, there can be an advantage if he makes his second and third choices the same as my first and second. If I choose HHT, for example, and Gengulphus chooses THH, then, for the third and subsequent tosses, if HH came up, there would be a 50% chance that he would win (depending upon the previous toss). If he didn't win (50% chance), there would then be a 50% chance I would win on the next toss. We would have an equal chance of winning with the first three tosses (1/8 each) followed by a 2:1 ratio. This equates to a 5:3 ratio.

Julian F. G. W.

[Gengulphus]

But, one for Gengulphus. Take the same game with three, four, five, six, seven or eight players. In each case, what position do you want your choice to be?

Good question, and I'll need to think about most of them! However, I can give the answer for eight players immediately: I don't care which position I'm in in that case, nor what my sequence is, because someone is going to win on the third toss, and I have a 1 in 8 chance that it will be me regardless of which sequence I choose...

Gengulphus

[modellingman]

I brute-forced it (bad form, I know) using the following approach:

I used a state description with six states: if the game has not come to an end these are described by the last two coin toss results - so 4 possibilities here HH, HT, TH and TT; and if the game has come to an end the number of the winning player - so two possibilities here: 1 and 2.

Given the choices of the two players, it is possible to construct a 6*6 transition matrix for the probabilities of moving from one state to another. For example, if player 1 chooses HHH and player 2 chooses HTT, the matrix looks like

Code: Select all

      HH    HT    TH    TT    1    2
HH   0.0   0.5   0.0   0.0   0.5   0.0
HT   0.0   0.0   0.5   0.0   0.0   0.5
TH   0.5   0.5   0.0   0.0   0.0   0.0
TT   0.0   0.0   0.5   0.5   0.0   0.0
 1   0.0   0.0   0.0   0.0   1.0   0.0
 2   0.0   0.0   0.0   0.0   0.0   1.0


where the first column is the "from" state and the first row is the "to state".

The starting state occurs when the first two coin tosses have taken place. The probabilities of the six states (HH, HT, TH, TT, 1 and 2) is given by the row vector (0.25, 0.25, 0.25, 0.25, 0, 0). Pre-multiplying the the 6*6 transition matrix by this row vector (ie a 1*6 matrix) yields the row vector of state probabilities after 3 coin tosses. The process can be repeated to get the state probabilities after any number of coin tosses. I went as far as 24 tosses.

This confirms that: irrespective of Player 1's choice Player 2 can always make a choice that stacks the odds in his favour. The optimal choices and probabilities of winning for Player 2 are:

Code: Select all

Player 1   Player 2   P(Win)
HHH         THH         0.87
HHT         THH         0.75
HTH         HHT         0.67
HTT         HHT         0.67
THH         TTH         0.67
THT         TTH         0.67
TTH         HTT         0.75
TTT         HTT         0.87


A further result is that HHH (and TTT) is an extraordinarily stupid choice for Player 1 as it provides no possible advantage. Whatever Player 2 picks, Player 1's probability of winning never exceeds that of Player 2. If Player 1 chooses HHH then both players have the same probability of winning if Player 2 chooses HHT or TTT. In all other cases Player 2 has the higher probability of winning. For anyone interested, the calc's were done in Excel and I'll publish the spreadsheet.

[modellingman]

Spreadsheet here.

[UncleEbenezer]

At least, not unless well-boozed-up.

Ok, that merlot isn't one I'll be looking out for next time I buy booze, but at least I can return to this to add to what several people have posted. I'll take HHH, and let my friend Guildenstern toss the coin to be sure of victory.

But in another world ...

Julian First Great Western points out that the key is the first two throws in my choice. If mine are HH, then your selection of THH ensures that I cannot ever win unless the first two tosses are HH (with HHH that becomes the first three).

So if I'm to stand a better-than-one-in-four chance, my first two choices must be HT[1]. Now your choice will be AHT[2], so that in a steady state, you get first-strike advantage on any potential victory for me.

Sadly our dismal human coin collapses that to two cases: A=H or A=T. So (as far as I can see) we need to mess about with tedious enumeration. We have two cases for my choice: HTH and HTT. And two of potential interest for yours: HHT and THT. Modellingman has posted your choices, so there's nothing to do beyond a bit of armwaving rationale.

If my choice is HTH, yours must be HHT for a 2:1 chance of victory. THT presents the symmetric case of two mythical serpents devouring each other's tails. But HHT means that if I'm to win (other than in the first three tosses), I need a sequence of length 4. HHTH loses despite containing my choice, so only THTH can win. Thus my chance of winning is half yours, which wins on either of HHHT or THHT. Similarly if I choose HTT, your HHT leaves me needing THTT, while you have two chances with HHHT and THHT.

That's not quite the whole story. Your THT to my HTT leaves me needing HHTT, while you win on either TTHT or HTHT, right? Not quite: your TTHT is an illusion, because again, it only applies at the start of the sequence: otherwise the TT follow a H and I won. So that's another case of 50/50.

Sorry, enumeration gets tedious even through a faint merlot haze, so I'm not going to try and hack through more detail. Besides, the relics of the mathematician I once purported to be feel like a failure if we have to enumerate cases. Or using a 'puter, console ourselves with the memory of the night in the DPMMS common room when the computer proved the existence of J4.[3]

[1] You didn't suppose my abstract algebraic symbols represent prescribed faces of the coin, did you?
[2] This is an insect's coin, whose faces are Head, Thorax and Abdomen.
[3] I think you'll get the reference. I was just a lowly student at the time.

[jfgw]

Similarly for other permutations, there can be an advantage if he makes his second and third choices the same as my first and second. If I choose HHT, for example, and Gengulphus chooses THH, then, for the third and subsequent tosses, if HH came up, there would be a 50% chance that he would win (depending upon the previous toss). If he didn't win (50% chance), there would then be a 50% chance I would win on the next toss. We would have an equal chance of winning with the first three tosses (1/8 each) followed by a 2:1 ratio. This equates to a 5:3 ratio.

This does not agree with the brute force result so there must be an error. I will have another go:

If a tail is tossed, either I win immediately or I will definitely lose as I need two heads on the trot to win and, if this occurs after a tail, I lose. Sequences that result in a win for me are:
HHT (1/8 chance)
HHHT (1/16 chance)
HHHHT (1/32 chance)
etc.

The probability of me winning is 1/8 + 1/16 + 1/32... = 1/4.

The ratio is 3:1

Julian F. G. W.

[modellingman]

No thanks then

The sequence you chose gives you an advantage

I can't explain why though.

You are of course right. The odds are between 2:1 and 7:1 in Gengulphus's favour, depending on your initial choice. I'm not going to try and explain, either. At least, not unless well-boozed-up.

But, one for Gengulphus. Take the same game with three, four, five, six, seven or eight players. In each case, what position do you want your choice to be?

By no means a full answer but I was intrigued by UncleE's question. So I extended the Markov Chain model I used previously to a 3 player game. This meant I could play around. The updated spreadsheet is here.

Take the case of 3 players where Player 1 chooses HHH and Player 2 chooses THH. In the 2 player game, Player 2's choice maximises Player 2's probability of winning. However, in the 3 player game Player 3 has 6 choices available and one of these, TTH, gives Player 3 a greater probability of winning than either of Players 1 and 2. I was a little curious about this and initially suspected my model was at fault. However, having looked in a little more detail, I don't think this is the case.

For these choices, the model indicates that if the game is still active after n tosses then Player 3 always has a greater probability of winning on the next toss than Player 2.

Consider such a game after 3 tosses. If the game has not yet ended then the possibilities for the first three tosses are
1. HHT
2. HTH
3. HTT
4. THT
5. TTT
Player 2 (THH) can win on the 4th toss from only the second of these possibilities, whilst Player 3 (TTH) can win from both the third and fifth possibilities. Since these five possibilities are equally likely, Player 3's probability of winning on the fourth toss is twice that of Player 2 (and Player 1 cannot win at all).

If the game is still active after the 4th toss, then there are 7 possibilities (10 obtained from the 5 above followed by H or T, respectively less the three of these 10 that bring the game to an end on the fourth toss). These 7 possibilites are
1. HHTH
2. HHTT
3. HTHT
4. HTTT
5. THTH
6. THTT
7. TTTT
Player 2 can win from 2 of these (no's 1 and 5), whilst Player 3 can win from 4 (no's 2, 4 , 6 and 7), so again Player 3's probability of winning on the fifth toss is twice that of Player 2

Player 3's comparative advantage over Player 2 increases to 5:1 if the game is still active after 5 tosses (I'll leave that one as an exercise!) and Player 3 retains the advantage for any subsequent tosses.

More generally(*), there are 8*7=56 possible combinations in which Players 1 and 2 can make their choices. However, from Player 3's perspective, these only amount to half this number since the order in which two possibilities are eliminated from Player 3's range of choices is immaterial as far as Player 3 is concerned. Of these 28 possibilities, Player 3 can obtain a greater probability of winning than either of the other two players in 24 of these cases.

However, this leaves 4 cases where this is not possible. Denoting these by the choices not available to Player 3 these 4 cases are:
1. HHT, THT
2. HHT, TTH
3. HTH, TTH
4. HTT, THH
For three of these(no's 1, 3 and 4) , Player 3 can achieve an "equal first" probability with another Player. For no 2, Player 3's best choice provides only an "equal last" probability with another player.

As for the 4, 5, 6 and 7 player game - who knows? (though I suspect shedding insight may well involve moving even further out of the realm of puzzles).

(*) Errors and omissions excepted!

modellingman

[UncleEbenezer]

But, one for Gengulphus. Take the same game with three, four, five, six, seven or eight players. In each case, what position do you want your choice to be?

By no means a full answer but I was intrigued by UncleE's question. So I extended the Markov Chain model I used previously to a 3 player game. This meant I could play around. The updated spreadsheet is here.

Indeed. I wouldn't attempt it without the aid of a computer, either.

Where the problem I posed gets interesting is that it involves not just the stats you can generate with a model/simulation, but also an element of games theory. I believe the answers are likely to vary according to assumptions you might make about your opponents: random play vs optimal play, with the latter itself being subject to incomplete information for all players but the last.

If we'd played the game in my family, I'd've wanted to play immediately after my dad, so as to target maximal victories over him, regardless of other players.

[psychodom]

I remember studying this with Markov Chains at DPMMS (probably after your time though Uncle E?).

It's called Penney's Game/Ante after Walter Penney.
It's a classic example of a 'nontransitive' game, like Rock-Paper-Scissors:

e.g. Scissors (is beaten by) -> Rock
and Rock -> Paper
but Paper does not beat Scissors, as it would if it were transitive.

In our game:
HTH -> HHT
HTT -> HHT
HHT -> THH
HHH -> THH
THH -> TTH
THT -> TTH
TTH -> HTT
TTT -> HTT

So for whatever initial choice, a second player can choose a better play.

As an algorithm for a winning strategy, if player A chooses 1-2-3, then player B can choose (not 2)-1-2
e.g. if A chooses HTT, then B can choose (not T)HT = HHT

I think Martin Gardner wrote about it back in the day, I'll have to see if I can dig it out.

-Dom

[DiamondEcho]

Do you wish to play?

No thanks. Because if it were truly random there'd be no reason to play, there'd be no relative advantage, and it would be a waste of time. So either it'd be a time-waster, or you have identified an advantage [and I don't need to ponder further what that might be].