This sort of misses the forest for the trees, although neat application.
Ballmer's argument is essentially about tail risk. Expected value is absolutely not a good way to make bets if you value survival, because you only get one shot. Same reason you wouldn't go all in every time you get a poker hand that's "expected" to win. Because you'll (very probably) be bankrupt in a few hands.
Sure the mean is +$0.07 or whatever, but the spread on that surely goes over the 0 line. So there may well be marginally more chance of winning than losing, on average, but you're only gonna get one outcome. So if the goal is to play to win, or else, then you probably shouldn't unless you like owing Ballmer 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.
If you're allowed to play the game a few trillion times or so, then by all means bleed him dry :P
> Ballmer's argument is essentially about tail risk
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.
> Expected value is absolutely not a good way to make bets if you value survival
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:
What idiot wouldn't put destruction of the world as '-infinity' of value?
Equating money with value is a simple trap as well. Who cares if you can win millions when a single loss wipes out all your savings? Since anything below a certain level of money leaves you trapped with no way out it could be argued that the value of being destitute is not 0 but -infinity which makes any risk of losing all money unacceptable. This is especially true in a world where people are willing to offer strange bets with arbitrarily high expected value as long as you have some money.
> What idiot wouldn't put destruction of the world as '-infinity' of value?
Literally anyone, you included. Every day, there is a chance that the roof collapse on you while you're sleeping; that's -Inf of value! Yet you don't put infinity resources into preventing that since you consider the probability low enough to not obsess over it.
No, I don't put infinity resources into it because that would make me die even earlier due to not having money or time to do what is necessary to stay alive.
The context can also be very important. For instance: In case A, you have $50, and are offered to bet them against a fair coin flip, if you guess right you win another $50, if you guess wrong you lose your $50; in this case the most rational choice would be to refuse to play the game. In case B, you have $50, and are offered to bet them against a fair coin flip, if you guess right you win another $50, if you guess wrong you lose your $50; in this case the most rational choice would be to agree to play this game.
The missing context is that in case A, you need in 10 minutes to repay $50 debt to the Sicilian mafia, or else they'll kill you to make an example for others, and you have no other assets or other ways to make money in this short time. In case B, the situation is the same, but you owe $100 instead of $50.
The St. Petersburg "paradox" is not a paradox if we consider any real-world implementation of it. The EV accumulates at the rate of $1 per flip. So, if we want to make the EV at least $1,000,000, we must find a counterparty that is willing to pay at least $2^1000000 (or at least 2^1000000 units of "utility" if we're trying to avoid the depreciating utility effect). That's plainly unrealistic. As soon as the counterparty has any fixed upper limit to its ability to pay (or provide utility), the EV becomes finite.
It's interesting that in this context the assumption of infinite growth is obviously unrealistic - but in the context of trad econ, infinite growth is considered a bedrock assumption.
Putting them together suggests it's flagrantly irrational to apply naive toy models to the real world. Even if they do have a nice mathy sheen.
Engineers (mostly) know this, but for some reason gamblers and economists (mostly) act as if they don't.
I don't mean specifically the St. Petersburg paradox but in the context of most things that economists analyze that have an infinite growth assumption.
> 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.
There are standard arguments (e.g. the Von Neumann–Morgenstern utility theorem) that an agent with rational preferences, with remarkably weak definitions of the word “rational”, must have an utility function and a subjective probability function such that their behaviour is always governed by the EV of that utility with respect to that probability.
Yeah but that utility function will not be a linear function of money so you can't say EV(u($$)) == u(EV($$)). This is the mathematical formulation that tells you that it is irrational to risk all your money to make an extra dollar even if u(EV($$)) is positive EV(u($$)) can be negative.
This is interesting to me in the context of a post[1] yesterday about teaching logical thinking to children. One of the top comments was about how, yes, teach logical thinking but also teach other types too. SBF and those who think with a heavy bias towards EV show an extreme weakness towards reality. Of course SBF himself is a perfect example of this. I won’t pretend to know if his math was always right but one of his defenses on trial was essentially “just run the simulations a few more times and we’ll get all the money back” which clearly shows a lack of understanding of reality.
I’m glad to now know there’s a common example of that weakness.
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.
> If the question is "would you play this game" the reasonable mathematical translation is "determine if the expected value is greater than zero".
Not really! And that may be the point of the question. It's not testing if you can pattern match to plausible CS concepts.
If you get one play, and the goal is to win, do you take the chance? The whole question is about the difference in likelihood in the limit (expected value, infinite plays) and what is a likely outcome _of one round_.
> It's not testing if you can pattern match to plausible CS concepts.
But thats a problem then, isn’t it?
Because if you abandon that framework there are many other possible frameworks to think in.
You say the question is about the difference in likelihood in the limit (expected value, infinite plays) and what is a likely outcome _of one round_. (Which may I say is just an other plausible CS concept you pattern matched.)
One might also say that you should play the game because even if you are playing like a chump and has absolutely the worst luck you are at max out of pocket of a 100 dollar. A real hustler can turn a personal meeting with Balmer into much more lucrative deal and earn back that hundred dollar million-fold that way.
Or you could say that the answer is no, because Balmer stinks and it would be ruinous to your personal reputation to be seen with him.
Or you could say “yes” because you know you don’t have cash at all. So even if he wins good luck trying to squeeze his reward out of you.
Or you could say “yes”, because while you distract Balmer with this inane game your associate will lift his valet and car keys.
Or you could say yes because what is the worst which can happen? You will spend a bit of a money, and have an awesome story to tell later.
Or you can answer no, because clearly a rich businessman does not have your best interest in his mind, so there must be some trap.
So this is what happens when you abandon the framework to answer the question as a plausible CS concept. You open the door to all these other alternative frameworks and more.
If it were about winning or losing that round, there wouldn't be so many different monetary values associated with each outcome. Instead, each outcome would be win, lose, or draw. Because there are monetary values, we have to decide if it's a good bet. If somebody offers me a chance to wager $1 on the outcome of a die roll where the payoff for choosing correctly is $10, I will do it, even though it's more likely that I will lose than win.
I don't think this is true. Most people will not be bankrupt after losing a dollar. If this is true then Steve failed badly at communicating this context.
To be honest, I think Steve just didn't grasp the mathematical deepness of the problem.
While it does seem that Ballmer doesn't have an understanding of the deepness of the problem, in his defence, he outscored BillG on the math SAT with a perfect score of 800, and graduated Harvard with a degree in applied mathematics.
Which makes me wonder if it's related to another 'simple' game theory problem that came up in Matt Levine's money stuff:
"They made me do the math on 1000 coin flips. EV(heads) (easy), standard deviation (slightly harder), then they offered me a +EV bet on the outcome. I said “let’s go.”
They said “Wrong. If we’re offering it to you, you shouldn’t take it.”
I said “We just did the math.”
They said “We have a guy on the floor of the Amex who can flip 55% heads.”"
I like that anecdote and the takeaway, especially with regards to trading: if someone's offering you what seems obviously a +EV trade, why are they offering it to you and what are you missing? Whether that was Ballmer's intended lesson is another matter..
Is the interview for an engineering position or for sales?
If you're hiring a software developer, I am going to assume all probabilities are about physical processes or data distributions or such, and there is no "if we're asking it means we have something up our sleeve". The data going to be sorted by merge sort is not going to have anything up its sleeve, or set any traps for me.
> Is the interview for an engineering position or for sales?
Either way. The coin-flip example and Ballmer's binary search game could apply with simple extensions to complicated processes like SLAs on cloud services.
> The data going to be sorted by merge sort is not going to have anything up its sleeve
That's a curious example, since one reason to use mergesort rather than quicksort is the latter's susceptibility to pessimal inputs.
You know that even smart mathematicians got tripped up by the Monty Hall problem, right?
> Even when given explanations, simulations, and formal mathematical proofs, many people still did not accept that switching is the best strategy.[5] Paul Erdős, one of the most prolific mathematicians in history, remained unconvinced until he was shown a computer simulation demonstrating Savant's predicted result.
I think you've misread. The bankruptcy was in an analogy to poker. The point is if you get _one round_ to play - essentially all or nothing - should you play? No.
> The point is if you get _one round_ to play - essentially all or nothing - should you play? No.
On the contrary, in general yes you should, because life as a whole will give you a variety of these sorts of risks. Steve Balmer's offer is just one episode in a lifelong series of risks offered you by the universe at large.
I actually think parkour community and practice teach and handle this very well. Same for free solo climbing.
Imagine you're in your bathroom, choose two tiles and step from A to B.
No problem. What if those tiles were all you had to stand on and you were 30 storeys up suddenly it's a whole different equation and your body instinctively knows it. In fact some of parkour training is learning to master your own fear and confidently execute things you know you can already do in the face of higher stakes.
If I offered you a dice roll and said guess the number, bet 1 dollar I'll pay you 12 on the right guess you'd bet 1 dollar but you wouldn't bet your life on it even though the EV was high. Even if the payout was 1 million you still might not take it (some might)
Edit Thinking about it more, my example is more about factoring in all the risks - a positive EV bet with a large downside risk is not a great one to take even if the risks are small which is where the picking up pennies in front of a steamroller analogy comes from
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.
Yes, precisely. Although that's more about bet sizing for optimal return in the long run, not quite about binary choice of whether or not to play. But conceptually bang on, I had it in mind
You could? There's no reason you couldn't do $50,000 with bets of $10,000. The point is you get 5 guesses before you lose. The bet sizes don't really matter.
They matter. I could play a game with negative expected value just for fun, if this negative expected value is not too negative. Or not for a fun, but to let Ballmer win to make him feel himself winner, to make him feel superior, hopefully it will help me to get what I want from him. To lose a game gracefully is a manipulation device, especially if the winner doesn't suspect, that you lose on purpose. And, the stories I heard about MS suggest that Gates, Ballmer and all those gray beards of MS were very competitive, so they are probably much more susceptible for this particular bait. $1 is a very small price for such a tactic. But $10,000... it depends on what I'm hoping to win, and on my detailed understanding of my further steps and probabilities of their success.
Life is more difficult than math abstractions of life. No one yet managed to mathematically describe any social situation to such level of details, so you could blindly believe your equations, like you do with physics.
The bet sizes here do really matter, because they are selected to ensure that there is no risk of ruin. Ballmer asks about playing the game once at a bet amount that anyone doing the job interview can cover.
I don't view the original problem this way, but let's think about it!
> 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.
hey, thanks for the blog post and your reply! I think I follow - a generalization of a coin-flip type game. I agree that if you have more starting money, you would never lose. From the binary search idea, even if chosen adversarially, the worst case is still log2(100) ~= 6.6. So if you get 1,000 guesses or just any number of guesses >= 7 you literally can't lose. Then you should definitely play.
Setting the limit at 5 brings you to the interesting point of there being a good mix of win/loss outcomes. 4 would be too few guesses and you'd very likely lose, and 7+ you'd definitely win. So the question is only interesting _because_ the limit is chosen so that the spread puts your odds on both sides of the 0 line. Otherwise it'd be clear cut.
The standard deviation being ~$1 is interesting. To me that suggests that with a mean of $0.07 and a deviation of +/- $1, it's essentially 50/50 odds. There's technically a slight edge in your favor, probably 53/47, but barely. So given a game with essentially no edge, would you play? Framing it that way - deciding to what degree the game is winnable - it's essentially not. You should not particularly expect to win, no matter your strategy.
I think part of the trick with the Ballmer question as well is the question is not necessarily about 'can you find an optimal strategy?' - it's 'do you play the game or not?'. The paths chosen within the round don't ultimately matter to that question. It's only intermediately necessary to model the intra-round decision paths in order to get to the overall win/loss distribution for a single round.
If you do end up getting the time, do make another blog post!
Here's another way to look at it. With a naive binary search strategy, which is an optimal algorithm for search for a sorted static array, we have:
Step # | % of reachable numbers in [1,100]
1 | 1% = 2^0
2 | 3% = 2^1 + 2^0
3 | 7% = 2^2 + 2^1 + 2^0
4 | 15% = 2^3 + ...
5 | 31% = 2^4 + ...
6 | 63% = 2^5 + ...
7 | 100% <-- 2^7 > 100
So out of all possible single-trial outcomes, only 31% of outcomes guess the number in <= 5 steps. In other words, in 1 trial you would expect a 69% chance of a non-positive outcome.
So an EV of +$0.2 or +$0.07 alone does not match the actual odds of winning in 1 trial. EV is most predictive in the infinite limit, and least predictive in a single trial - which this is. First off, $0.2 isn't even a possible outcome so there's a good reminder that the mean value does not always occur in the dataset.
This is also pretty straightforward from the classical interview-y 'Big O' perspective. If you translate the question to the natural CS-worded equivalent, something like "can you search a sorted array of length 100 to find an arbitrary value in 5 steps or less?", one readily sees that O(log2(n)) -> log2(100) = 6.6 > 5, so you definitely can't guarantee it. If we put odds on it as above, we can see that the odds are also not in your favor.
Now, if you want to look at it as saying after 5 steps you've removed ~96% of the search space, that's cool and all that you've reduced the candidates to only 3-4 remaining numbers, but those aren't the odds of winning. We know that 7 guesses is enough to guarantee finding the number, so after 5 guesses we ought to be 'close'. But the game is not horseshoes, so the fact that we're close is not relevant
> Same reason you wouldn't go all in every time you get a poker hand that's "expected" to win. Because you'll (very probably) be bankrupt in a few hands.
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.
People are really zeroing in on the word 'bankrupt' here. The point was if you used that strategy, all in 100% of the time for positive EV, you will _probably_ go bankrupt even though the n=infinity limit of that strategy is positive.
The whole poker thing was merely an analogy in the first place.
Calling an all-in and going all-in are two totally different things, unless the all-in (that you'd be calling) is for an amount greater than you have. Otherwise, it's just "bet a lot, but you can keep trying if you lose". Going all in, on the other hand, is "bet it all, and if you lose you're done". The risk on the later is much greater. Any time there is no chance for recovery on failure, your risk analysis changes dramatically.
But in a cash game, if you're properly bankrolled (a common number people recommend is to have at least 40 buy-ins worth of cash set aside for the stakes you're playing), the one buy-in you lose if you lose an all-in is relatively small and you can just buy in again and keep playing. Going back to what OP said, if you shove every time you get aces you will profit over time as long as you have a properly managed bankroll, it's just not the most profitable way to play aces in most situations. It's different in tournaments because when you're late enough into a tournament, losing your stack actually does mean losing everything since you can't re-buy
What you are getting at is that for a single person, the chance of going bankrupt is high but for a population ensemble, the average wealth increases.
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.
It's kind of a given that you can't use the proposed mixed strategy for a single game, because it expects you to draw one of the patterns at the start of the game.
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.)
agree about the EV stuff. it only makes sense over many draws and the problem states that he is thinking of "a number", that sounds like one game.
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?
That is an interesting question. I suppose it's equivalent to the 'worst case' performance for binary search, which would be a relevant topic. Finding the optimal strategy in the case where the opponent _may_ be adversarial could be interesting. I don't imagine the odds improve compared to the base situation, but not sure
what if you, say, decided to make the bet that your opponent is adversarial and just did binary search, but restricted high, low and mid to snap to the nearest adversarial numbers when adjusting them?
When Ballmer said 'adversarial', I considered this strategy: he's not actually required to pick a fixed number at the start at all. He can simply give the answer to each guess which leaves the largest number of possible numbers remaining, guaranteeing a loss regardless of strategy.
Right! I'm not sure if that's actually what he had in mind, but if he did, it's funny because it makes all this mathematical analysis completely pointless.
The OP has a complex randomized strategy that guarantees to average at least $0.07 against any adversary; meanwhile, just by delaying his "pick" and stringing you along, Ballmer makes you take seven guesses and owe him a dollar each time.
If you were expecting to win $0.07 on average, how many rounds would you play before you realise you're being scammed?
The OP's article is interesting, but it assumes a very weak notion of "adversarial", in which Ballmer still commits to some initial choice.
Interestingly it's actually possible for a player to know this is the case if Ballmer uses a commitment scheme [1]. For example, at the start of the game Ballmer could generate 500 random bits, append his chosen number in the range 1-100 to this, hash the result and then send you that hash: At the conclusion of the game, he sends you the 500 random bits, and you can check that concatenating his chosen number (now revealed) to those bits and hashing the result produces the hash he originally sent. (If Ballmer lies and changes his number, he would need to somehow come up with 500 bits that when concatenated with this different number still produce the original hash. This is hard.)
His wording of the rules implies he chooses a number and sticks with it. He "has a number in mind". Of course some interviewers like to play mind games and twist things up to make themselves feel smart but I don't think that's his intent here.
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.
This is how it is done in the analysis of competitive ratios of online algorithms. The adversary can change its mind on a whim, it merely has to commit to the decisions it has already made in the past.
I mean, who know what he’s thinking, but based on the game description that strategy isn’t “adversarial”, it’s lying. Maybe the lesson is “don’t play games for money with people who will cheat”, but it would be a boring one.
Edit: Oops, nope, this comment is wrong, ty fgna for pointing that out!
I feel like there's an even simpler proof that you can beat adversarial-ballmer, with exactly the same expected positive outcome as binary search vs random ballmer.
I call my algorithm "randomly offset binary search". It goes like this:
1. Pick a random number between 0-100, call this 'offset'
2. Perform the binary search algorithm, except at each step add 'offset' to the value and mod by 100.
That's it. Now, even if Ballmer knows you're using this strategy, he can't make it perform any worse by selecting any specific number. Therefore your expected outcome is still $0.20 per game, beating the strategy proposed in this blog post.
Unfortunately the numbers are not circular :( By offsetting the initial number, the binary search does not work optimally right? Imagine the number is below 50, and you start by guessing 60, now you have to search for 30 numbers instead of 25, and thus the binary search is not optimal.
reply
Neat. A nice way to see this is to imagine that the numbers 1-100 are arranged around a clockface; you randomly spin the clock before doing a conventional binary search starting from the top.
Stack ranking existed at MSFT before Ballmer became CEO, i.e., when billg was CEO.
It was a practice that Jack Welch brought into the corporate world and Microsoft was just guilty of following what were thought to be best practices at the time.
Source: worked at Microsoft before Windows Mobile was a thing.
As an aside, Windows Phone was my favorite phone OS and Ballmer seemed like the one who actually cared about it a lot.
Tangent:
I love that phrase. Anytime I hear someone make that statement I think about the 9,000 things that have been considered "best practice" until we actually understood that they weren't even "good practice". It gets thrown around as if it's been studied and confirmed when in reality it means "a bunch of people are doing it"
Is this a perfect example of broken modern tech interviews?
Balmer's question seems fair for the complexity of the answer he was expecting.
As the interviewee you would presumably provide the (mathematically) wrong answer, but you'd show your thinking along the way, including a small demonstration of CS principles.
Keep in mind that Balmer had a long career, so if he ever asked this question, it was probably back in the 80s when no one expected you to come up with the complex solution outlined in the post.
If you did outline the correct answer, that would be amazing, and you'd be an instant hire. But the question doesn't fundamentally seem broken to me because either answer (taking the bet or not) needs to be well justified.
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.)
Which is exactly the same as “no” in this situation. If you were capable of proving the opposite I assume he would have been willing to hear you out.
> not be able to give you the answer to this on the spot
Realizing the most obvious strategy would be suboptimal if the game is adversarial is the first step of the correct answer though. If you didn’t know what to do next obviously the correct answer is “no, because I don’t know”.
Someone who is trying to absolve himself from making any decision ls is presumably not the sort of a person they were looking for.
Also would Balmer have been hiring for engineers to begin with?
No, it's about understanding what an interview is for. They're not trying to get the answer. They're trying to find out what you know, how you think and how you communicate.
Do you spot that it's different with one Vs many plays? Do you spot the binary search? Do you spot that an adversarial opponent can push things? Can you clearly communicate these?
If you just say "I don't know" and that's it you are showing you don't know how to communicate important information and miss soft skills about understanding the context of an interview.
If you say "I don't know" and talk through your thoughts then great. The point is talking things through, even if you have gotten the wrong answer.
Maybe you'd be able to say "and here's how I'd code a simulation to check"
That seems reasonable, and in that context I would think it's actually a good interview question.
But it seems that Steve Ballmer used this question as if it has a single right answer, and that answer is "no". Unless it's more about the question "do you want to play this game, right here, right now?", then it becomes more about heuristics and quick reasoning.
In fairness, if someone proposes a complex and contrived game which cannot be easily analysed but is potentially adversarial... you shouldn't play them.
Seems so. The broken tech interview idea stems from the idea that interview questions that do not pertain to the job will lead to hiring the wrong people.
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.
Thanks for playing along. This is a perfect example of why pointless trivia does well in an interview. It reveals the psuedo-intellectuals who will overanalyze the situation in an effort to try and sound intelligent. Exactly who you want to steer clear of.
The candidate you actually want to hire will respond with something to effect of "That's dumb. Let's instead talk about X, which will be a far more appealing topic to both of us."
Well.. most people generally don’t like working with annoying, self-entitled know-it-alls. So I guess the question serves its purpose if it filters such people out.
> effort to try and sound intelligent. Exactly who you want to steer clear of.
I wouldn’t be reading your comments if I wanted to stay clear of stuff like that, would I?
I think you're missing my point. The problem isn't the question - it's the fact that Balmer was objectively wrong about the answer - and he never changed that determination after having conversations about it however many times. ("I asked this question all the time.")
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.
I'd love to address your point, but unless you further articulate your position I won't be able. I see nothing in my statements that isn't directly said or implied from the linked video.
Well to be fair Steve Ballmer is a terrible leader and if he had to take the tech interviews he wouldn't have passed and Microsoft wouldn't have stagnated for 10 years, before Satya Nadella took over and brought the company back on its feet.
He’s probably a decent leader just not a very good CEO for a company that needs to develop new products and enter new markets to continue growing rather than to try and squeeze every remaining penny from their current customers.
is it? If I was forced to ask this question as an interviewer, and the candidate said, "actually, you're wrong, here's why" that's a very good signal. Do most people not do this?
(typically there's discussion with all the interviewers and it isn't just "did the candidate get the question right or not). I personally think a lot of big tech interview questions are dumb but I think the process isn't as broken as I thought, seeing it from both sides.
>If I was forced to ask this question as an interviewer, and the candidate said, "actually, you're wrong, here's why" that's a very good signal. Do most people not do this?
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.
I don't work in the tech industry but I always assumed these questions were designed for you to demonstrate your problem-solving skills, regardless if you get the answer correct or not.
In this case, it would just be showing that you can reason about binary search and showing that the mean profit is 0.20 dollars
As long as it's used to figure out if the two parties would enjoy working with each other, I guess it's fine. But yes, increasingly often this turns into a quiz or worse.
I don't think the average CS curriculum is going to cover advanced game theory. And you certainly aren't going to doing most linear programming on the spot in a interview.
We let our computers play. My computer's AI vs Ballmer's AI. One trillion six hundred eighty-three billion thirty-six million fifty-one thousand nine hundred eighty-four computer games in 30 seconds.
This is a very nice book covering mixed strategy in game theory.
A very nice motivating example from the book:
"There are two cards, an ace and a deuce. Player A draws either of the two at random; B does not see which card is drawn. If A has drawn the ace, he says "I've got the ace" and demands a dollar from his opponent. If A has drawn the deuce, then he may either (A1) say "I've got the ace" and demand a dollar from his opponent or (A2) confess that he has got the deuce and pay his opponent a dollar.
The opponent, if he is paid the dollar voluntarily, can only accept it. If, however, a dollar is demanded from him, then he may either (B1) believe that player A has got the ace and give him the dollar or (B2) demand a check so as to see whether A's statement is true or not. If it is found that A does have the ace, B must pay A two dollars. If, however, it is found that A is bluffing B and has the deuce, player A pays B two dollars.
Analyze the game and find the optimal strategy for each player and the expected payoff."
Nice! I tried to solve this the other day too, but came from the other angle--trying to find a probability vector for Ballmer that always won (finding the best response tree is n^3 complexity best I could find). I'm somewhat surprised since I figured for sure Ballmer had a big edge by picking numbers near the endpoints, making the player pay a large cost to check them.
People are unable to think randomly. They'll avoid the obvious "not random" numbers 2 and 99, for example. I read somewhere that most people, asked to pick a number between 0 and 10, will pick 7. And the next digit would probably be odd, and not 5, because 5 is not random. That leaves you with 71, 73, 77 and 79. 77 is not random, so 71, 73 or 79. I'd pick 73 as my first guess.
I'd say those were good odds!
(That's why when you're picking a "random" number, it's best to use an actual dice.)
This is how you win at hammer-paper-scissors, too.
Ballmer could also change the number he's thinking of as you make guesses, so part of the game would be guessing what he's thinking.
I guess this is part of the clarifications one normally asks when in an interview setting, but he has specified numbers and not integers. One could choose (pi*2)/2 and you will owe a lot of money.
I find it interesting: it is definitely symmetrical, but I did not expect that in the final result 1/98 could be more important as a starting value, while 2-17/82-97 are not used at all.
This really depends on the pure strategies that you choose.
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.
I did a very similar exercise after reading the original post.
You can get the EV a lot closer to the optimal +0.2 (Although I was unable to prove how close) by dropping the requirement "do not increase worst-case complexity for the binary search" as this is lost with initial guesses outside 36-64 anyway. Deviating at a higher depth makes punishing specific guesses in the tails a lot cheaper, only giving up 1-2 cents of EV.
It would only make sense if Ballmer writes the number he is originally guessing on a piece of paper and fold it before game begins. And win/loss is checked with what is written on the paper.
Otherwise it is a hidden mutable information game where Ballmer dynamically changes higher/lower for maximum tree depth and always make you lose.
I wonder whether the search algorithm would need (and can?) to be adjusted to respond to the increased probability of playing numbers that are hard to find with standard binary search.
I'm no mathematician, but I think that if you know something about the probability distribution before searching, then you can be more efficient than blindly using binary search. And if you assume Ballmer is out to get you (i.e. the distribution is not random) then you can use that information to improve the search speed.
If a second party can submit adversarial values into a system, potentially causing a denial of service in a binary search (where comparisons are computationally expensive and data is unevenly distributed), there is a much simpler solution: avoid using sorted collections and binary search. Instead, use hashmaps. To address similar HashDoS attacks, many implementations (in Python, Rust, Java, etc.) use a randomized hash function, which vaguely resembles the idea of randomizing starting value for binary search.
The point is that Ballmer is an adversary, and may choose the worst cases for binary search. As I understood, the algorithm in TFA holds against any choice.
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.
Preliminary analysis: one in every three numbers has this undesirable property; the edges mess this up but shouldn't be able to add more than two extra undesirables; it should be impossible to have more than ceil(33.333) + 2 = 36 undesirables.
(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.
After watching the interview I can't imagine why anyone would spend time trying to solve for this or entertain this as a valid test of anything. In 7 guesses he TWICE amended if she was high/low after hearing her guess.
He also doesn't say he wants to play in this reality where the rules of maths hold. That his one and your one mean the same thing. That your accent doesn't have to match his. That you haven't got to be holding a certain pose when you say it. There are always implied rules, and Ballmer's implied rules are he'll use a whole number, not change his number and be fair. You could probably spend now until the end of time adding stipulations and he'd still be able to cheat.
I'd recommend never learning about philosophy as you'll disappear into nihilsm.
And lottery wins aren't taxable every where on the planet (e.g. the UK), so you made the same "mistake" as the author too!
Steve Ballmer's incorrect binary search interview question - https://news.ycombinator.com/item?id=41434637 - Sept 2024 (240 comments)