Where are you getting that from? As far as I can tell, he makes no such arguments in the interview. The problem, and his explanation of the answer, are phrased purely in terms of expected value of a single iteration of the game. And the twist is the adversarial selection of the number, not risk of ruin.

It'd be an awful example of tail risk anyway. With the obvious strategy the tail is extremely fat.

Yes! The St. Petersburg "Paradox" shows that we intuitively know that. I put "paradox" in quotes because I don't think it's a paradox, it's just a sane reaction.

(Sam Bankman-Fried was a big fan of EV and famously declared that he would toss a coin where heads would double the "value" (?) of the world but tails would destroy it.)

In short, the St. Petersburg paradox goes as follows: a fair coin is tossed until heads come up, and the player wins $2^n, where n is the number of times the coin was flipped. So for example if heads come up on the first flip the player gets $2, if it comes up on the second they get $4, on the third, $8, on the tenth $1024 (2^10), etc. It's easy to show that the expected value of the game is infinite (approaches infinity).

Therefore, someone perfectly rational (?) should be willing to pay virtually any amount of money to play the game, because any finite amount of money is less than an infinite amount of money, and therefore the expected gain is always positive.

Yet you will probably not find many people (except SBF?) willing to pay millions of dollars to play that game.

It's only a paradox if we think it shows that people are not "rational". But I think it simply shows EV is not a good measure of risk, and everyone knows it.

Very complete and fascinating article about the St. Petersburg Paradox here:

https://plato.stanford.edu/entries/paradox-stpetersburg/

Unlike most people here I actually think questions like this are a decent way to see how people think. I would expect people with math/stats/cs background to be able to at least start the conversation about this problem.

However when you hide hypotheses or add your own BS constraints as a gotcha without explicitly stating them is where you lose me.

If the question is "would you play this game" the reasonable mathematical translation is "determine if the expected value is greater than zero". If you're going to talk about tail risk you need to specify utility functions (possibly asymmetric for the two players!) and you need to explicitly say that's what you mean.

To be honest, I think Steve just didn't grasp the mathematical deepness of the problem.

Betting more than the Kelly fraction increases the risk of ruin, especially in the long run.

https://en.m.wikipedia.org/wiki/Kelly_criterion

Note: Not saying that this is applicable in the original post's situation. It's relevant to the parent comment though, and very useful in many situations, such as investing.

If he was trying to make that point, why set the bet at $1 - a loss that wouldn't imperil anyone?

The situation is entirely fictional, why not fictionally gamble with a five-figure sum?

> the spread on that surely goes over the 0 line.

Do you imagine starting with $1 or $1000? :)

Let's add a condition that Ballmer has infinite money, we start with a specific budget, and we can't continue playing if we exceed budget randomly changes after each game,

In the game where you start with $N, win $1 with probability p > 0.5 and lose $1 otherwise, the chance of eventually losing all your money is (p/(1-p))^N. [1]

So, the ruin chance actually becomes exponentially lower the more money you have at the start.

The steps in the random walk above belong to a simple, Bernoulli-like random distribution. Meanwhile the mixed strategy is a more complex discrete random variable because it can do more steps than just +1 and -1.

However, I believe that the same principle applies for the mixed strategy.

If you zoom out and consider "batches" of steps, you can apply the Central limit theorem and see that all these random walks work roughly the same. The caveat being that you need a large enough starting budget to "zoom out" :)

Granted, the standard deviation for the mixed strategy is ~$1. I would guesstimate that if you start with ~$1000, there's no way you will ever lose your money.

> What would be more interesting is to monte carlo simulate this strategy and look at the win/loss distribution. Presumably the choice is then not so clear cut.

Agree, this would be a nice demonstration! I will think about doing this next time I get a couple of hours of free time.

[1] https://math.stackexchange.com/a/153141/65143

You're calling an all-in 100% of the time in a cash game if your expected value is positive. If you don't, you can't afford to play at that table.

You're not going all-in with any hand expected to win because that's not how you maximize profit. It has nothing to do with the risk of going bankrupt. Because again, if that's a concern you shouldn't be sitting at the table.

Tournament poker is a bit different because there are certain points where you have positive chip EV and negative $ EV and the math changes.

This is absolutely true. All it takes is to understand that for the single person, the model isn't ergodic but all expected value based models assume ergodicity.

