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

Cet article démontre que, dans un tournoi round-robin aléatoire à joueurs de force égale, si une fonction $k(n)$ tendant vers l'infini satisfait une condition de croissance spécifique, alors avec une probabilité tendant vers 1, les $k(n)$ scores les plus élevés (et par symétrie les plus bas) sont tous distincts.

L'essentiel

Voici une explication de ce papier de recherche, imaginée comme une histoire de tournoi, sans jargon mathématique complexe.

Le Grand Tournoi de l'Égalité

Imaginez un immense tournoi d'échecs (ou de ping-pong) où tout le monde joue contre tout le monde. C'est ce qu'on appelle un tournoi « round-robin » (tournoi toutes rondes).

Dans ce tournoi, il y a une règle très spéciale : tous les joueurs sont exactement de la même force. Personne n'est un génie, personne n'est un débutant. C'est une loterie parfaite. Chaque match se termine par un score qui peut être une victoire (1 point), une défaite (0 point), ou parfois un match nul (0,5 point), mais toujours de manière aléatoire.

Le but de l'article de Yaakov Malinovsky est de répondre à une question simple mais profonde :

Si on regarde les scores des joueurs, est-il possible que les meilleurs joueurs aient tous des scores différents, ou vont-ils forcément se retrouver à égalité ?

L'Analogie du « Chapeau de Scores »

Pour comprendre, imaginez que vous avez un chapeau rempli de billets de loterie. Chaque billet représente le score total d'un joueur à la fin du tournoi.

• Si vous avez 100 joueurs, vous avez 100 billets.
• Comme tout le monde est égal, la plupart des billets auront des valeurs très proches (autour de la moyenne).
• Mais certains billets seront très hauts (les gagnants) et d'autres très bas (les perdants).

La question est : Si on regarde les $k$ meilleurs billets (les $k$ meilleurs scores), est-ce qu'ils sont tous différents les uns des autres ?

Dans la vraie vie, si vous avez un petit tournoi, il est très fréquent que deux joueurs finissent avec exactement le même score (par exemple, deux joueurs finissent avec 4,5 points). C'est comme si deux billets de loterie avaient le même numéro.

La Découverte Magique

L'auteur a prouvé quelque chose de contre-intuitif : Si le tournoi est assez grand, et si on ne regarde pas trop de joueurs à la fois, alors les meilleurs joueurs auront presque certainement des scores uniques.

C'est comme si, dans une foule immense, la probabilité que deux personnes aient exactement la même taille (au millimètre près) devient nulle, à condition de ne comparer que les 10 personnes les plus grandes.

La condition magique :
Le papier donne une formule précise pour dire combien de joueurs ($k$) on peut regarder sans qu'il y ait d'égalité.

• Si le tournoi a $n$ joueurs.
• Et si le nombre de joueurs que l'on compare ($k$) est « petit » par rapport à la racine quatrième de $n$ (une façon mathématique de dire « beaucoup plus petit que la taille totale »).

Alors, avec une probabilité de 99,99 %, les $k$ meilleurs joueurs auront tous des scores distincts. Pas de partage de première place ! Pas de match nul pour le podium !

Pourquoi est-ce difficile à prouver ? (Le problème des « Jumeaux »)

Pourquoi ce n'est pas évident ? Parce que dans un tournoi, les scores ne sont pas indépendants. C'est comme une balance :

• Si le joueur A bat le joueur B, le joueur A gagne un point et le joueur B n'en gagne pas.
• Si le joueur A gagne, cela change automatiquement les chances que le joueur B ait un score élevé.

C'est ce qu'on appelle une dépendance négative : si l'un monte, l'autre a tendance à descendre. C'est comme une balançoire : si un enfant monte, l'autre descend. Cela rend les calculs très compliqués, car on ne peut pas traiter chaque joueur comme un lanceur de dés indépendant.

L'auteur a utilisé des outils mathématiques avancés (comme la « transformation de Cramér », qui est un peu comme une loupe pour voir les événements très rares) pour montrer que, malgré ces liens complexes entre les joueurs, la nature aléatoire finit par créer de la diversité dans les scores extrêmes.

En Résumé

