Recently, my two youngest nephews have started playing basketball. Several weeks ago, I taught them– along with my wife– how to play Knockout, a game I remember playing at the various basketball camps I attended as a kid. The rules are pretty simple:
The players line up behind the free throw line, with the first two players each having a basketball. (At camp was often 80 or so, with the line stretching to the other end of the court, but in this case .) Each player in turn shoots initially from the free throw line. If he makes it, he passes the ball to the next player and goes to the end of the line. If he misses, he must recover the ball and shoot again– not necessarily from the free throw line– until he makes it. If a player ever fails to make a shot before the player behind him makes his shot, he is “knocked out” of the game. The last player remaining wins.
How fair is this game? That is, if we assume that all players are equally skilled, how important is your choice of starting position in line? Intuitively, it seems like it would be better to start nearer the end of the line, with the extent of advantage depending on the assumed difficulty of all shots taken. As usual, my intuition turned out to be wrong (or at least not entirely correct), which is why I think this is an interesting problem.
Let’s model the game by assuming that each player during his turn makes the initial free throw with probability , and (after a miss) makes any following shot with probability . (My guess at reasonable values for are somewhere between 0.4 and 0.6, with somewhere between 0.7 and 0.9.) Also, let’s assume that players always alternate shots, so that a player never gets two consecutive opportunities to make his shot without the other player shooting.
To make this more precise, the following figure shows the transitions between the five basic game states, with each node representing a shooting situation for the ordered subset of numbered players currently remaining in the game, with the player to shoot indicated in red.
(For reference, a simplified two-player variant of this game was discussed earlier this year at Mind Your Decisions. However, that game is still not quite Knockout as discussed here, even restricting to players and . For example, if players 1 and 2 both miss, then player 1 makes his following shot, he does not immediately win the game.)
Knockout is relatively easy to simulate, but is a bit more challenging to approach analytically. Like the dice game Pig discussed earlier this year, the problem is that game states can repeat, so a straightforward recursive or dynamic programming solution won’t work.
So, as usual, to present the problem as a puzzle: in the game of Knockout with just players, as a function of and , what is the probability that the first player wins?
(Hint: I chose not just because it’s the simplest starting point, but because I think the answer is particularly interesting in that case: the probability does not depend on !)