You are playing a game where you are betting on the outcome of coin flips. Playing the game costs $1 and you get to guess either heads or tails. A coin is then flipped and if you guessed correctly you win back your $1 and another $1, if you guessed wrong you lose your $1. You may play the game as many times as you want as long as you have the money to continue, or may quit anytime. Before the game, you have access to a genie that will answer any one yes/no question about the coin flip game. The genie knows the results of all the coming flips. Given that you start the game with $N, find a strategy that maximizes your winnings.
Earlier I had posed the problem stating that the genie knew the future, but that can cause weird possible questions involving not having a well posed question. Anyway, the intention is that the genie be capable of answering your question solely knowing what the coin flips are going to be. If a genie who knows the outcome of random events bothers you, we can instead suppose all the flips have been determined ahead of time and the genie simply has access to all the results.
Clearly with no genie, the only thing you can do will have an expected final outcome average of $N, since the game is fair for all strategies, so the question is to find out how much the one bit of information the genie gives you is worth. One thing I found interesting about this problem is that you can also prove optimality of the correct answer.
3 comments:
I know how to win a dollar! That's good right? The answer is to ask if the first flip is heads... O_o
How about a slightly better bad answer:
"Are there more heads than tails in the first N flips?"
If yes, say heads every time, if no, say tails every time. At worst you'll break even.
You should be able to do better by figuring out when you should quit the game. If there's a critically huge string of victories then I need to stop playing... statistically anyway.
Those my initial thoughts. That and the title 'bit in a bottle' is clever.
How much initial money do you have?
If you only have $1 you NEED to get the first one right... There is a losing condition given, but how much do you need to lose in order to LOSE-lose.
You have $N initially, as stated in the problem.
If you only have $1, you don't NEED to get the first one right, unless you want to guarantee the money you end with. It is possible to come up with a strategy that simply maximizes the expected money you end with.
The strategy that I use for the answer does guarantee the money you end with though, rather than expected value (so, in the N=1 case, it simply asks "is the outcome of the first flip heads?", and plays only that one flip). I am not sure how large the class of strategies that maximizes expected money is.
Post a Comment