How Likely Is a Lopsided League?

Fiddler League Baseball has six divisions of five teams each. Suppose each team’s winning percentage is chosen uniformly at random between $0$ and $100$ percent, independently of every other team. What is the probability that every team in the East division has a higher winning percentage than every team in the Central division?

The Fiddler, Zach Wissner-Gross, September 15, 2023(original post)

The official solution appeared in the post of September 22, 2023 and gives $1/252$ for the main puzzle and $2{,}565{,}091/29{,}745{,}716 \approx 8.6234$ percent for the Extra Credit. Both agree with the answers below.

Solution

The actual percentages do not matter, only their order. Two teams tie with probability zero, so the ten teams of the two divisions finish in some order from best to worst, and since the percentages are independent and identically distributed, all $10!$ orders are equally likely.

Now forget which team is which and keep only the division: write E for an East team and C for a Central team, and read the ten teams from best to worst. Each order of the ten teams gives a string of five Es and five Cs, and every string arises from exactly $5! \times 5!$ orders (shuffle the Es among themselves and the Cs among themselves). So all strings are equally likely too. There are $\binom{10}{5} = 252$ of them, and East is wholly above Central for just one, EEEEECCCCC. $$\boxed{\ \frac{1}{252} \;\approx\; 0.40\% . \ }$$

The computation

The program builds the ranking one team at a time, from the top. At each step the next team is equally likely to be any team not yet placed, which is exactly what a random order means. It tracks only how many teams of each division have been placed, and adds up the exact probabilities, with fractions, of all the ways the event can turn out. For the main puzzle the event is decided as soon as either the first Central team is placed (failure, unless East is already complete) or the fifth East team is (success).

from fractions import Fraction
from functools import lru_cache

SIZE = 5   # teams per division

def chance(divisions, verdict):
    """Rank all teams from best to worst, one at a time: the
    next team is equally likely to be any team not yet
    ranked. counts[d] is how many of division d are ranked so
    far; verdict(counts) is 1 or 0 once the event is decided,
    None while it is still open. Returns the exact chance."""
    @lru_cache(None)
    def p(counts):
        v = verdict(counts)
        if v is not None:
            return Fraction(v)
        left = divisions * SIZE - sum(counts)
        total = Fraction(0)
        for d, c in enumerate(counts):
            if c < SIZE:
                nxt = counts[:d] + (c + 1,) + counts[d + 1:]
                total += Fraction(SIZE - c, left) * p(nxt)
        return total
    return p((0,) * divisions)

def east_over_central(counts):
    east, central = counts
    if east == SIZE:            # East all ranked: did any
        return int(central == 0)  # Central team come first?
    return 0 if central else None

main = chance(2, east_over_central)
print("main:", main, f"= {float(main):.5f}")

It prints

main: 1/252 = 0.00397

Extra Credit

Across all six divisions, what is the probability that there are two divisions such that every team in one has a higher winning percentage than every team in the other?

Solution

A first guess multiplies: there are $6 \times 5 = 30$ ordered pairs of divisions, each with chance $1/252$, giving $30/252 \approx 11.9\%$. That overcounts. When one division sits wholly above another it tends to sit above others too, so the pairs come in clumps, and the clumps are counted several times over.

A cleaner picture comes from thinking of each division as a span: the stretch of percentages from its worst team, $m$, to its best team, $M$. Division $X$ lies wholly above division $Y$ exactly when $X$’s span starts above the point where $Y$’s ends, $m_X > M_Y$. Some pair like this exists exactly when the highest of the six worst-team values is above the lowest of the six best-team values. (The two values must then come from different divisions, since within a single division the worst is below the best.) So the event fails exactly when the highest worst-team value is below every best-team value: when all six spans share a common point.

To find the chance that the spans share a point, look at the division whose worst team is highest; call it $D$, and write that worst-team value as a fraction $t$ between $0$ and $1$. For this to happen with all spans sharing a point:

• one of $D$’s five teams is at $t$ and its other four are above $t$, which has probability density $5(1 - t)^4$;

• each of the other five divisions has a team below $t$ (so $D$’s worst is the highest) and a team above $t$ (so its span reaches $t$). For one division the chance is $1 - t^5 - (1 - t)^5$, removing the cases all below and all above.

The six choices of $D$ give six cases that cannot overlap, so the chance $q$ that the spans share a point is $$q \;=\; 6 \int_0^1 5(1 - t)^4 \bigl(1 - t^5 - (1 - t)^5\bigr)^5 \, dt .$$ The integrand is a polynomial, so this is exact arithmetic. Expand the fifth power as a sum of terms $t^{5a}(1 - t)^{5b}$, with $a + b + c = 5$ and coefficients $\frac{5!}{a!\,b!\,c!}(-1)^{a+b}$, multiply each by the factor $(1 - t)^4$, and integrate with the standard formula $\int_0^1 t^p (1 - t)^q\,dt = \frac{p!\,q!}{(p + q + 1)!}$: $$\begin{aligned} q &\;=\; 30 \sum_{a + b + c = 5} \frac{5!}{a!\,b!\,c!}\,(-1)^{a+b}\,\frac{(5a)!\,(5b + 4)!}{(5a + 5b + 5)!} \\ &\;=\; \frac{27{,}180{,}625}{29{,}745{,}716} . \end{aligned}$$ The sum has $21$ terms. The answer is the complement: $$\boxed{\ 1 - q \;=\; \frac{2{,}565{,}091}{29{,}745{,}716} \;\approx\; 8.6234\% . \ }$$ That is well short of the $11.9\%$ first guess, as the clumping argument predicted.

The computation

The ranking program from The computation above, now with six divisions. It uses none of the span argument. Reading down the ranking, some division lies wholly above another exactly when one division has all five teams placed while another has none placed yet. The first moment any division is completed settles the matter: if some division has not yet begun, the completed one lies above it; if every division has begun, each one’s best team is already above every division’s worst team, so no division can lie wholly above another.

def some_division_over_another(counts):
    if SIZE in counts:          # first division completed:
        return int(0 in counts)   # has some other not begun?
    return None

extra = chance(6, some_division_over_another)
print("extra credit:", extra, f"= {float(extra):.6f}")

It prints

extra credit: 2565091/29745716 = 0.086234