Consider a fair coin, tossed 100 times to create a sequence of $H$s and $T$s.
A participant is allowed to ask 1 yes or no question (e.g. was the first coin flip heads?), then plays a game where he tries to guess all 100 coins. The participant is awarded $\$1$ for every coin guessed correctly, and loses $\$1$ for each incorrect guess. Find and prove an optimal strategy for the player.
I have a hunch that the optimal strategy may be to ask "Were there more heads than tails?" and then, depending on the answer, proceed to guess either all $H$s or all $T$s. With this strategy, the player is guaranteed nonnegative earnings, and I believe the expected value is $$\sum_{i=0}^{50}{\binom{100}{i}\left(\frac{1}{2}\right)^{99}(100-2i)} \approx \$7.96$$
I've confirmed the expected value with a Monte-Carlo simulation in Python, but I'm having trouble proving that this is optimal.
My best attempt to translate this into more rigorous mathematics is to consider the yes/no question as a partition. Let $X$ be the set of $2^{100}$ possible sequences and $x$ be the sequence rolled. A yes/no question will always partition the set into two. Suppose that set $A$ is the set of all sequences in which the answer to our question is "yes", then the expected value of our game would be $$E[G] = \frac{|A|}{2^{100}}E[G|x\in A]\space + \left(1-\frac{|A|}{2^{100}}\right)E[G|x \notin A],$$
where G is the expected value of the game, playing with some optimal strategy. I've also made the note that given any specific set $A$, $x \in A$ implies there is an optimal (but not necessarily unique) guess. For instance, if we know that there are more heads than tails, a sequence of 100 $H$s is an optimal guess.
from Hot Weekly Questions - Mathematics Stack Exchange
user815048
Post a Comment