Maximizing expected value of coin reveal game

Question

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?

Answer 1

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*}$$

Answer 2

To approach part 2 of your question:

What if I asked your question multiple times, for some subsets of the coins? Is there perhaps a 'divide and conquer' strategy we can use here?

Let's first generalize Brian M. Scott's approach: let $F(m)$ be the expected return, given that the answer to the question "are there more heads than tails in these $m$ coins?" is known.

Then:

$$F(m) = \sum_{k=0}^{\lfloor{m/2}\rfloor}2^{-m}{m \choose k}(m-k) + \sum_{k=\lfloor{m/2}\rfloor+1}^{m}2^{-m}{m \choose k}k $$ $$ = 2^{-m} \left( \sum_{k=m-\lfloor{m/2}\rfloor}^{m}{m \choose k}k + \sum_{k=\lfloor{m/2}\rfloor+1}^{m}{m \choose k}k \right) $$

When $m$ is even, $m - \lfloor{m/2}\rfloor = \lfloor{m/2}\rfloor = m/2$, and we get the result Brian M. Scott gave:

$$F(m) = \frac{m}{2} \left( 1 + 2^{-m} {m \choose \frac{m}{2}} \right)$$

When $m$ is odd, $m - \lfloor{m/2}\rfloor = \lfloor{m/2}\rfloor + 1$, and so with similar manipulations (a few steps combined here for brevity), we get:

$$F(m) = 2^{-m} \left( \sum_{k=\lfloor{m/2}\rfloor+1}^{m}{m \choose k}k + \sum_{k=\lfloor{m/2}\rfloor+1}^{m}{m \choose k}k \right) $$ $$= 2^{-m} \left( 2 \sum_{k=\lfloor{m/2}\rfloor+1}^{m}m{m-1 \choose k-1}\right) $$ $$= 2^{-m} m\left(\sum_{k=0}^{m-1}{m-1 \choose k} + {m-1 \choose \lfloor{m/2}\rfloor}\right)$$ $$= 2^{-m} m\left(2^{m-1} + {m-1 \choose \lfloor{m/2}\rfloor}\right)$$ $$= \frac{m}{2}\left(1 + 2^{-(m-1)} {m-1 \choose \lfloor{m/2}\rfloor}\right)$$ $$ = \frac{m}{m-1}F(m-1)$$

Now, we can define the expected per-coin payoff for a group of $m$ coins when we know wheteher there are more heads or not at a cost of $\$1$, as:

$$v(m) = \frac{(F(m)-1)}{m}$$

It turns out that this function is maximized at $m=25$, with $$v(25) \approx 0.54059$$

(And fortunately $25$ divides $100$, so no tricky issues!!).

So the optimal strategy appears to be: separate the coins into four equal sized groups of 25, and ask the question 4 times; total estimated return $\$54.059$.

Answer 3

I assume the coin is fair, such that it is as likely to get heads as tails.

The expectation could be calculated like this, where $S$ is money won by your strategy and $N$ is the number of heads:

$ E[S] = P(N=50)\cdot 50 + \sum_{i=51}^{100} i\cdot(P(N=i)+P(N=100-i)) = P(N=50)\cdot 50 + \sum_{i=51}^{100} 2i \cdot P(N=i) $.

The thinking is the following. If the number of heads is say 57, you select heads and earn 57. If the number of heads is 43, you select tails and win 57. Special care must be taken with the number 50.

Now $N$ follows a binomial distribution $\text{bin}(100,1/2)$. Plugging the point probabilities into the above formula, the expectation can be found with any decent calculator.