Logo

Mathematical Sciences Research Institute

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

Seminar

Combinatorics Seminar: Two probabilistic proofs of Moon's Theorem and the Bradley-Terry model February 11, 2019 (12:10 PM PST - 01:00 PM PST)
Parent Program: --
Location: UC Berkeley Math (Evans Hall 939)
Speaker(s) Brett Kolesnik (University of California, Berkeley)
Description No Description
Video
No Video Uploaded
Abstract/Media

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.

No Notes/Supplements Uploaded No Video Files Uploaded