Combinatorics Seminar: Two probabilistic proofs of Moon's Theorem and the Bradley-Terry model

Seminar | February 11 | 12:10-1 p.m. | 939 Evans Hall | Note change in date

 Brett Kolesnik, UC Berkeley

 Department of Mathematics

In an n-team tournament, each pair of teams plays a win-lose match. Landau's Theorem (1953) states that a sequence (x1,x2,...,xn), written in non-decreasing order, is the score sequence of some n-team tournament if and only if it is majorized by (0,1,...,n-1), meaning that all partial sums x1+...+xk are at least k(k-1)/2, with equality for k=n. Moon's Theorem (1963) extends this to random tournaments, in which case x is the mean score sequence. We give two short, probabilistic proofs of Moon's Theorem, one of which is fully constructive. We also show that the set of mean score sequences is the closure of those arising from the Bradley-Terry model (a model for sports results), where for a sequence of abilities (a1,a2,...,an), the probability that team i beats j is L(ai-aj), where $L(x)=e^x/(1+e^x)$ is the logistic function. This talk offers a glimpse into a longstanding mystery: the lack of a canonical construction for a joint distribution in the representation theorem (Strassen 1965) for convex order. This is joint work with David Aldous.