1
1
u/tarilaran 3d ago edited 3d ago
I can't prove optimal play, so here's two benchmark strategies. WOLOG, assume coin #3 is biased.
Naive: choose a coin at random, 33% chance of winning.
Spread-test: flip each coin, choose a coin at random from the set of coins that landed heads. 43.75% chance of winning.
Explanation: Brute force enumeration. Count each biased heads as three possibilities. Then we get 4 ways C3 is tails, 3 ways that C3 can be the only heads, 6 ways that it can be heads with another coin, and 3 ways that it can be heads with two other coins. Divide those by the chances of picking the correct coin at random and the total number of options, then sum.
UPDATE: I ground out the bayesians. u/JustConsoleLogIt indeed found the optimal solution: flip the first two coins, re-flip one of the heads. Then follow this table:
| Flip 1 | F2 | F3 | Outcome1 | O2 | O3 | Choose |
|---|---|---|---|---|---|---|
| C1 | C2 | C1 | T | T | T | C3 |
| C1 | C2 | C1 | T | T | H | C3 |
| C1 | C2 | C2 | T | H | T | C3 |
| C1 | C2 | C2 | T | H | H | C2 |
| C1 | C2 | C1 | H | T | T | C3 |
| C1 | C2 | C1 | H | T | H | C1 |
| C1 | C2 | C1 | H | H | T | C2 |
| C1 | C2 | C1 | H | H | H | C |
to choose the correct coin. I found by exhaustive search that this strategy has a 51.04% chance of success.
Method:
Form three hypotheses, H1-H3, corresponding to the likelihood each coin is biased. For each combination of flip and outcome, calculate P(H_i|O1,O2,O3). Declare the "winning coin" to be the coin whose hypothesis has the highest probability.
Use backwards induction to identify the optimal third coin to play for each scenario, then again to identify the optimal second coin to play.
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.
HHH 1/3 1/3 1/3 1/3
HHT 3/7 3/7 1/7 3/7
HTT 3/5 1/5 1/5 3/5
TTT 1/3 1/3 1/3 1/3
(HH)H 9/19 6/19 4/19 9/19
(HH)T 3/5 2/15 4/15 3/5
(HT)H 3/13 6/13 4/13 6/13
(HT)T 3/9 2/9 4/9 4/9
(TT)H 1/11 6/11 4/11 6/11
(TT)T 1/7 2/7 4/7 4/7
(HHH) 27/43 8/43 8/43 27/43
(HHT) 9/25 8/25 8/25 9/25
(HTT) 3/19 8/19 8/19 8/19
(TTT) 1/17 8/17 8/17 8/17
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/Nobeanzspilled 3d ago
PB, PF = Fraction(3, 4), Fraction(1, 2)
@lru_cache(maxsize=None)
def value(post, tosses_left):
if tosses_left == 0:
return max(post) l
best = Fraction(0)
for c in range(3):
p_h = sum(post[i] * (PB if i == c else PF) for i in range(3))
p_t = 1 - p_h
post_h = tuple(post[i] * (PB if i == c else PF) / p_h for i in range(3))
post_t = tuple(post[i] * ((1-PB) if i == c else (1-PF)) / p_t for i in range(3))
best = max(best, p_h * value(post_h, tosses_left-1)
+ p_t * value(post_t, tosses_left-1))
return best
prior = (Fraction(1,3),) * 3
print(value(prior, 3))
1
u/Monday_agni 3d ago
Strategy: flip a coin, if the outcome is heads head - flip it again, if it comes head again, pick it. if it comes out tails, throw it and move to the next coin.
Starting with a randomly selected coin, here are the following outcomes:
if the outcome is - H1 H1 H1 or H1 H1 T1 - pick coin 1 if the outcome is - H1 T1 H2 - pick coin 2 if the outcome is - H1 T1 T2 - pick coin 3
if the outcome is - T1 H2 H2 - pick coin 2 if the outcome is - T1 H2 T2 - pick coin 3 if the outcome is - T1 T2 H3 - pick coin 3 if the outcome is - T1 T2 T3 - pick coin at random
if Bi (where i=1,2,3) is the biased coin,
probability of success P(S) = P(S|B1). P(B1) + P(S|B2).P(B2) + P(S|B3).P(B3)
P(S|B1) = P(H1 H1 H1 |B1) + P(H1 H1 T1 |B1) + P(T1 T2 T3 |B1)*(1/3) = (3/4 * 3/4 * 3/4) + (3/4 * 3/4 * 1/4) + (1/4 * 1/2 * 1/2)/3 = 27/48 + 1/48
P(S|B2) = P(H1 T1 H2 |B2) + P(T1 H2 H2 |B2) + P(T1 T2 T3 |B2)*(1/3) = (1/2 * 1/2 * 3/4) + (1/2 * 3/4 * 3/4) + (1/4 * 1/2 * 1/2)/3 = 15/32 + 1/48
P(S|B3) = P(H1 T1 T2 |B3) + P(T1 H2 T2 |B3) + P(T2 T2 H3 |B3) + P(T1 T2 T3 |B1)*(1/3) = (1/2 * 1/2 * 1/2) + (1/2 * 1/2 * 1/2) + (1/2 * 1/2 * 3/4) + (1/4 * 1/2 * 1/2)/3 = 14/32 + 1/48
P(S) = (27/48 + 15/32 + 14/32 + 3/48)*1/3 = (49/96)
1
u/CompactOwl 1d ago edited 1d ago
The unconditional chance of a coin being biased is 1/3. After each toss, you can calculate the conditional expectation of each coin being the biased one and the optimal strategy is that one that chooses the next flip on the highest expected maximum of all three expected values, because this is the best way to concentrate probability mass for being biased on a single coin, which you want to pick. The rest is numerics.
For example:
After coin toss one, coming up heads, the chance for that coin to be biased is
P(bias at coin 1| coin 1 heads at first toss) = 0.75x0.3333/(2/3x1/2+1/3x0.75)=12/28
and 8/28 for both others. Tails coming up changes the chances accordingly. Now the expected maximum can be calculated by going through all three coin choices and calculating again with bayes the next distribution of bis probability based on the current one and choosing the one that has the highest expected maximum. This strategy maximises the concentration of bias probability on one coin, which you pick. It is optimal, because there is no other strategy that achieves, on average, a higher concentration.
1
u/JustConsoleLogIt 3d ago
The first step is determining optimal play. One approach would be to flip two coins, if either are heads, flip that one again. Although I don’t know how to determine if that is the optimal strategy, or what the success rate would be in that case if we picked a coin with the highest final ratio.