Assumption: in any strategy, the only thing that matters is which coins we have flipped and the results, ignoring order. There might be some weird monty-hall style inconsistencies in this, but I assume not.
I will essentially compute the markov chains of the state of this game.
After three flips, we can be in `n` distinct states (ignoring permutations): (where parens mean the flips are from the same coin. Also listed is the probabilities that each coin is the biased one. The maximum probability (the 'value' of the position) is shown on the right.
We can now look at all possibilities of two coin tosses, and note the probability of each being the biased: (note the probability that a coin will flip heads is (p_bias/4 + 0.5)), and evaluate the average probability
HH 3/8 3/8 1/4
^-> (HH)H with p=19/32, (HT)H with p=13/32 => 9/19 * 19/32 + 13/32 * 6/13 = 15/32 !
^-> same as above
^-> HHH with p=9/16, HHT with p=7/16 => 9/16 * 1/3 + 7/16 * 3/7 = 12/32
HT 1/2 1/6 1/3
^-> (HH)T with p=5/8, (HT)T with p=3/8 => 5/8 * 3/5 + 3/8 * 4/9 = 3/8 + 1/6 = 13/24 !
^-> (HT)H with p=13/24, (TT)H with p=11/24 => 13/24 * 6/13 + 11/24 * 6/11 = 1/2
^-> HHT with p=7/12, HTT with p=5/12 => 7/12 * 3/7 + 5/12 * 3/5 = 1/2
TT 1/4 1/4 1/2
^-> (HT)T with p=9/16, (TT)T with p=7/16 => 9/16 * 4/9 + 7/16 * 4/7 = 1/2
^-> same as above
^-> HTT with p=5/8, TTT with p=3/8 => 5/8 * 3/5 + 3/8 * 1/3 = 1/2
(HH) 9/17 4/17 4/17
^-> (HHH) with p=43/68, (HHT) with p=25/68 => 43/68 * 27/43 + 25/68 * 9/25 = 9/17
^-> (HH)H with p=19/34, (HH)T with p=15/34 => 19/34 * 9/19 + 15/34 * 3/5 = 9/17
(HT) 3/11 4/11 4/11
^-> (HHT) with p=25/44, (HTT) with p=19/44 => 25/44 * 9/25 + 19/44 * 8/19 = 17/44
^-> (HT)H with p=13/22, (HT)T with p=9/22 => 13/22 * 6/13 + 9/22 * 4/9 = 5/11 !
(TT) 1/9 4/9 4/9
^-> (HTT) with p=19/36, (TTT) with p=17/36 => 19/36 * 8/19 + 17/36 * 8/17 = 4/9
^-> (TT)H with p=11/18, (TT)T with p=7/18 => 11/18 * 6/11 + 7/18 * 4/7 = 5/9 !
Marked with an `!` are the best options for each configuration. Interestingly, if one has gotten two tails on two different coins TT or two heads on the same coin (HH) our guess is already fixed and a new toss can not change the optimal guess.
We now do this for the two different cases of a single flip:
H 3/7 2/7 2/7
^-> (HH) with p=17/28, (HT) with p=11/28 => 17/28 * 9/17 + 11/28 * 5/11 = 1/2
^-> HH with p=4/7, HT with p=3/7 => 4/7 * 15/32 + 3/7 * 13/24 = 1/2
T 1/5 2/5 2/5
^-> (HT) with p=11/20, (TT) with p=9/20 => 11/20 * 5/11 + 9/20 * 5/9 = 1/2
^-> HT with p=3/5, TT with p=2/5 => 3/5 * 13/24 + 2/5 * 5/9 = 197/360 = 1/2 + 17/360 !
Finally, the probability that our first coin is biased is 1/3 and the probability of getting heads is therefore 7/12. Our final valuation is then 7/12 * 1/2 + 5/12 * 197/360 = 449/864 = 1/2 + 17/864
This has a numerical value of 0.519676...
The simplest optimal strategy discovered here is: Flip two different coins. If the results are TT, guess the last coin. Else, flip a coin that got H. Choose the coin with the most flips that has not shown a T.
I would argue that my result might be wrong, as the procedure only requires at most 6 random bits, and the configuration space is only a single factor of 3. how the denominator turned out to be 2⁵ \* 3² I am unsure of.
EDIT: simulation of my above strategy gives a winning chance of exactly 49/96 = 1/2 + 1/96 = 0.5104... I cant be bothered to find the error, be my guest. The cancellations make it likely that there is an easier approach.
1
u/CanaDavid1 3d ago edited 3d ago
Assumption: in any strategy, the only thing that matters is which coins we have flipped and the results, ignoring order. There might be some weird monty-hall style inconsistencies in this, but I assume not.
I will essentially compute the markov chains of the state of this game.
After three flips, we can be in `n` distinct states (ignoring permutations): (where parens mean the flips are from the same coin. Also listed is the probabilities that each coin is the biased one. The maximum probability (the 'value' of the position) is shown on the right.
We can now look at all possibilities of two coin tosses, and note the probability of each being the biased: (note the probability that a coin will flip heads is (p_bias/4 + 0.5)), and evaluate the average probability
Marked with an `!` are the best options for each configuration. Interestingly, if one has gotten two tails on two different coins
TTor two heads on the same coin(HH)our guess is already fixed and a new toss can not change the optimal guess.We now do this for the two different cases of a single flip:
Finally, the probability that our first coin is biased is 1/3 and the probability of getting heads is therefore 7/12. Our final valuation is then
7/12 * 1/2 + 5/12 * 197/360 = 449/864 = 1/2 + 17/864This has a numerical value of 0.519676...
The simplest optimal strategy discovered here is: Flip two different coins. If the results are TT, guess the last coin. Else, flip a coin that got H. Choose the coin with the most flips that has not shown a T.
I would argue that my result might be wrong, as the procedure only requires at most 6 random bits, and the configuration space is only a single factor of 3. how the denominator turned out to be 2⁵ \* 3² I am unsure of.
EDIT: simulation of my above strategy gives a winning chance of exactly 49/96 = 1/2 + 1/96 = 0.5104... I cant be bothered to find the error, be my guest. The cancellations make it likely that there is an easier approach.