6
$\begingroup$

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?

$\endgroup$

3 Answers 3

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Good derivation. There is one typo on the second line, I guess. $\endgroup$
    – EmG
    Aug 19, 2021 at 12:34
  • $\begingroup$ @EmG: I don’t think so: $\binom{100}k=\binom{100}{100-k}$, I factored out the $2^{-100}$, and everything else is unchanged. $\endgroup$ Aug 20, 2021 at 18:16
  • $\begingroup$ To give an intuition on why the answer (minus $50$) should be around $4$, we can consider our payout as $\mathbb(E)|X - 50|$, where $X \sim Bin(100, 1/2)$ with variance $\sigma^2 = 25$. Using a normal approximation, and folding the distribution across the mean to get a half-normal distribution, we get a mean of $\sqrt{2\sigma^2/\pi} = \sqrt{2\times (25/\pi)} \approx \sqrt{2\times 8} = 4$. This (more precisely $3.9894...$) is accurate to $0.25\%$ of the exact profit calculated by Brian M. Scott above. $\endgroup$ Nov 4, 2021 at 22:13
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Actually, the maximum is at $m=23$, with $v(23)\approx0.54062$, so tricky issues after all :-). But $F(m)$ for odd $m$ is concave, so we can't do better than use $25$ for each batch; any combination of $4$ odd values that average to $25$ would be worse, and doing $5$ batches of $20$ would be considerably worse. So I think the solution stays the same. $\endgroup$
    – joriki
    Apr 26, 2020 at 8:00
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Please explain your down-vote. I did not continue the calculations (Brian M. Scott e.g. later easily found a nice expression), as this did not seem to be the focus-point of the question. $\endgroup$
    – Furrer
    Sep 18, 2016 at 15:17
  • $\begingroup$ Yes, unexplained downvotes are a nuisance. I upvoted to compensate; the answer isn't as complete as the others but certainly not bad enough to warrant a negative vote total. $\endgroup$
    – joriki
    Apr 26, 2020 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.