Re:Steve Ballmer's incorrect binary search interview question
by baking on Tuesday September 03, 2024 @03:22PM
(#41438224)
I think you did the math wrong. The expected value for the guesser is $0.20 if Ballmer chooses randomly. I think Balmer is saying that he can beat you if he chooses adversarially and you choose the expected initial guesses.
I agree that if you choose your first guess somewhat randomly in the 40-60 range (maybe not a uniform distribution though) Balmer would be forced to choose randomly and you would be back at a positive $0.20 EV. For example, you could flip 6 coins and add the number of heads, then flip another coin to decide whether you add or subtract the number of heads from 50 for your starting guess. But I think you would need to randomize your later guesses a bit also.
Re:Steve Ballmer's incorrect binary search interview question
by whimsicalism on Tuesday September 03, 2024 @08:45PM
(#41440755)
right but as posed the EV is positive if ballmer picks randomly so you have to go into consideration of the adversarial case
The post never answers the question "so what is the real expectation value", which is a more difficult question. But I think if the interviewee chooses a number randomly from 40-60 as the first guess and does a binary search from there, Ballmer can't really improve on choosing his initial number randomly.