A man in a trench coat approaches you and pulls an envelope from his pocket. He tells you that it contains a sum of money in bills, anywhere from $1 up to $1,000. He says that if you can guess the exact amount, you can keep the money. After each of your guesses he will tell you if your guess is too high, or too low. But! You only get nine tries. What should your first guess be to maximize your expected winnings?
My solution is based on a basic, yet elegant, strategy. The first guess can be selected arbitrarily between $1 and $1000 - let’s say here that my first guess is $500. If my guess is correct, then I win (yay!). But since I have just a 1 in 1000 probability of guessing correctly on the first try, I’m probably not done. So if the trenchcoat man says the actual value is higher, my next guess will be the midway point between my first guess and the maximum possible value. Initially, this will be $1000. If the trenchcoat man says the actual value is lower, my next guess will be the midway point between my first guess and the minimum possible value ($1).
So let’s say my guess is too low and the actual value is higher. My second guess would be $750. If I’m correct, I win. If the actual amount is lower, my next guess will be the midpoint between $500 and $750 - remember that I now know it must be within this range.
I can iterate through this process with up to 9 guesses. At that point, if I still have not guessed the amount, I lose.
To simulate this process in R, I wrote the following function
As an example, let’s say the actual amount of money is $736 and my first guess is $500. Here’s how that would play out:
This tells me the different guesses, as well as the fact that I eventually won (win = 1) in the ninth round.
Of course, there is no reason why I have to choose $500 for my initial guess. What if I instead started at $1?
Clearly not the best initial guess. I wasted my first guess and ended up not winning the money. But how do we know which initial guess provides the highest expected value? That is, the initial guess that maximizes my potential winnings regardless of the actual amount of money held by the trenchcoat man?
To answer that question, I calculate the results for every potential initial guess (each integer between 1 and 1000) and every potential actual amount of money (again, each integer between 1 and 1000). This results in 1,000,000 different potential game states. From there, we can calculate the average winnings for each initial guess. These average winnings are the expected value, or what we might expect to win if we always use that amount for the initial guess.
In order to do this in R, I use the Vectorize function to expand my original function to work with multiple game states.
Now that we have all the potential outcomes of the game, I can calculate the expected winnings for each initial guess and find the best starting point.
So if you get up to nine guesses, your first guess should be $744. Why is it not $500? Shouldn’t that be optimal, since it minimizes the potential range of values for which you’ll need to initially account? Well, not quite.
There are a range of initial guesses that provide you the same overall win rate.
The win rate for initially guessing $300 is the same as for initially guessing $600 - 51.1%. However the expected value for initially guessing $300 is just $204, compared to initially guessing $600 ($281). Which actual values can you win before you run out of attempts?
This is the crux: lower starting guesses allow you to win at the same rate, but the value of each set of winnings is lower.
More (or Fewer) Guesses
But what if we modify the game rules so that you get fewer guesses? Or more guesses? How does the number of attempts change the optimal starting guess?
Here I do the same thing as before, but I vary the number of tries the player gets for each set of simulations.
The fewer guesses you receive, the higher your initial guess must be to maximize your expected winnings. If you had 12 11 or more guesses, it simply does not matter what your initial guess is: you can always win using my proposed strategy.
11 is the minimum number of guesses needed to guarantee victory.
Update 2: $744 or $745?
Others have found the optimal starting guess to be $745. This discrepancy is based on how you round each guess. The default R approach to rounding is complicated, but adheres to international standards.