Got a credit card? use our Credit Card & Finance Calculators
Thanks to Anonymous,bruncher,niord,gvonge,Shelford, for Donating to support the site
A coin-tossing game...
-
- Lemon Quarter
- Posts: 4255
- Joined: November 4th, 2016, 1:17 am
- Been thanked: 2631 times
A coin-tossing game...
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
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
-
- Lemon Quarter
- Posts: 2045
- Joined: November 4th, 2016, 10:25 am
- Has thanked: 230 times
- Been thanked: 489 times
Re: A coin-tossing game...
Probably only if I get to name my sequence second
(I think that gives me an advantage??)
(I think that gives me an advantage??)
-
- Lemon Quarter
- Posts: 4255
- Joined: November 4th, 2016, 1:17 am
- Been thanked: 2631 times
Re: A coin-tossing game...
chas49 wrote: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!
chas49 wrote:(I think that gives me an advantage??)
Well, the question is whether it gives me an advantage... ;-)
Gengulphus
-
- Lemon Quarter
- Posts: 2045
- Joined: November 4th, 2016, 10:25 am
- Has thanked: 230 times
- Been thanked: 489 times
Re: A coin-tossing game...
No thanks then
The sequence you chose gives you an advantage
I can't explain why though.
The sequence you chose gives you an advantage
I can't explain why though.
-
- The full Lemon
- Posts: 10980
- Joined: November 4th, 2016, 8:17 pm
- Has thanked: 1505 times
- Been thanked: 3050 times
Re: A coin-tossing game...
chas49 wrote: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?
-
- Lemon Quarter
- Posts: 2595
- Joined: November 4th, 2016, 3:36 pm
- Has thanked: 1121 times
- Been thanked: 1182 times
Re: A coin-tossing game...
UncleEbenezer wrote:chas49 wrote: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.
-
- Lemon Quarter
- Posts: 4255
- Joined: November 4th, 2016, 1:17 am
- Been thanked: 2631 times
Re: A coin-tossing game...
UncleEbenezer wrote: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
-
- Lemon Slice
- Posts: 638
- Joined: November 4th, 2016, 3:46 pm
- Has thanked: 625 times
- Been thanked: 377 times
Re: A coin-tossing game...
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
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:
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.
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.
-
- Lemon Slice
- Posts: 638
- Joined: November 4th, 2016, 3:46 pm
- Has thanked: 625 times
- Been thanked: 377 times
-
- The full Lemon
- Posts: 10980
- Joined: November 4th, 2016, 8:17 pm
- Has thanked: 1505 times
- Been thanked: 3050 times
Re: A coin-tossing game...
UncleEbenezer wrote: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.
-
- Lemon Quarter
- Posts: 2595
- Joined: November 4th, 2016, 3:36 pm
- Has thanked: 1121 times
- Been thanked: 1182 times
Re: A coin-tossing game...
jfgw wrote: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.
-
- Lemon Slice
- Posts: 638
- Joined: November 4th, 2016, 3:46 pm
- Has thanked: 625 times
- Been thanked: 377 times
Re: A coin-tossing game...
UncleEbenezer wrote:chas49 wrote: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
-
- The full Lemon
- Posts: 10980
- Joined: November 4th, 2016, 8:17 pm
- Has thanked: 1505 times
- Been thanked: 3050 times
Re: A coin-tossing game...
modellingman wrote:UncleEbenezer wrote: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.
Re: A coin-tossing game...
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
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
-
- Lemon Quarter
- Posts: 3131
- Joined: November 4th, 2016, 3:39 pm
- Has thanked: 3060 times
- Been thanked: 554 times
Re: A coin-tossing game...
Gengulphus wrote: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].
Return to “Games, Puzzles and Riddles”
Who is online
Users browsing this forum: No registered users and 3 guests