I was asked this question today in an interview and am still not sure of the answer. The question is as follows.
Part one:
Say I have flipped 100 coins already and they are hidden to you. Now I reveal these coins one by one and you are to guess if it is heads or tails before I reveal the coin. If you get it correct, you get $\$1$. If you get it incorrect, you get $\$0$. I will allow you to ask me one yes or no question about the sequence for free. What will it be to maximize your profit?
My approach for this part of the problem was to ask if there were more heads than tails. If they say yes, I will just guess all heads otherwise I just guess all tails. I know the expected value for this should be greater than 50 but is it possible to calculate the exact value for this? If so, how would you do it?
Part two:
Same scenario as before but now I will charge for a question. I will allow you to ask me any amount of yes or no questions as I go through this process for $\$1$. What is your strategy to maximize your profit?
I was not sure about the answer to this part of the question. Would the best option be to guess randomly? I think the expected value of this should be 50. I am not sure about the expected value of part one but if it is greater than 51, I think I could also use that approach. Anyone have a good idea for this part?
Best Answer
It’s not too hard to calculate the expected value of your strategy for the first problem.
Let $k$ be the number of heads. If you’re told that there are more heads than tails, and on that basis you guess heads every time, you’ll win $k$ dollars. If you’re told that there are not more heads than tails, and you guess tails every time, you’ll win $100-k$ dollars. The probability that there are $k$ heads is $2^{-100}\binom{100}k$, so your expected winnings are
$$\begin{align*} &\sum_{k=0}^{50}2^{-100}\binom{100}k(100-k)+\sum_{k=51}^{100}2^{-100}\binom{100}kk\\ &\qquad=2^{-100}\left(\sum_{k=0}^{50}\binom{100}{100-k}(100-k)+\sum_{k=51}^{100}\binom{100}kk\right)\\ &\qquad=2^{-100}\left(\sum_{k=50}^{100}\binom{100}kk+\sum_{k=51}^{100}\binom{100}kk\right)\\ &\qquad=2^{-100}\left(50\binom{100}{50}+2\sum_{k=51}^{100}\binom{100}kk\right)\\ &\qquad=2^{-100}\left(50\binom{100}{50}+2\sum_{k=51}^{100}100\binom{99}{k-1}\right)\\ &\qquad=2^{-100}\left(50\binom{100}{50}+200\sum_{k=50}^{99}\binom{99}k\right)\\ &\qquad=2^{-100}\left(50\binom{100}{50}+100\sum_{k=0}^{99}\binom{99}k\right)\\ &\qquad=2^{-100}\left(50\binom{100}{50}+100\cdot2^{99}\right)\\ &\qquad=50\left(1+2^{-100}\binom{100}{50}\right)\\ &\qquad\approx \$53.98\;. \end{align*}$$