Library · The Fiddler: Solutions · Chapter 82
Can You Play the Favorite?
In a four-team region seeded through , when an -seed plays an -seed the -seed wins with probability . The bracket is vs and vs , and the winners meet. What is the probability the -seed wins the region?
The Fiddler, Zach Wissner-Gross, March 21, 2025(original post)
Solution
The -seed beats the -seed with probability , then meets the -seed (who arrives with probability ) or the -seed (probability ):
The computation
Encode the bracket: the -seed must beat its first opponent, then beat whichever of the - and -seeds survives, each path weighted by the model’s win probabilities.
from fractions import Fraction as F
beat = lambda m, n: F(n, m + n) # P(m-seed beats n-seed)
print(beat(1, 4) * (beat(2, 3)*beat(1, 2) + beat(3, 2)*beat(1, 3))) # 14/25
Extra Credit
As before, an -seed beats an -seed with probability . Now a region has teams, where is a very large whole number, seeded to and played in the traditional format: in the first round opponents’ seeds add up to , in the second round they would add up to if the stronger team always advanced, and so on. What is the probability that the -seed wins the region?
Solution
Fold the bracket up from the bottom. Each slot in each round has a distribution over which seed arrives there; when two slots meet, every pair of possible arrivals plays, and the winner’s distribution follows from the win rule. The first few values are exact fractions: The probability falls as grows, because the -seed has more rounds to survive. The question is where it ends up, and the key observation is that it does not fall to zero, nor to one half, but levels off.
Here is why. The -seed’s opponent in the round steps before the end comes from a block of the bracket whose favourite is seed or so, and in the early rounds of a huge bracket that opponent is almost always one of the block’s strong seeds. Against a seed near the -seed loses with probability , about . The chances of losing in successive rounds, counting back from the final, are therefore roughly proportional to , a sum that stays finite however many rounds are added. Adding an extra early round to a big bracket costs the -seed only a sliver, and the slivers shrink geometrically. So the probability tends to a definite limit. The early rounds are nearly free; the final few rounds against seeds , , , , … decide it.
That limit has no closed form that I know of, but the exact fold-up converges fast: from on, each further round changes the value by less than , and from on by less than . For a very large region, a little better than a coin toss. (The source’s value is paywalled; this is my own.)
The computation
The fold-up described above, carried out exactly (in floating point) for brackets of up to teams. The bracket order puts seeds and side by side, recursively, which is the traditional seeding.
import numpy as np
def bracket(k):
"""Seeds in bracket order: neighbours meet in round 1, and so on."""
o = [1]
while len(o) < 2**k:
m = 2*len(o) + 1
o = [x for s in o for x in (s, m - s)]
return o
def one_seed_wins(k):
# each slot: (seeds that can emerge, probability of each)
slots = [(np.array([s]), np.array([1.0])) for s in bracket(k)]
while len(slots) > 1:
nxt = []
for (s1, p1), (s2, p2) in zip(slots[0::2], slots[1::2]):
meet = p1[:, None]*p2[None, :] # who meets whom
a, b = s1[:, None], s2[None, :]
w1 = (meet*b/(a + b)).sum(axis=1) # M beats N w.p. N/(M+N)
w2 = (meet*a/(a + b)).sum(axis=0)
nxt.append((np.concatenate([s1, s2]), np.concatenate([w1, w2])))
slots = nxt
seeds, probs = slots[0]
return probs[seeds == 1][0]
for k in (2, 4, 6, 8, 10, 12, 14):
print("k = %2d: %.7f" % (k, one_seed_wins(k)))
It prints
k = 2: 0.5600000
k = 4: 0.5192184
k = 6: 0.5158337
k = 8: 0.5154592
k = 10: 0.5154323
k = 12: 0.5154313
k = 14: 0.5154314
The values settle at ; the last digit wobbles only through rounding in the floating-point sums.