Probabilities in Knockout: solution

This is a very brief follow-up to the previous post about the basketball game Knockout, and the advantage of starting the game at a particular position in line. Specifically, if we start the game with $n$ equally skilled players, each of whom makes their initial shot (usually from the free throw line) with some fixed probability $p$ , and any follow-on rebound shots with probability $q$ , then what is the probability of winning the game as a function of starting position?

Using the state transition diagram from last time, let $P_{n,k,s}$ be the probability that, with $n$ players remaining in the game currently in state $s \in \left\{1,2,3,4,5\right\}$ , the player in position $k$ (starting from zero) wins. Then we can translate the state diagram into a corresponding system of equations using the following Mathematica code:

numPlayers = 2;
eq = {
    P[1, 0, 1] == 1,
    Table[
     {
      P[n, k, 1] == p P[n, Mod[k - 1, n], 1] + (1 - p) P[n, k, 2],
      P[n, k, 2] == p If[k == 0, 0,
                      P[n - 1, Mod[k - 2, n - 1], 1]] + (1 - p) P[n, k, 3],
      P[n, k, 3] == q P[n, Mod[k - 1, n], 4] + (1 - q) P[n, k, 5],
      P[n, k, 4] == q P[n, Mod[k - 1, n], 1] + (1 - q) P[n, k, 2],
      P[n, k, 5] == q If[k == 0, 0,
                      P[n - 1, Mod[k - 2, n - 1], 1]] + (1 - q) P[n, k, 3]
      },
     {n, 2, numPlayers},
     {k, 0, n - 1}
     ]
    } // Flatten;

Then we can determine the probabilities of winning for each position in line by solving for $P_{n,k,1}$ for $k=\left\{0,1,...,n-1\right\}$ .

Table[
    P[numPlayers, k, 1],
    {k, 0, numPlayers - 1}
] /. Solve[eq, Cases[eq, _P, {2}]] // First;

Interestingly, in the game with just $n=2$ players, the probability of the first player winning is $1/(3-p)$ , independent of $q$ , as shown in the following figure. The second player’s advantage is minimized when the initial shot is easier.

Probability of first player (red) and second player (blue) winning in two-player Knockout, vs. probability of making the initial shot from the free throw line.

With more than two players, the probabilities of winning depend on both $p$ and $q$ in a more complicated way. If we make the reasonable assumption that rebounds and put-backs are about the same difficulty, say $q=0.8$ , no matter from where the initial shot is taken, then we can show similar results for $n=3$ and $n=4$ , etc.

Probabilities of winning with 3 players, vs. p (with q=0.8).

Probabilities of winning with 4 players, vs. p (with q=0.8).

As mentioned last time, my intuition suggested that it’s always better to start farther back in line, but the above figures show that’s not necessarily the case, at least if the initial shot is sufficiently difficult– for example, if players start by shooting from the three-point line instead of the free throw line.

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Probabilities in Knockout: solution

Chris Wellons says:

November 9, 2014 at 4:43 am

Interesting results. It’s another case of simple rules leading to complex shapes. I wish your plots had sliders attached to them so that I could interactively watch how the curves change as q (continunously) and n (discretely) are changed.

- possiblywrong says:
  
  November 9, 2014 at 4:28 pm
  
  Yeah, once again I can see more from my sandbox than I can show with this WordPress environment– it would be nice to be able to embed JavaScript, for example.
  
  Another way to see more of the “landscape” as p and q vary is to identify those regions where the *order statistics* of the relative advantage among the players doesn’t change. These plots show what I mean; in each one, the blue region, for example, indicates the values of (p,q) where the “intuitive” behavior holds, i.e., probability of winning increases the farther back in line you start. The other colors show regions where it might be better to *not* start at the back of the line. (I included an extra plot for 5 players since that’s the first time where things get more interesting.)