1. Le Contexte : Un tournoi géant où tout le monde est égal.
2. Le Problème : Est-ce que les meilleurs joueurs finissent souvent à égalité ?
3. La Réponse : Non ! Si le tournoi est assez grand, les meilleurs joueurs auront presque toujours des scores uniques.
4. La Condition : Cela fonctionne tant qu'on ne compare pas trop de joueurs par rapport à la taille totale du tournoi.

C'est une preuve que dans le chaos d'un grand système aléatoire, l'individualité (ou ici, la distinction des scores) finit par émerger naturellement pour les extrêmes. C'est comme si la nature détestait les égalités parfaites parmi les champions, à condition que le groupe soit assez vaste.

Résumé technique

Voici un résumé technique détaillé de l'article « On the Size of the Largest Distinct Extreme Score Set in Random Round-Robin Tournaments » de Yaakov Malinovsky, rédigé en français.

1. Problématique et Contexte

L'article s'intéresse aux tournois complets aléatoires (round-robin) impliquant $n$ joueurs. Dans ce modèle, chaque paire de joueurs $(i, j)$ s'affronte une fois. Le score obtenu par le joueur $i$ contre $j$ est une variable aléatoire $X_{ij}$, et le score de $j$ contre $i$ est $X_{ji} = 1 - X_{ij}$.

Hypothèses du modèle (Modèle $M[0,1]$) :

• Les variables $X_{ij}$ prennent leurs valeurs dans un ensemble dénombrable $D \subset [0, 1]$.
• Les paires $(X_{ij}, X_{ji})$ sont indépendantes pour toutes les paires distinctes.
• Tous les joueurs sont de force égale, ce qui implique que les $X_{ij}$ sont identiquement distribués avec une espérance $\mu = E[X_{ij}] = 1/2$.
• Le score total d'un joueur $i$ est la somme de ses performances contre tous les autres : $s_i(n) = \sum_{j \neq i} X_{ij}$.

Objectif :
Le problème central est de déterminer la taille maximale $k(n)$ d'un ensemble de scores extrêmes (les $k$ plus grands ou les $k$ plus petits) qui soient tous distincts avec une probabilité tendant vers 1 lorsque $n \to \infty$.
Cela généralise un problème historique posé par Epstein (1967) pour les tournois classiques ($D=\{0,1\}$), où l'on cherchait à savoir si le joueur ayant le score maximal était unique. Malinovsky et Moon (2024) ont résolu ce cas, et Amir et Malinovsky (2026) l'ont étendu à l'existence d'un unique maximum. Ce papier va plus loin en caractérisant la taille de l'ensemble des scores distincts.

2. Méthodologie

L'auteur utilise une approche combinant la théorie des grandes déviations, l'analyse asymptotique des statistiques d'ordre et la théorie de la dépendance négative.

La preuve repose sur trois propositions clés pour démontrer que l'événement $U_{n,k}$ (les $k$ plus grands scores sont distincts) a une probabilité tendant vers 1.

Stratégie de preuve :

1. Définition d'un seuil critique : On définit un seuil $t_{n,k}$ tel que le nombre attendu de scores le dépassant soit de l'ordre de $k$. Ce seuil est défini par :
   $$t_{n,k} = (n-1)\mu + x_{n,k}(n-1)^{1/2}\sigma$$
   où $x_{n,k}$ est choisi pour que $n P(s_1(n) > t_{n,k}) \sim k$.

2. Contrôle du nombre de scores au-dessus du seuil :
   Soit $Z_t$ le nombre de joueurs ayant un score strictement supérieur à $t$. La première étape consiste à montrer que $Z_{t_{n,k}} \ge k$ avec une probabilité tendant vers 1. Cela est obtenu via l'inégalité de Chebychev et l'exploitation de la dépendance négative (negative dependence) des indicateurs de scores, un résultat établi dans des travaux précédents (Malinovsky et Rinott, 2023).

