On the Size of the Largest Distinct Extreme Score Set in Random Round-Robin Tournaments

Het bewijst dat in een willekeurige round-robin-toernooimodel met even sterke spelers, met een waarschijnlijkheid die naar één convergeert, de $k(n)$ hoogste (en laagste) scores allemaal verschillend zijn zolang $k(n)$ naar oneindig gaat en aan een specifieke asymptotische voorwaarde voldoet.

De kern

Hier is een uitleg van het onderzoek in eenvoudig Nederlands, met behulp van alledaagse vergelijkingen.

Het Grote Toernooi: Een Verhaal over Gelijke Kans en Unieke Winnaars

Stel je een groot toernooi voor, zoals een schaaktoernooi of een voetbalcompetitie, waarbij iedere speler tegen iedereen speelt. Dit noemen we een "round-robin" toernooi.

In dit specifieke onderzoek kijken we naar een heel eerlijk toernooi:

1. Alle spelers zijn even sterk. Er is geen favoriet.
2. Elke wedstrijd levert precies 1 punt op. Als speler A wint, krijgt hij 1 punt en B 0. Als ze gelijk spelen, krijgen ze beiden 0,5. Als er een andere uitkomst mogelijk is (bijvoorbeeld 0,8 en 0,2), telt het altijd op tot 1.
3. Het is puur geluk. Omdat iedereen even sterk is, hangt de uitslag puur van het toeval af.

De vraag die de auteur, Yaakov Malinovsky, stelt, is heel simpel maar verrassend moeilijk om wiskundig te bewijzen:

"Als er heel veel spelers zijn, hoe groot moet de groep van de 'topscorers' zijn voordat we zeker weten dat ze allemaal een verschillend aantal punten hebben?"

Stel je voor dat er 1000 spelers zijn. De top 10 heeft waarschijnlijk allemaal een heel hoog aantal punten. Maar is het mogelijk dat twee van die top 10 precies evenveel punten hebben? (Bijvoorbeeld: beide hebben 750 punten).

De Kern van het Onderzoek

De wiskundige bewijst dat als het toernooi groot genoeg wordt, de kans dat de top-spelers (en ook de onder-spelers) allemaal een uniek score hebben, bijna 100% is.

Maar er is een voorwaarde: de groep die je bekijkt mag niet te groot zijn.

Stel je een trechter voor:

• Als je kijkt naar de top 5 spelers in een toernooi van 10.000 mensen, is het bijna zeker dat ze allemaal een ander score hebben.
• Als je kijkt naar de top 5.000 spelers, is de kans groot dat er veel mensen met precies hetzelfde score zitten (want er is niet genoeg ruimte in de "ladder" om iedereen uniek te maken).

De formule in het paper (die er misschien eng uitziet: $k(n)^2 \log(n/k(n)) / \sqrt{n} \to 0$) is eigenlijk een rekenregel die zegt:
"Je mag de groep van 'topscorers' die je bekijkt laten groeien naarmate het toernooi groter wordt, maar ze mogen niet te snel groeien. Als ze te snel groeien, gaan de scores gaan 'kruipen' en elkaar raken (dus gelijk worden)."

De Analogie: De Drukte op een Feest

Laten we het vergelijken met een groot feest:

• De Spelers: Iedereen op het feest.
• De Scores: Hoeveel glazen drankje iemand heeft gedronken. Omdat iedereen even veel kans heeft om een glas te pakken, is het gemiddelde aantal glazen voor iedereen hetzelfde.
• Het Doel: Kijken we naar de mensen met de meeste drankjes.

Als er 100 mensen zijn, en je kijkt naar de top 3, is het heel waarschijnlijk dat de eerste 10 glazen, de tweede 10,5 en de derde 11 heeft. Ze zijn uniek.
Maar als je kijkt naar de top 50 mensen, is de kans groot dat er 5 mensen zijn die precies 12 glazen hebben gedronken. Ze "kruipen" tegen elkaar aan.

De wiskundige formule zegt eigenlijk: "Zolang je kijkt naar een groep die klein genoeg is in verhouding tot het totale aantal mensen (en niet te snel groeit), zullen de 'winnaars' altijd een unieke rang hebben. Er zal geen gelijkspel zijn in de top."

Waarom is dit belangrijk?

In de echte wereld (zoals bij schaken of sport) willen we vaak weten wie de beste is. Als twee spelers precies evenveel punten hebben, is het lastig om te zeggen wie de echte winnaar is.

