Two persons engage in a game of chance.
The game is to nominate a sequence of three consecutive coin tosses [H or T].
Player one firstly nominates a sequence and then player two makes a nomination.
The game finishes when the last three tosses match either one of the players' nominations.
How can player two be assured of winning most of the time?
Given the choices that can be made by player one, what are the odds of player two winning?
Oh, it doesn't matter who tosses the coin.
The following simulation treats 1 as tails and zero as heads.
Each moving list of three tosses is coded as a binary number in the variable bval, where the current toss is added to twice (equivalent to a shift left) the preceding value mod 4 (to cut off the 3rd prior toss).
DIM rowwin(8, 8)
FOR tr = 1 TO 100000
hct = 0: tct = 0
toss = INT(2 * RND(1))
bval = 2 * (bval MOD 4) + toss
tct = tct + 1
IF tct > 2 THEN
IF had(bval) = 0 THEN
had(bval) = 1
FOR i = 0 TO 7
IF had(i) = 0 THEN
rowwin(bval, i) = rowwin(bval, i) + 1
hct = hct + 1
LOOP UNTIL hct = 7
IF tr MOD 10 = 0 THEN
FOR row = 0 TO 7
FOR col = 0 TO 7
LOCATE row + 1, col * 7 + 1
PRINT USING "#.####"; rowwin(row, col) / tr;
player First player chooses
choice HHH HHT HTH HTT THH THT TTH TTT
HHH 0.0000 0.4992 0.4004 0.4011 0.1258 0.4171 0.3016 0.5020
HHT 0.5008 0.0000 0.6653 0.6685 0.2501 0.6235 0.5031 0.7045
HTH 0.5996 0.3348 0.0000 0.5010 0.5015 0.4987 0.3761 0.5856
HTT 0.5989 0.3316 0.4990 0.0000 0.4984 0.4994 0.7511 0.8784
THH 0.8742 0.7499 0.4985 0.5016 0.0000 0.4982 0.3362 0.6051
THT 0.5829 0.3765 0.5014 0.5006 0.5018 0.0000 0.3333 0.6026
TTH 0.6984 0.4969 0.6239 0.2489 0.6638 0.6667 0.0000 0.5051
TTT 0.4980 0.2955 0.4144 0.1216 0.3949 0.3975 0.4949 0.0000
The table shows the 2nd player's probability of a win given the various options he can choose. Players can't choose the same set.
It looks like HHH can be beaten by THH,and in fact, the only way that HHH can win in this pairing is if HHH leads off the run, with probability 1/8, giving the second player a probability of 7/8 of winning.
It looks like the best strategy for defeating HHT is with THH. The former can win only if the first two tosses are HH, otherwise the second player wins. The second player in this case has 3/4 probability of winning.
To counter HTH, it's best to select HHT. Any initial T's can be ignored. After that, any HH pair is a win for player 2 unless an HTH comes up first. After the initial T's are discarded, the first of course is an H. There's a 1/2 probability that the next one is an H (leading to a win) and a 1/4 probability that the next two are TH (leading to a loss) and a 1/4 probability of TT, leaving us back at the beginning, discarding T's. These subsequent probabilities are all in a 1/2 to 1/4 ratio of win to lose and so the overall probability is 2/3, agreeing with the observed simulation result.
If the first player chose HTT, the second should use HHT also. Again, any initial T's can be ignored. Again any HH pair will be a win for player 2, unless in this case HTT comes up first. The first toss after the initial T's are thrown away is H. There's a 1/2 probability that the next one is an H (leading to a win) and a 1/4 probability that the next two are TT (leading to a loss) and a 1/4 probability of TH, leaving us back with no winner yet and a startoff with an initial H. The probability is again 2/3 of a second-player win as in the preceding paragraph.
The replies to the remaining player-1 choices can be obtained just by swapping all instances of H and T in the above descriptions of strategy.
If player 1 knows these things, he should choose HTH or THT to minimize player 2's optimal strategy. That makes player 2's probability of winning 2/3.
Posted by Charlie
on 2013-06-13 17:52:15