3. Contrôle des égalités (collisions) :
   Soit $W_n(t)$ le nombre de paires de joueurs $(u, v)$ ayant exactement le même score strictement supérieur à $t$. L'objectif est de montrer que $P(W_n(t_{n,k}) \ge 1) \to 0$.
   Pour cela, l'auteur calcule l'espérance $E[W_n(t_{n,k})]$. La méthode utilise :

   • Le conditionnement sur le résultat du match entre deux joueurs spécifiques.
   • La transformée de Cramér (tilting) pour borner les probabilités de grandes déviations pour les sommes de variables aléatoires discrètes.
   • Des inégalités de concentration (type Kolmogorov/Rogozin) pour borner la densité de probabilité des scores.

4. Synthèse :
   Si le nombre de scores au-dessus du seuil est $\ge k$ et qu'il n'y a aucune collision (égalité) parmi eux, alors les $k$ plus grands scores sont nécessairement distincts.

3. Résultats Principaux

Théorème 1 :
Soit $k(n)$ une suite telle que $k(n) \to \infty$ lorsque $n \to \infty$. Si la condition suivante est satisfaite :
$$\frac{k(n)^2 \log(n/k(n))}{\sqrt{n}} \to 0$$
Alors, la probabilité que les $k(n)$ scores les plus élevés soient tous distincts tend vers 1 :
$$\lim_{n \to \infty} P(U_{n,k(n)}) = 1$$

Corollaire 1 (Symétrie) :
Par symétrie du modèle ($X_{ij} \stackrel{d}{=} 1 - X_{ij}$), le même résultat s'applique aux $k(n)$ scores les plus faibles.

Interprétation de la condition :
La condition impose une limite sur la croissance de $k(n)$. Par exemple, si $k(n) = o((n/\log n)^{1/4})$, le théorème s'applique. Cela signifie que l'on peut garantir l'unicité d'un nombre croissant de scores extrêmes, mais ce nombre ne peut pas croître aussi vite que la racine carrée de $n$ (à cause du terme $\sqrt{n}$ au dénominateur).

4. Contributions Clés

1. Généralisation du modèle : Extension des résultats d'unicité du maximum (cas $k=1$) à un ensemble de taille $k(n)$ croissante, dans un cadre général de scores continus ou discrets ($D \subset [0,1]$).
2. Traitement de la dépendance négative : Utilisation rigoureuse de la propriété de dépendance négative des scores dans les tournois complets pour borner la variance du nombre de scores extrêmes, ce qui est crucial car les scores ne sont pas indépendants (la somme des scores est fixée par les matchs).
3. Technique de Cramér pour les collisions : Développement d'une borne fine sur la probabilité que deux joueurs aient exactement le même score élevé, en utilisant la méthode de changement de mesure (tilting) adaptée aux variables discrètes.
4. Résolution asymptotique : Fourniture d'une condition suffisante précise et optimale (dans le contexte des méthodes utilisées) pour la distinctivité des scores extrêmes.

5. Signification et Impact

Ce travail apporte une compréhension profonde de la structure des scores dans les tournois aléatoires, un problème fondamental en théorie des graphes aléatoires et en statistiques des comparaisons appariées.

• Théorie des graphes : Contrairement aux graphes aléatoires d'Erdős-Rényi où les dépendances sont positives (l'existence d'une arête n'influence pas négativement les autres), les tournois présentent une dépendance négative (un joueur gagne, un autre perd). Ce papier exploite cette propriété spécifique pour obtenir des résultats de concentration.
• Statistiques et Inférence : Les résultats sont pertinents pour l'évaluation des performances dans les compétitions sportives ou les systèmes de classement (comme aux échecs), en quantifiant la probabilité de "classements stricts" (sans ex-aequo) parmi les meilleurs joueurs.
• Limites de la distinctivité : Le papier établit une frontière mathématique claire : au-delà d'une certaine taille $k(n)$, il devient inévitable d'avoir des égalités parmi les scores extrêmes en raison de la discrétisation des scores et de la taille finie de l'échantillon.

En résumé, Malinovsky démontre que pour des tournois de grande taille, tant que l'on ne considère pas un nombre trop grand de joueurs (sub-linéaire par rapport à $\sqrt{n}$), les scores des meilleurs (et des pires) joueurs seront presque sûrement tous différents, ce qui valide l'existence de classements stricts dans des modèles probabilistes réalistes.