# Optimal strategy for tossing three dependent coins

Suppose that I have three correlated coins. The marginal probability of Head of coin $$i$$ is denoted by $$p_i$$.

The conditional probability of head for coin $$i$$ given the outcomes of coin $$j$$ and $$k$$ is denoted by $$p_i|x_j,x_k$$, where $$x_j,x_k\in\{H,T\}$$. We can similarly construct the conditional probability of $$i$$ given $$x_j$$.

Each coin can be tossed at most once and you receive a \$1 for a head and -\$1 for a tail. You don't have to toss all the coins, and your objective is to maximize the total reward.

What would be the optimal sequence of tossing coins in this case?

If the coins are independent of each other, the order wouldn't matter. The optimal strategy should be "flip coin i if $$p_i>\frac{1}{2}$$". For the case of two coins, it can be shown that it is always the best to flip the coin with a higher marginal $$p_i$$. However, this doesn't have to be optimal for three coin cases. I've been thinking about this problem for a quite long time but can't come up with a general solution or an intuition that might help..

• You can go over all strategies, and check the expected profit of each of them. There aren't so many strategies to try: $1 + 3(1+2(1+1)^2)^2 = 244$. – Yuval Filmus Feb 12 '20 at 22:44
• @YuvalFilmus, I want to generalize the strategy for the cases with more coins.. – Andeanlll Feb 13 '20 at 8:06
• Your question doesn't indicate this. Perhaps you should update your post to reflect this new information. – Yuval Filmus Feb 13 '20 at 16:22
• Also explain how the distribution is given to you in general. Are you simply given all $2^n$ individual probabilities of the possible coin tosses of $n$ coins? – Yuval Filmus Feb 13 '20 at 16:22