This Riddler Classic puzzle explores a randomized team drafting strategy designed to prevent teams from throwing games.

You are one of 30 team owners in a professional sports league. In the past, your league set the order for its annual draft using the teams’ records from the previous season — the team with the worst record got the first draft pick, the team with the second-worst record got the next pick, and so on. However, due to concerns about teams intentionally losing games to improve their picks, the league adopts a modified system. This year, each team tosses a coin. All the teams that call their coin toss correctly go into Group A, and the teams that lost the toss go into Group B. All the Group A teams pick before all the Group B teams; within each group, picks are ordered in the traditional way, from worst record to best. If your team would have picked 10th in the old system, what is your expected draft position under the new system?

*Extra credit:* Suppose each team is randomly assigned to one of T groups where all the teams in Group 1 pick, then all the teams in Group 2, and so on. (The coin-flipping scenario above is the case where T = 2.) What is the expected draft position of the team with the Nth-best record?

Here is my solution to the general case:

[Show Solution]

Number all the teams according to their original seeding order and suppose there are $K$ teams in total. Label the groups $1,2,\dots,T$, where Group 1 gets picked first, Group 2 second, and so on.

Let’s calculate team $N$’s expected draft position given that it was placed in Group $i$. For each other team $k$, define the random variable:

\[

X_k = \begin{cases}

1 & \text{if team }k\text{ finishes ahead of team }N\\

0 & \text{if team }k\text{ finishes behind team }N

\end{cases}

\]The final draft position of team $N$ is therefore $1 + \sum_{k\ne N} X_k$, where we sum over $k=1,2,\dots,K$ but exclude team $N$. The expected value of this sum is the sum of expected values (linearity of expectation), so we can focus our attention on a particular other team $k$.

- If $1 \le k \le N-1$, then $X_k = 1$ if team $k$ ended up in groups $1$ through $i$. The probability of this occurring is $\tfrac{i}{T}$.
- If $N+1 \le k \le K$, then $X_k = 1$ if team $k$ ended up in groups $1$ through $i-1$. The probability of this occurring is $\tfrac{i-1}{T}$.

The expected draft position of team $N$ is therefore:

\[

1 + (N-1)\frac{i}{T} + (K-N)\frac{i-1}{T}

\]Remember that this was conditioned on team $N$ ending up in Group $i$, which happens with probability $\tfrac{1}{T}$. So the final expected draft position of team $N$ is therefore:

\begin{align}

\sum_{i=1}^T \frac{1}{T} \left( 1 + (N-1)\frac{i}{T} + (K-N)\frac{i-1}{T} \right) \\

\end{align}After simplifying (make use of this identity), we find that the expected final position for team $N$ is given by the formula

$\displaystyle

\frac{2N+(K+1)(T-1)}{2T}

$

We can perform a few quick sanity checks to convince ourselves that this solution is correct.

- When $T=1$ (only one group), the formula yields $N$, the same as the original seeding, as it should.
- When $K=N=1$ (only one team), the formula yields $1$, as it should.
- More precisely, if the original seed is $N = \tfrac{K+1}{2} + \Delta$, where $\Delta$ is the offset from the middle, the formula yields an expected draft position of $\tfrac{K+1}{2} + \tfrac{\Delta}{T}$. In other words, if you started off better than average, you can expect to end up better than average and similarly if you started below average. The division by $T$ shows that as you add more groups, the randomized drafting strategy has an equalizing effect.

In the particular case mentioned in the problem statement, we have $K=30$, $N=10$, and $T=2$, which leads to an expected value of $\frac{51}{4} = 12.75$.

While the expected draft position is not that difficult to characterize, one can also ask about the *distribution* of draft positions:

[Show Solution]

Finding the actual distribution of draft positions is more complicated that just finding its expected value. To find the distribution, we will answer the question: “what is the probability that team $N$ finishes with position $j$ given that it lands in Group $i$?”. We’ll compute the probability by counting the number of ways that $j-1$ other teams can end up ahead of team $N$ in the draft.