See [section 4 here](https://www.jasoncollins.blog/posts/ergodicity-economics-a-p...) on losing wealth on a positive value bet.

And some of the patterns are just obviously suboptimal if this is your only chance:

> With probability 0.9686%: Binary search, first guess is 1.

(I wonder what Ballmer would think that, when proposed to play this game, you first manually throw dice to draw a random number in the range 1 - 1,000,000 and if it's 9,686 or less, you start your binary search at 1. He might be impressed by your dedication to the mixed strategy.)

I think people are missing the forest for the trees on it mattering if Balmer was "right" or "wrong".

It's his interview question. He's using it as a way to see your thought process more than the answer you arrive at at the end.

I imagine if interviewees had these thoughtful disagreements, he'd either guide them to the reason he had a different answer or value their input.

that said, the problem screams binary search and you know your opponent is a computer person, so i guess the question is: if you make a bet that your opponent is making an adversarial choice that assumes you're going to do a vanilla binary search, can you improve your odds of coming out ahead by modifying your own binary search to always assume the target is an adversarial one?

If I were to take the bet with him, I'd make him write down the number first hide it (turn the paper over / put it under a book, whatever).

The initial set of strategies wasn't very diverse and compensated for the binary search "weaknesses" on the ends of the spectrum by sometimes guessing 1 and 98.

But after adding some more pure strategies to the set, we've got a far better mixed strategy that prefers the numbers between 28-70 as the first pick: https://github.com/gukoff/ballmer_puzzle#winning-strategy

As others said, if you don't expect adversary behavior in your data, it should be good enough.

> If Ballmer is choosing his secret number uniformly at random, then the expected value of the game is [that you win $0.20]. But, as Ballmer points out in the linked video, if he knows you’re going to do a plain old binary search, then he certainly won’t ever choose 50 as his secret number. In fact, he has no reason to choose 25 or 75 either. Or 12, 13, 37, 38, 62, 63, 87, or 88. If Ballmer avoids those eleven numbers, and chooses uniformly at random from among the rest, that alone is enough to lower the expected value of the game from [$0.20] to about [−$0.0045].

So I think Ballmer was being perfectly honest in what he said: he does know a strategy that makes the expected value of binary search counterintuitively negative, and that strategy is (as he says explicitly) to avoid the first few numbers that you're going to guess. No further speculation about errors or deception on his part is needed.

(Also, since six bits will serve to identify 64 different numbers, it should be impossible to have more than 36 numbers that can't be identified that way.)

I'll update with boring manual data later.

---- update ----

That was wrong; using a naive guessing method, I found 37 values that require 7 guesses.

Well, rereading what he (was reported to have) said, I now think that probably was his intent, and he was just sloppy. At least, he can't have it both ways: Either he genuinely commits to a number at the outset, and uses the word "adversarial" to mean a very weak form of adversary (one that is defeated in expectation by TFA's mixed strategy), or he is using "adversarial" in the standard (strong) sense, in which case he must be lying about committing to a number, which is a shifty mind game as you say.

What you're saying sounds to me like "your answer doesn't need to be correct, it just needs to sound reasonable". What you're filtering on with this question is good bullshitters.

To me, the only reasonable to this question is "I don't know". I think even a mathematical genius like Terrence Tao would not be able to give you the answer to this on the spot. (Although I can also totally believe that he would instantly see this from some obscure theorem that only like 5 people on the planet know.)

And, indeed, what Microsoft really needed in the 80s was people who truly understood memory management in C, not gamblers left to hack their way into something that kind of worked sometimes. Microsoft's need to correct that hiring mistake later set them back significantly. Had they asked about the intricacies of C as it directly pertained to the job instead of unrelated trivia, they would be in a much stronger position now.

It doesn't matter that it was difficult to prove he was wrong. The issue is that it was impossible to prove he was right. And if anyone ever tried to bring that up to him, he never once heard them.

I believe an interviewer who is wrong and does not listen to you is a perfect example of the broken process. Especially given that he was an industry leader - in this interview he was providing a historical example of the process' merits - all while being entirely incorrect.

The question is whether Ballmers ego would allow him this flexibility if it's his own question.

Some people might be very emotionally attached to the questions they created, but not so much to those they've been given as an interviewer.

I've fared well pointing out issues with questions in the past and gotten the job. I'd try to be diplomatic about it though and not outright say they're wrong. Instead pointing out how with a classical binary search the expected value is negative, but there are strategies from game theory to deal with adversarial picks and here you could reach a positive expected value.

Kind of a "yes, and..." approach. You acknowledge their view, and then you add a new perspective. But don't say they're wrong.

Funny enough in situations where I suspect the interviewer was given the question it probably wouldn't have helped, not due to emotional attachment, but because the interviewer had a tenuous grasp of the topic themselves and couldn't stray from the script they were given.

I'd say it's impossible to answer this question conclusively within the time frame of an interview. That makes it, in my opinion, a bad interview question.

My answer to this question would be to show that I understand what it would take to answer this question correctly (you'd have to find a mixed strategy that has a positive expected value for every choice of number), I wouldn't be able to give a confident "yes" or "no" answer on the spot. I think that's the only correct answer.

In practice, I think this question is advantegeous for those who confidently blurt out an answer and then make up a heuristic argument for it. But a heuristic argument can be found for both "yes" and "no".

Presumably Balmer did ask this question. At least a few times. And yet he never heard of the correct answer, and believed the incorrect answer to be correct.

That tells you that if anyone did say "actually, you're wrong" he never listened to them.