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?
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