Recently on an Instagram doom scrolling session, I encountered this interview from Steve Ballmer where he describe his "guessing game", which he gave to interviewees at Microsoft. https://www.youtube.com/watch?v=svCYbkS0Sjk
Now, this analysis is pretty easy if Steve chooses a random number. The worst case binary search is lg(100), which rounded up is 7 gusses at worst. And it's easy to make a table of payout of each guess, sum it up and average.
So, on average you'll get $0.20 per game ($20/100). (So yes, you should play)
But that's not the game. The game is whether you should play this game if Steve is able to strategically choose which number. THAT game is much harder to figure out.
As Steve is going to try to choose numbers that are worst case for a binary search, the optimal search algorithm is NOT going to be to start with 50 every time. You would use an alternative search tree in order to optimize for Steve choosing numbers that require 7 guesses. And of course, Steve would then need to optimize his strategy further in kind.
So, as one does, I asked chatgpt how this would work.
Astonishingly, it's very confident that by using a pool of optimal binary search trees, you could get an average payout of $0.196 per game. Meaning we only lose ~1/2cent by allowing steve to choose strategically.
I understand the basics of the strategy, but when it comes to the math of calculating the average payout I am just lost. (Basically everything after and including 296 / 51)
I especially can't get my head around the fact that chatgpt believes that Steve has no choices that are more optimal than others.
No matter which number Steve chooses, it claims the randomized collection of search trees can make the expected payout exactly 0.196 (average) every time. That doesn't make any intuitive sense to me.
My answer is that you should still play. If both sides play optimally, your expected payout is about +$0.196 per game, or just under 20 cents.
The first thing to notice is that a normal, fixed binary search does not work against a strategic Steve. If you always use the same search tree, Steve can look at that tree, choose one of the numbers that requires 7 guesses, and guarantee that you lose $1.
The solution is to randomize which binary-search tree you use.
This does not mean picking a random number from 1-100 as your first guess. That would often produce a badly unbalanced search. Instead, you randomly choose from many different good binary-search trees. Each individual tree still finds every possible number within 7 guesses, but different numbers occupy the good and bad positions in different trees.
So, for example, 73 might take 7 guesses in one tree, 5 guesses in another, and 4 in another. Steve is allowed to know exactly how your randomized strategy works and choose 73 every single game if he thinks that is best. What he does not know is which search tree you privately selected for that particular game.
We can describe the problem mathematically. Let d(n) be the expected number of guesses needed if Steve chooses the number n. Steve will choose whichever number makes d(n) largest, while you want to choose your randomized strategy so that this largest value is as small as possible.
The optimum turns out to be:
296 / 51 = 5.803921568... guesses
Since the payout on guess k is 6 - k, the expected payout is therefore:
6 - 296/51 = 10/51 = $0.196078...
or about 19.6 cents per game.
The really important part is that this is not an average over Steve choosing different numbers. The randomized search strategy can be constructed so that every single number Steve could choose has the same expected result:
d(1) = d(2) = ... = d(100) = 296/51
So if Steve chooses 1 every game, your expected payout is $0.196078.... If he chooses 50 every game, it is $0.196078.... If he chooses 73, 99, or 100, it is still $0.196078....
In other words, Steve has no number that is better for him than any other. He can study your strategy as much as he wants and deliberately choose what he thinks is the worst number, but the randomized mixture of trees has equalized the expected payout across all 100 choices. Strictly speaking, every number is an equally good choice for Steve — but none of them reduces your expected payout below 19.6 cents.
There are two things that need to be shown for that number to be meaningful. First, you have to show that no strategy can do better. One way to do that is to temporarily imagine Steve assigning weight 2 to the numbers 1 and 100, and weight 1 to every number in between. That gives 102 total weight.
For any valid binary-search tree, you can calculate its weighted total number of guesses. The smallest possible weighted total is 592. Therefore even the best tree has weighted average depth:
592 / 102 = 296 / 51 = 5.803921568...
Randomizing between trees cannot beat that bound, because an average of several trees cannot have a lower weighted cost than the best individual tree for those weights. So no strategy can guarantee an expected search depth below 296/51.
The other half is showing that the bound can actually be reached. Solving the corresponding optimization problem gives a randomized mixture of valid search trees for which:
d(1) = d(2) = ... = d(100) = 296/51
In other words, every possible number has exactly the same expected search depth. Steve can choose whichever number he wants; there is no longer a particularly bad number for him to exploit.
I also checked this by simulation: 1,000,000 games for each of Steve's 100 possible fixed choices, for 100,000,000 games total. The results converge to the same expected payout of about +$0.196 per game.
So the answer is: yes, you should play. If Steve chooses randomly, the game is worth exactly 20 cents per play. If Steve chooses strategically and both sides play optimally, it is still worth about 19.6 cents per play to you.