史蒂夫鲍尔默错误的二分搜索面试问题

史蒂夫·鲍尔默 (Steve Ballmer) 提出了一个游戏，他选择一个 1 到 100 之间的随机数字。他根据正确识别他选择的数字所需的猜测次数提供各种奖励。玩家首先进行一次猜测，如果猜对，将获得 5 美元。每次错误猜测后，玩家必须根据猜测的次数向史蒂夫支付逐渐减少的金额。具体来说，直到第六次猜测，玩家每次猜测都会损失 4 美元，第七次猜测为 3 美元，第八次猜测为 2 美元，并且对于任何后续猜测都会损失 1 美元的初始赌注。需要澄清的是，在最佳游戏过程中，潜在损失总额超过了游戏过程中的潜在收益。史蒂夫声称，由于这些成本，游戏的预期价值为负，但他提出了一个有缺陷的论点。通过采用二分搜索算法，玩家可以最大限度地减少损失。二分搜索涉及将每一步的可能性范围减半，直到确定正确的选择。使用递归二分搜索函数的 Python 脚本演示了游戏的预期价值约为 0.20 美元，而不是负数。因此，尽管史蒂夫的说法与此相反，但游戏的预期价值仍然对玩家稍微有利。史蒂夫似乎并不打算让六次尝试没有奖励，因为修改规则以包括连续六次尝试的 0 美元罚款会导致预期价值进一步降低。

Steve Ballmer proposes a game where he picks a random number between 1 and 100. He offers various rewards based on how many guesses are needed to correctly identify his chosen number. Players start by making a single guess and receive $5 if they guess correctly. After each incorrect guess, the player must pay Steve a decreasing amount based on the number of guesses made. Specifically, players lose $4 for every guess up to the sixth guess, $3 for the seventh guess, $2 for the eighth, and lose their initial stake of $1 for any subsequent guesses. To clarify, the total potential losses exceed the potential gains over the course of the game when playing optimally. Steve claims that the expected value of the game is negative due to these costs but provides a flawed argument. By employing a binary search algorithm, a player can minimize their losses. Binary search involves halving the range of possibilities at each step until the correct choice is identified. A python script using a recursive binary search function demonstrates the expected value of the game being approximately $0.20, rather than negative. Therefore, the expected value of the game remains slightly favorable to the player despite Steve's assertions to the contrary. It appears Steve may not have intended for there to be no reward for six attempts, since revising the rules to include a $0 penalty for six consecutive attempts results in a further diminished expected value.

Here's what he says: "I'm thinking of a number between 1 and 100. You can guess, after each guess I'll tell you whether high or low. You get it the first guess I'll give you five bucks. Four bucks, three, two, one, zero, you pay me a buck, you pay me two, you pay me three".

The question is "Should you accept to play this game?". In the interview, Ballmer states that the answer is "No" for two reasons: firstly, because he can pick numbers that'll be the most difficult for you to determine, secondly because the expected value of the game (assuming Ballmer chooses randomly) is negative: you end up paying Ballmer.

He's right on the first count. If you follow a binary search strategy (which will be optimal if he's choosing randomly) and he chooses one of 2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 85, 87, 90, 93, 96, 98 or 100 then you owe him $1. For all other numbers you get $0 (if he chose 1, 4, 7, 10, 13, 16, 19, 23, 26, 29, 32, 35, 38, 41, 44, 48, 51, 54, 57, 60, 63, 66, 69, 73, 76, 79, 82, 86, 89, 92, 95 or 99) or a positive outcome (some of his money!).

In the video above Ballmer chooses 59 which a binary search strategy would have found in 5 steps resulting in the interviewer, Emily Chang, winning $1. She was actually pretty close to doing that. The binary search steps would be 50, 75, 62, 56, 59 and she guessed 50, 75, 60, 55, 57, 58, 59.

On the second count (Baller implies the expected value is negative), if he's choosing randomly, then he's wrong. The expected value is $0.20 (calculated discretely using the code below). The code calculates the number of guesses for each value and an overall expected value assuming Ballmer chooses randomly.

use strict;
use warnings;

my @v = (0, 5, 4, 3, 2, 1, 0, -1, -2);

my $ev = 0;
my $ec = 0;

my @range = (1..100);

foreach my $r (@range) {
my $l = $range[0];
my $h = $range[$#range];

my $s = 0;
while (1) {
$s += 1;
my $g = int(($l + $h)/2);

if ($r == $g) {
print "$r found in $s steps (" . dollar($v[$s]) . ")\n";
$ev += $v[$s];
$ec += 1;
last;
}

if ($g < $r) {
$l = $g + 1;
next;
}

if ($g > $r) {
$h = $g - 1;
next;
}
}
}

$ev /= $ec;
print "Game expected value is " . dollar($ev) . "\n";

sub dollar {

my ($d) = @_;

my $f = (int($d) == $d)?'%d':'%.2f';
return sprintf("%s\$$f", ($d<0)?'-':'', abs($d));
}

This chart shows the expected winnings (or loss) depending on the number Ballmer chooses. The shape of the binary search can be seen in the chart itself.

A different way to think about the expected value and binary search is as follows:

1. On the first guess you choose 50 and win $5 with a probability of 1/100

2. On the second guess you choose 25 or 75 and win $4 with a probability of 2/100

3. On the third guess you choose 12, 37, 62 or 88 and win $3 with a probability of 4/100

4. On the fourth guess you choose 6, 18, 31, 43, 56, 68, 81 or 94 and win $2 with a probability of 8/100

5. And so on.

The gives the expected value as 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100 (note the last term is the remaining possible numbers having reached the end of the binary search). That's 0.2.

Why was Ballmer wrong?

One possibility is that he didn't mean to have the $0 for 6 guesses. If he'd said "I'm thinking of a number between 1 and 100. You can guess, after each guess I'll tell you whether high or low. You get it the first guess I'll give you five bucks. Four bucks, three, two, one, you pay me a buck, you pay me two, you pay me three" then the expected value is -$0.49.

史蒂夫鲍尔默错误的二分搜索面试问题 Steve Ballmer's incorrect binary search interview question