Dit paper zegt ons:

1. In een groot, eerlijk toernooi is het bijna onmogelijk dat de absolute top een gelijkspel heeft. De "winnaar" is bijna altijd uniek.
2. Dit geldt ook voor de onderkant: de slechtste spelers hebben bijna altijd een uniek, laag score.
3. De wiskundige heeft een nieuwe manier gevonden om dit te bewijzen, door te kijken naar hoe "negatief afhankelijk" de scores zijn.

Wat betekent "negatief afhankelijk"?
Stel je voor dat speler A heel veel punten haalt. Dan betekent dit automatisch dat zijn tegenstanders minder punten hebben gekregen (want de som is altijd 1). Als A wint, verliest B. Als A heel goed scoort, duwt dat de scores van anderen omlaag. Ze "duwen" elkaar uit elkaar, in plaats van dat ze samen naar boven gaan. Deze duwkracht zorgt ervoor dat de scores zich verspreiden en minder snel op elkaar gaan lijken.

Samenvatting in één zin

Als je een heel groot, eerlijk toernooi organiseert, is het statistisch bijna zeker dat de beste spelers (en de slechtste spelers) allemaal een uniek aantal punten hebben, zolang je niet naar een te grote groep kijkt; de natuur van het spel zorgt er namelijk voor dat gelijke scores in de top zeldzaam zijn.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "On the Size of the Largest Distinct Extreme Score Set in Random Round-Robin Tournaments" van Yaakov Malinovsky, geschreven in het Nederlands.

Titel en Context

Titel: Over de grootte van de grootste verzameling van unieke extreme scores in willekeurige round-robin-toernooien.
Auteur: Yaakov Malinovsky (University of Maryland, Baltimore County).
Datum: 10 maart 2026 (voorgesteld).

1. Probleemstelling

Het paper onderzoekt een algemeen model voor round-robin-toernooien (waarbij elke speler tegen elke andere speler speelt) met $n$ spelers.

• Het Model ($M[0,1]$): Elke wedstrijd tussen speler $i$ en speler $j$ resulteert in een score $X_{ij}$ voor speler $i$ en $X_{ji}$ voor speler $j$.
  • De scores liggen in een aftelbare verzameling $D \subset [0, 1]$.
  • Er geldt de symmetrie: $X_{ij} + X_{ji} = 1$.
  • Alle spelers zijn "even sterk", wat betekent dat de $X_{ij}$ identiek verdeeld zijn.
  • De totale score van speler $i$ is $s_i(n) = \sum_{j \neq i} X_{ij}$.
• Het Doel: De auteurs willen bepalen onder welke voorwaarden de $k(n)$ hoogste scores in het toernooi paarsgewijs verschillend (uniek) zijn met een waarschijnlijkheid die naar 1 convergeert naarmate $n \to \infty$.
• Achtergrond: Dit bouwt voort op eerdere werken (o.a. Epstein, Guy, Malinovsky & Moon) die zich richtten op de uniciteit van de enkele hoogste score. Dit paper generaliseert dit naar een set van $k(n)$ extreme scores.

2. Methodologie

De bewijsvoering maakt gebruik van een combinatie van grote afwijkingen-theorie (large deviations), asymptotische analyse en de eigenschappen van negatieve afhankelijkheid in toernooimodellen.

Kernconcepten:

1. Gedefinieerde Grootheden:
   • $\mu = E[X_{ij}] = 1/2$ (door symmetrie).
   • $\sigma = \sqrt{Var(X_{ij})} \leq 1/2$.
   • Een drempelwaarde $t_{n,k}$ wordt gedefinieerd als: $t_{n,k} = (n-1)\mu + x_{n,k}(n-1)^{1/2}\sigma$, waarbij $x_{n,k}$ zo wordt gekozen dat het verwachte aantal scores boven deze drempel ongeveer $k(n)$ is.
2. Evenementen:
   • $Z_{t}$: Het aantal spelers met een score $> t$.
   • $W_n(t)$: Het aantal paren spelers $(u, v)$ met gelijke scores $> t$.
   • Het doel is om te bewijzen dat $P(W_n(t_{n,k}) = 0 \text{ en } Z_{t_{n,k}} \geq k(n)) \to 1$.
