It is an interview question：
You toss 4 fair coins, you will win 1 for each head. After the tossing, you can choose any 2 of them to retoss again. You can take such retoss any times you want. What is the expected value for this game under optimal strategy?
I think it is a Markov chain problem, we have 6 states: S(start), 4H, 3H1T, 2H2T, 1H3T, 4T. 4H must be a stopping(absorbing) state, however I am not sure for the left states, roughly think probability of increasing of value is larger than decreasing after retoss. Then does that mean we will stop until we get 4H?
Best Answer
I have interpreted your question in three different ways. I will answer all
Interpretation 1:
You can retoss any two coins and toss them again as much as you like.
In this case, our expectation is simply $4$. We keep tossing tails until we get all heads. Even if this means picking up and re-tossing a tails and heads (which alone doesn't increase our expectation) with probability $1$ we will reach $HHHH$
Interpretation 2:
Once you finished flipping the four coins, you are once permitted up to two re-tosses of any two coins. You may not use both or even one and re- tosses can be used on the same coin. This, I think, is a much more likely question from a quant firm.
Let $S$ denote the random variable on how many heads you have tossed. I will write $S$ like this:
$S$ = $X_1 + X_2 + X_3 + X_4 + \mathbb{1}_{A_1}X_5 + \mathbb{1}_{A_2}X_6$
$X_i$ is $1$ if the $i^{th}$ coin is Heads and $0$ if it is Tails. The $A_i$ are the events that involve us tossing the coins in the first place. For example if we tossed $HHHH$ we would not use any re-tosses. As $A_1$ depends only on $X_1,X_2,X_3$ and $X_4$ it is independent of $X_5$. Similarly, $A_2$ depends only on $X_1$ to $X_5$ So by linearity and independence:
$\mathbb{E}[S] = \sum\limits_{i=1}^4 \mathbb{E}[X_i] $ + $\mathbb{P}[A_1]\mathbb{E}[X_5] + \mathbb{P}[A_2]\mathbb{E}[X_6]$
$\mathbb{E}[X_i] = \frac{1}{2}$ for fair coins.
We only don't use the first retoss if all $4$ of the first coins are heads and so $\mathbb{P}[A_1] = 1- \frac{1}{2^4} = \frac{15}{16}$.
Similarly we only don't use the sixth toss if we tossed all heads right away or if we tossed $3$ heads and our first re-toss was a heads. Hence $\mathbb{P}[A_2^c] = \frac{1}{2^4} + \binom{4}{3}\cdot\frac{1}{2^4} \cdot \frac{1}{2} = \frac{3}{16}$ Hence $\mathbb{P}[A_2] = \frac{13}{16}$
And so $\mathbb{E}[S] = 2.875$
Which is slightly less than $3$ as expected as tossing $6$ coins strictly dominates this.
Interpretation 3:
Once you toss the $4$ coins you make a choice, either to retoss $2$ coins in which case you must hearby select $2$ coins and toss them both or you do nothing.
The strategy here is clear. Tossing $2$ coins has expectation $1$ and so you should only ever retoss $TT$ if you can.
You can do this manually by working out your EV conditioned on the first $4$ coin tosses or you can use my indicator variable system again which I will show.
$S = X_1 + X_2 + X_3 + X_4 + \mathbb{1}_{A}(X_5+X_6)$
We only retoss if we have had $0,1$ or $2$ heads which happens with probability $\frac{11}{16}$ and so $\mathbb{E}[S] = 2 + \frac{11}{16} = 2.6875$
Which again is less than my Second Interpretation because this is strictly dominated by it due to less flexibility in re-tosses, before we got to retoss if we had $3$ heads but here we do not.
Ask lots of questions in technical interviews, they are deliberately ambiguous to see what information you recognize to be missing, work out which of these interpretations is valid. Good luck!
Edit:
Interpretation 4:
You are forced to reflip two coins irrespective of the results, however, you do have a choice in the matter of what two coins are reflipped.
Let $R$ for "residue" denote the expected change you gain when forcibly retossing.
You have either $2$ tails to toss, only $1$ or $0$ with respective probabilities $\frac{11}{16} , \frac{4}{16} , \frac{1}{16}$
In the first case your EV increases by $1$ , the second it is unchanged and in the third, it decreases by $1$.
Hence $\mathbb{E}[R] = \frac{10}{16} $ and so the expected value of this game is $2+\frac{10}{16} = 2.625$