3 ms·

The punch line of this post is that if Ballmer defines the payouts so that the interviewee receives floor(lg N) dollars for hitting in one guess, then Ballmer's

The punch line of this post is that if Ballmer defines the payouts so that the interviewee receives floor(lg N) dollars for hitting in one guess, then Ballmer's expected payout decreases as N increases — with a sharp step upward each time N reaches a power of two. This is... exactly how the floor function is defined to behave! The graphs would be much more enlightening if the artificial step function were removed. Instead of subtracting from floor(lg N), subtract from plain old lg N — or even don't subtract from anything at all, and just graph the number of guesses required.

possiblywrong 2y ago
Author of the linked article here; you're right that just the expected number of guesses is roughly monotonic. However, that expected number of guesses (along with Ballmer's expected payout) increases, not decreases, as N increases, with a sharp step downward, not upward, each time N reaches a power of two. The intent here is to reasonably compare hypothetical job interview questions for different N. If N=100, then Ballmer offers 6 dollars in exchange for one dollar per guess, and the linked Gukov article shows that Ballmer's expected return is negative. What if he instead challenged an interview candidate with N=127? What about N=255, or N=511, etc.? He presumably wouldn't continue to offer only 6 dollars to play in these cases, but also presumably a similarly nice round number of dollars... and now the question/conjecture is interesting: from the updated graph, it looks like Ballmer's expected return decreases as N=2^k-1 increases, but does it always remain positive? Or is there some sufficiently large key space beyond which even an optimal guesser can't ever win on average? To me, this question seems easier to ask when the expected return is presented in this way. That is, does each sawtooth interval always span zero expected return?

possiblywrong 2y ago

Author of the linked article here; you're right that just the expected number of guesses is roughly monotonic. However, that expected number of guesses (along with Ballmer's expected payout) increases, not decreases, as N increases, with a sharp step downward, not upward, each time N reaches a power of two. The intent here is to reasonably compare hypothetical job interview questions for different N. If N=100, then Ballmer offers 6 dollars in exchange for one dollar per guess, and the linked Gukov article shows that Ballmer's expected return is negative. What if he instead challenged an interview candidate with N=127? What about N=255, or N=511, etc.? He presumably wouldn't continue to offer only 6 dollars to play in these cases, but also presumably a similarly nice round number of dollars... and now the question/conjecture is interesting: from the updated graph, it looks like Ballmer's expected return decreases as N=2^k-1 increases, but does it always remain positive? Or is there some sufficiently large key space beyond which even an optimal guesser can't ever win on average? To me, this question seems easier to ask when the expected return is presented in this way. That is, does each sawtooth interval always span zero expected return?