Can you solve the basketball riddle? - Dan Katz
You’ve spent months creating a basketball-playing robot, the Dunk-O-Matic, and you’re excited to demonstrate it at the prestigious Sportecha Conference. Until you read an advertisement: “See the Dunk-O-Matic face human players and automatically adjust its skill to create a fair game for every opponent!”
That's not what you were told to create. You designed a robot that shoots baskets, sometimes successfully and sometimes not, taking turns with a human opponent. No one said anything about teaching it to adjust its performance. Maybe the CEO skimmed an article about AI and overpromised, setting you up for public embarrassment.
Luckily, you installed a feature where, given any probability q, you can adjust the robot to have that probability of success on each attempt. You swiftly gather information, and jackpot: your team has a dossier on all potential demo participants, including the probability each has of making baskets.
In each match, the human shoots first, then the robot, then the human again, and so on until someone makes the first successful basket and wins. You can remotely adjust the Dunk-O-Matic’s probability between opponents. What should that probability be for each opponent, so that the human has a 50% chance of winning each match?
Pause here to figure it out yourself. Answer in 3. Answer in 2. Answer in 1. You might guess that q should be equal to p. But that ignores the advantage of going first. Suppose p and q are both 100%. Even though the competitors are equally skilled, the first player always wins. So a deeper analysis is required.
One approach involves adding up every chance the human has to win, using geometric series. A geometric series is an infinite sum of numbers, where each number is the previous number multiplied by a common ratio. Two facts about geometric series are useful here. First, if the common ratio r of a geometric series has absolute value less than 1, the series has a finite total. And second, if the first number in the series is a, that total is: a divided by 1 minus r.
How does this help us calibrate our robot? Remember that the human has probability p of making a basket. Since they go first, they have probability p of winning on the first try. What’s the probability that they win on the second try? That attempt only happens if both players miss. The probability of a miss is 1 minus the probability of a success, so the miss probabilities are 1 minus p and 1 minus q.
The chance of both happening is the product of those values. So the probability of two failures and then a human success is p times (1 minus p) times (1 minus q). Winning on the third try requires another round of misses, so that chance is p multiplied by the double-miss probability twice.
If we add all the possible probabilities of a human win, the total is the sum of a geometric series. Since the first number in the series is p, and the ratio is this product that’s less than 1, the sum will be (p divided by 1) minus the ratio. We want this sum to be 1/2. Using some algebra to solve for q, we find that q should equal p divided by 1 minus p.
If p is greater than 50%, q would need to be bigger than 1, which can’t happen. In that case, a fair game is impossible, because the human has a better-than-50% chance of winning immediately. The robot's total probability is also the total of a geometric series.
How does this series compare to the human’s? To win, the robot needs some number of double misses, then a human failure followed by a robot success. If q equals p over 1 minus p, (1 minus p) times q is p. For our choice of q, not only do these series have the same sum, but they’re the same series!
We could bypass geometric series by starting with this reasoning. The robot’s chances of winning in the first round is (1 minus p) times q, and so if we want that chance to match the human’s first-round chance, we want it to equal p, making q: p over 1 minus p. More rounds may occur, but before each round, the competitors are tied, so everything effectively restarts.
If they have the same odds of winning in the first round, they also will in the second round, and so on. The demonstration goes perfectly, but while you didn't want to embarrass yourself, you also didn’t want to deceive the public. Taking the stage, you explain your company’s false promises and your hastily ad-libbed solution.
Thankfully, the ensuing bad press is directed at your employers, and it turns out the presentation volunteers own a more employee-friendly robotics company. After some tedious intellectual property litigation, you find yourself at a healthier workplace with a regular spot on a pickup basketball team.