- Start by considering the teams $1 \le k \le N-1$, which are the teams that have a higher seed than team $N$. Suppose exactly $p$ of these teams end up in Group $i$. There are ${N-1 \choose p}$ ways this can happen, each with probability $\tfrac{1}{T}.$ Therefore we have a net probability of $\color{red}{P_1 = {N-1\choose p}\left(\tfrac{1}{T}\right)^p}$.
- Out of the remaining $N-1-p$ teams, suppose exactly $r$ of them end up in groups $1$ through $i-1$. There are ${N-1-p \choose r}$ ways this can happen, each with probability $\tfrac{i-1}{T}$. The net probability is $\color{red}{P_2 = {N-1-p \choose r}\left(\tfrac{i-1}{T}\right)^r}.$ If $i=1$, then $P_2=0$ for all values of $p$.
- The remaining $N-1-p-r$ teams must necessarily be in groups $i+1$ through $T$, each with probability $\tfrac{T-i}{T}$. The net probability is $\color{red}{P_3 = \left(\tfrac{T-i}{T}\right)^{N-1-p-r}}.$ If $i=T$, then $P_3=0$.
- There must be $j-1$ teams ahead of team $N$ in the final draft, and we have thus far accounted for $p+r$ of them. The rest must come from teams $N+1 \le k \le K$, which are the teams that have a lower seed than the team $N$. These must end up in groups $1$ through $i-1$. There are ${K-N \choose j-1-p-r}$ ways to do this, each with probability $\tfrac{i-1}{T}$. The net probability is $\color{red}{P_4 = {K-N \choose j-1-p-r}\left(\tfrac{i-1}{T}\right)^{j-1-p-r}}.$ If $i=1$, then $P_4=0$.
- The remaining $K-N-j+1+p+r$ teams must necessarily be in groups $i$ through $T$, each with probability $\tfrac{T-i+1}{T}$. The net probability is $\color{red}{P_5 = \left(\tfrac{T-i+1}{T}\right)^{K-N-j+1+p+r}}.$

This accounts for every possible arrangement, so to find the probability that team $N$ finishes with position $j$, we must sum over all possible values of $p$ and $r$, and then sum over possible values of $i$ while including an additional $\frac{1}{T}$ factor as we did in the solution to the first part. The final probability of interest is therefore:

\[

P(K,N,T,j) = \frac{1}{T}\sum_{i=1}^T \sum_{p=0}^{N-1} \sum_{r=0}^{N-1} P_1P_2P_3P_4P_5

\]Note that some terms will be identically zero. We use the convention that ${a \choose b} = 0$ if $b < 0$.
Unfortunately, this messy formula doesn't appear to simplify to anything nice, so we have to be content with computing it numerically. To illustrate what the result looks like, here is a plot of $P(30,10,T,j)$ as a function of $j$ and for increasing values of $T$ (the number of groups).

- When $T=1$, the distribution is concentrated at $N=10$, since there is no probability involved; each team will always be drafted in seed order.
- When $T=2$, the distribution is bimodal. Even though the initial seed was $N=10$ and the expected value of the final draft position is $12.75$ as we computed earlier, the probability of being drafted anywhere near the expected value is very low! This makes sense, because whether we end up in Group 1 or Group 2 has a substantial effect on our final draft position.
- Similar multi-modal distributions occur for $T=2,3,\dots$ Ultimately, the distribution converges to the uniform distribution. Again, this makes sense; if you imagine a
*very* large number of groups, the probability that two teams end up in the same group is vanishingly small. So the final draft position is essentially determined by the group number only.

Hi Laurent,

I think this solution fails a different sanity check. Take the case of a 30 team league and two groups, like Ollie posed, but consider the worst team (which would be N=1 in your formula, because that’s the way you defined N even though the problem said “N-th best record” not “N-th worst record”.)

Anyway, the worst team will always pick first in its group. It has a 50-50 chance of being in either group. Therefore its expected draft position is (1/2)(1+16) = 8.5.

Your formula gives 8.25

Either I’m missing something really basic, or Ollie has published an incorrect solution. If you can point out my mistake, great! Otherwise, I believe I have the correct general solution and I’d be happy to share it with you to check it out.

Thanks,

Greg

Never mind. I solved the wrong problem. I misread the instructions on how the teams are divided into groups as “divided equally into groups” rather than “divided with equal probability into groups”.

Laurent,

Nice work calculating the distribution. I had never worked that out. While the probabilities don’t simplify nicely, there is a neat formula for the variance of the position of team $N$ when there are $K$ teams and $T$ groups. Remarkably, it does not depend on N: $$\frac{(K^2-1)(T^2-1)}{12T^2}$$ I can send you the proof if you’d like.

Oh wow, that’s a beautiful formula! Fascinating that it doesn’t depend on $N$.

You missed another sanity check: when T=K you should have a purely random assignment, but your general answer depends on the team’s position N still.

A small mistake you made is that the probability of one of the other teams lands in group i given that one of the slots is taken by team N is a little bit lower than the probability it falls in any other group. I think this is enough to fix your solution.

In the randomization step, each team rolls a $T$-sided die to determine which group they fall in. So it’s definitely possible that two teams end up in the same group. If we have as many teams as groups ($T=K$), the final ordering shouldn’t be random. For example, every time the 1-seed team lands in a group with another team, they will always come out ahead. So we should expect the solution to depend on $N$.

The case where it becomes random is when $T\to\infty$. (infinitely many groups). In that scenario, the probability that two teams end up in the same group is vanishingly small, and the final ranking is simply a random permutation of the teams. I added this extra case to my write-up.