Maximizing expected value of coin reveal game

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

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$.

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.