3. Technische Hulpmiddelen:
   • Cramér-transformatie: Gebruikt om de kansen van zeldzame gebeurtenissen (extreme scores) te schatten via de Cramér-vertegenwoordiging (tilted random variables).
   • Negatieve afhankelijkheid: Het paper maakt gebruik van het feit dat de indicatorvariabelen voor hoge scores negatief geassocieerd zijn (bewezen in eerdere werken van Malinovsky en Rinott). Dit stelt de auteurs in staat om Chebyshev-ongelijkheden effectief toe te passen op de som van deze variabelen, ondanks de correlaties tussen de scores van verschillende spelers.
   • Concentratie-ongelijkheden: Gebruik van resultaten van Rogozin en Kolmogorov over de afname van de concentratiefunctie voor sommen van discrete willekeurige variabelen.

3. Belangrijkste Resultaten

Hoofdstelling (Theorem 1):
Laat $k(n) \to \infty$ als $n \to \infty$. Als de volgende voorwaarde geldt:
$$\frac{k(n)^2 \log(n/k(n))}{\sqrt{n}} \to 0$$
dan geldt:
$$\lim_{n \to \infty} P(\text{de } k(n) \text{ hoogste scores zijn paarsgewijs verschillend}) = 1.$$

Corollarium 1:
Door symmetrie geldt hetzelfde resultaat voor de $k(n)$ laagste scores. Als de hoogste $k$ scores uniek zijn, zijn ook de laagste $k$ scores uniek.

Specifiek geval (Opmerking 1):
De voorwaarde is bijvoorbeeld vervuld als $k(n) = o((n/\log n)^{1/4})$. Dit betekent dat men een groeiend aantal top-scores kan garanderen dat uniek is, zolang dit aantal niet te snel groeit ten opzichte van $n$.

4. Bewijsstructuur (Samengevat)

Het bewijs van Theorem 1 rust op drie proposities:

1. Propositie 1: Bepaalt de drempel $t_{n,k}$ en toont aan dat het verwachte aantal spelers met score $> t_{n,k}$ asymptotisch gelijk is aan $(1+\delta)k(n)$. Dit maakt gebruik van de normaalbenadering en de Cramér-transformatie voor grote afwijkingen.
2. Propositie 2: Toont aan dat de kans dat het werkelijke aantal spelers boven de drempel kleiner is dan $k(n)$, naar 0 gaat. Dit wordt bewezen met Chebyshev's ongelijkheid, waarbij de negatieve covariantie tussen de scores essentieel is om de variantie te beheersen.
3. Propositie 3: Bepaalt een bovengrens voor het verwachte aantal paren met gelijke scores boven de drempel ($E[W_n(t_{n,k})]$). De schatting is van de orde $O\left(\frac{k(n)^2 \log(n/k(n))}{\sqrt{n}}\right)$. Als deze term naar 0 gaat, is de kans op een gelijkheid (en dus een niet-unieke score) verwaarloosbaar.

De combinatie van deze drie stellingen (via de ongelijkheid $P(U^c) \leq P(Z < k) + P(W > 0)$) levert het bewijs op.

5. Betekenis en Bijdrage

• Generalisatie: Het paper verlegt de focus van de uniciteit van één winnaar naar de uniciteit van een verzameling van top-presteraars. Dit is relevant voor statistische inferentie in sporten en vergelijkingsmodellen.
• Wiskundige Scherpte: Het biedt een scherpe asymptotische voorwaarde voor de grootte van de unieke extreme set. De gebruikte methode combineert klassieke kansrekening met geavanceerde technieken voor negatieve afhankelijkheid in grafentheoretische structuren.
• Toepassing: De resultaten zijn van toepassing op elk toernooimodel waar scores in $[0,1]$ liggen en spelers even sterk zijn, inclusief het klassieke model met win/verlies ($D=\{0,1\}$) en meer complexe scoringssystemen.
• Verwante Gebieden: Het paper maakt een interessante vergelijking met willekeurige grafen (Erdős-Rényi), maar benadrukt dat round-robin-toernooien een vorm van negatieve afhankelijkheid vertonen, wat de analyse fundamenteel anders maakt dan bij onafhankelijke randen in grafen.

Kortom, het paper levert een rigoureus wiskundig bewijs dat in grote, willekeurige round-robin-toernooien met even sterke spelers, een aanzienlijk aantal top-scores met hoge waarschijnlijkheid uniek is, mits het aantal beschouwde scores niet te snel groeit ten opzichte van het totale aantal spelers.