Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The expected value of the game is positive regardless of Ballmer’s strategy

gukov.dev

Post reply on HN
Print view View original

161–166 of 166 posts

Re: The expected value of the game is positive regardless of Ballmer’s strategy

#161

Post by vjo »

gukoff wrote: post #134
vjo wrote: post #106

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…

Interesting! What about the worst case? And which kinds of strategies did you pick?

Using random strategies with small sub-optimal deviations, I get to about $0.189

Ref. https://pastebin.com/YcRhGpV6

Re: The expected value of the game is positive regardless of Ballmer’s strategy

#162

Post by lern_too_spel »

lern_too_spel wrote: post #156
TheOtherHobbes wrote: post #122

Earlier quoted context omitted.

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…

When you're this far away from saturation, infinite growth is a good approximation.

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.

Re: The expected value of the game is positive regardless of Ballmer’s strategy

#163

Post by vismit2000 »

Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...

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."

Re: The expected value of the game is positive regardless of Ballmer’s strategy

#164

Post by ywvcbk »

randomdata wrote: post #70
ywvcbk wrote: post #66

Earlier quoted context omitted.

> Had they asked about the intricacies of C Presumably it wasn’t Ballmer who was asking questions like that? If he was running the “business”, sales etc. part of the company. All of the things you listed would have been less than worthless if they weren’t able to convince anyone to buy their products.

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…

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?

Re: The expected value of the game is positive regardless of Ballmer’s strategy

#165

Post by qarl »

lupire wrote: post #143
qarl wrote: post #125

Earlier quoted context omitted.

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 b…

You are claiming things that are absent from and contradicted by the interview.

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.

Re: The expected value of the game is positive regardless of Ballmer’s strategy

#166

Post by nighthawk454 »

nighthawk454 wrote: post #159
gukoff wrote: post #131

Earlier quoted context omitted.

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 ot…

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…

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% 100

So out of all possible single-trial outcomes, only 31% of outcomes guess the number in 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

Post reply on HN