Tournaments and random walks

Abstract

We study the relationship between tournaments and random walks. This connection was first observed by Erdős and Moser. Winston and Kleitman came close to showing that $S_n=\hat{I}˜(4^n/n^{5/2})$. Building on this, and works by Takács, these asymptotic bounds were confirmed by Kim and Pittel. In this work, we verify Moser's conjecture that $S_n\sim C{4}^n/n^{5/2}$, using limit theory for integrated random walk bridges. Moreover, we show that $C$ can be described in terms of random walks. Combining this with a recent proof and number-theoretic description of $C$ by the second author, we obtain an analogue of Louchard's formula, for the Laplace transform of the squared Brownian excursion/Airy area measure. Finally, we describe the scaling limit of random score sequences, in terms of the Kolmogorov excursions, studied recently by Bär, Duraj and Wachtel. Our results can also be interpreted as answering questions related to a class of random polymers, which began with influential work of SinaÄ­. From this point of view, our methods yield the precise asymptotics of a persistence probability, related to the pinning/wetting models from statistical physics, that was estimated up to constants by Aurzada, Dereich and Lifshits, as conjectured by Caravenna and Deuschel.

v3: added ref #25 + corrected typo in Prop 21