Good ways to approach this dynamic probability/expected value game

Question

There are 3 coins labelled A, B and C. You are told that the coins have probabilities of 0.75, 0.5 and 0.25 of landing on heads but you don't know which coin has which probability. In order to investigate, you are allowed to pay for the following options as many times as you want:

• Pay $5 to select any pair of coins, flip them both and get told how many of the coins turned up heads (you aren't told which coin lands on which side, only the sum of the number of heads e.g. if you pick pair AB to flip, if one lands on heads and the other on tails, you are just told that there was 1 head between the pair)

• Pay $15 to select one coin, flip it and see the result

Your job is to try identify the coin that has the least probability of landing on heads. You win $200 if you correctly do this. How would you play to maximize your expected earnings in this game?

Answer 1

Just to provide a framework : if you just guess which is the 0.25 coin, without flipping any coins, your expected winnings are 200/3= 66.67 dollars, so the question is whether we can beat that by flipping coins.

For example, let’s spend 15 dollars to flip a single coin. P(head)= 0.5 since it is equally likely to be the 0.25,0.5 or 0.75 coin. Also note that p(this coin is the 0.25 coin)=1/3. The point is, if we flip this coin and get a tail, maybe it tells us some useful information. Using the Bayesian formula:

P(this is the 0.25 coin|tail)= p(tail|0.25 coin)* p(0.25 coin)/p(tail)

= 0.75*(1/3)/0.5= 0.5

So if we guess this coin is the 0.25 coin our expected winnings are 0.5*200, minus the 15 fee which equals 85, an improvement.

But what if we flip a head? Then the Bayes formula gives

p(0.25 coin|head)=0.25*(1/3)/0.5= 1/6.

Here the best we can do is select at random one of the other two coins each of which must have a 5/12 chance of being the 0.25 coin , for an expected winnings of 5/12 *200 -15 = 68.3 dollars, still a slight improvement.

So this is by no means exhaustive - other coin flipping ideas need to be studied, but it seems to get complex quickly.

Answer 2

I think an appropriate way to tackle this is to label it and perform Bayesian analysis.

Consider the labels H, F, T for Head-Coin, Fair-Coin and Tail-Coin for what a coin is loaded towards.

The task is to identify the label, T, as quickly as possible to extract maximum reward, whilst possibly choosing to pay for some statistically random information. This makes the game dynamic since new information may lead to optimal strategies dependent upon that stage.

Let $P(I_1, ..., I_n, A^H, B^F, C^T)$ be the probability that coins, A, B, C are labelled as H, F, and T respectively with the outcomes of n pieces of information, each possibly obtained for some (different) cost.

At any stage a guess can be made which coin is labelled as T, obviously maximising the probability.

As an example suppose 15\$ is paid to obtain a single coin flip on A and that the result is Tails ($I_1=\{A \; flip = Tails\}$):

$$ P(I_1, A^T, B^F, C^H) = \frac{1}{6} * 0.75 = 0.125 \propto 0.250 \\ P(I_1, A^T, B^H, C^F) = \frac{1}{6} * 0.75 = 0.125 \propto 0.250 \\ P(I_1, A^F, B^T, C^H) = \frac{1}{6} * 0.50 = 0.083 \propto 0.166 \\ P(I_1, A^F, B^H, C^T) = \frac{1}{6} * 0.50 = 0.083 \propto 0.166 \\ P(I_1, A^H, B^T, C^F) = \frac{1}{6} * 0.25 = 0.042 \propto 0.083 \\ P(I_1, A^H, B^F, C^T) = \frac{1}{6} * 0.25 = 0.042 \propto 0.083 \\ $$

What we are really seeking is the state probability given the information, so:

$$P(I_1, A^X, B^Y, C^Z) = P(A^X, B^Y, C^Z|I_1) P(I_1)$$

$P(I_1)$ is 0.5, because in the absense of any other information the chance of flipping any coin at heads or tails is 50%. Consider just the top two lines here:

$$ P(I_1, A^T, B^F, C^H) = 0.125 = P(A^T, B^F, C^H | I_1) P(I_1) \\ P(I_1, A^T, B^H, C^F) = 0.125 = P(A^T, B^H, C^F | I_1) P(I_1) \\ \implies P(A^T, B^H, C^F | I_1) = 0.25 \\ \implies P(A^T, B^F, C^H | I_1) = 0.25 \\ \implies P(A^T|I_1) = 0.5 $$

At this stage the payoff is as described by @dm63 answer.

Also we can now consider a second piece of information, $I_2$. Suppose coin B is flipped an it comes up Heads.

This is where Bayesian networks get tricky. Note that,

$$P(I_2, I_1, A^X, B^Y, C^Z) = P(A^X, B^Y, C^Z | I_2, I_1) P(I_2 | I_1) P(I_1)$$

We can calculate the left side as done before in each case, we know $P(I_1)$ and we can use the state probabilities derived from $I_1$ to assess $P(I_2|I_1)$. From before,

$$ P(B^F|I_1) = 0.083 + 0.250 = 0.333 \\ P(B^H|I_1) = 0.250 + 0.166 = 0.416 \\ P(B^T|I_1) = 0.083 + 0.166 = 0.249 \\ $$

Hence B coming up Heads given $I_1$ is: $0.333 * 0.5 + 0.416 * 0.75 + 0.249 * 0.25 = 0.541 $

Thus we have our revised state estimates given $I_1, I_2$:

$$ P(A^T, B^F, C^H | I_1, I_2) = 0.231 \\ P(A^T, B^H, C^F| I_1, I_2) = 0.347 \\ P(A^F, B^T, C^H| I_1, I_2) = 0.077 \\ P(A^F, B^H, C^T| I_1, I_2) = 0.230 \\ P(A^H, B^T, C^F| I_1, I_2) = 0.039 \\ P(A^H, B^F, C^T| I_1, I_2) = 0.077 \\ $$

Thus, $A^T$ is 0.578, $B^T$ is 0.116 and $C^T$ is 0.307. The expectation in this case guessing A having spent 30\$ is 85.6\$.

In general you can expect a reinforcement learning agent to learn what to do based on its choices of guessing or playing for new information. You can use the Bayesian options as heuristics to give an agent an idea of what to play in each iteration.

Answer 3

Since you can perform option (1.) for both coins as many times as you want, if you repeat that option for N times, where N is a sufficiently large number such as 1 million, wouldn't the following combinations yield a result such as:

• A&B = (0.5 $\cdot$ 0.75 + 0.5 $\cdot$ 0.50) $\cdot$ 1,000,000 ~= 625,000 heads
• B&C = (0.5 $\cdot$ 0.50 + 0.5 $\cdot$ 0.25) $\cdot$ 1,000,000 ~= 375,000 heads
• A&C = (0.5 $\cdot$ 0.75 + 0.5 $\cdot$ 0.25) $\cdot$ 1,000,000 ~= 500,000 heads

If you obtain the latter 2 results (containing C), you can use option (2.) to identify the least probability coin i.e. C? by using said option with either of the 2 involved coins in the initial option i.e. option (1.)