La méthode probabiliste a été introduite par Paul Erdős, un mathématicien prolifique d’origine hongroise, dont il a déjà été question à plusieurs reprises sur Images des Maths, par exemple ici et là. Cette méthode trouve de nombreuses applications, plus particulièrement en combinatoire et en théorie des graphes, mais également dans d’autres domaines tels que la théorie des nombres. Nous allons l’illustrer ici dans le cadre d’un problème qui apparaît lorsqu’on veut classer les participants d’un tournoi.

Tournois indécis

Imaginons un tournoi dans lequel s’affrontent un certain nombre de joueurs (ou d’équipes). Ses règles de base sont les suivantes :

1. Chaque joueur affronte successivement tous les autres joueurs.
2. Dans chaque match il y a un vainqueur et un perdant (pas d’ex æquo).

La seconde règle est réalisée par exemple dans un match de tennis (alors que les tournois de tennis habituels n’obéissent pas à la première règle, ce que nous allons ignorer). Mais le tournoi peut tout aussi bien être un tournoi d’échecs ou de « chifoumi » évoqué ici.

Commençons par le cas où trois joueurs participent au tournoi. Nous les appellerons (c’est juste un exemple [1]) Roger, Rafael et Novak. Combien d’issues ce tournoi peut-il avoir ? Pour les dénombrer, il est utile de commencer par géométriser le problème, en représentant chaque issue possible par un graphe. Les sommets du graphe sont les joueurs, et pour chaque match, nous traçons une flèche allant du vainqueur au perdant. Cela donne un graphe dit complet (il y a exactement une arête entre toute paire de sommets, à cause de la règle 1) et orienté (chaque arête a un seul sens, ce qui reflète la règle 2). Il y a exactement $8$ graphes possibles, les voici :

Dans la suite, nous appellerons tournoi chacune des issues possibles. On peut classer ces tournois en deux catégories :

1. Les tournois représentés en bleu, dans lesquels un joueur a gagné deux matchs, un joueur a perdu deux matchs, et un joueur a gagné un match et perdu l’autre.
2. Les tournois représentés en rouge, dans lesquels chaque joueur a gagné un match et perdu l’autre.

Dans le premier cas, on peut facilement établir un classement, alors que dans le second cas ce n’est pas possible (à moins de tenir compte de critères supplémentaires, par exemple le nombre de manches gagnées). Nous appellerons indécis un tournoi dans lequel chaque joueur est battu par au moins un autre joueur.

Un tournoi peut-il être indécis pour n’importe quel nombre de joueurs ? La réponse est oui, pourvu qu’il y ait au moins $3$ joueurs. En effet, il suffit que le graphe contienne un cycle, c’est-à-dire qu’on puisse ordonner les joueurs de telle manière que le premier batte le second, le second le troisième, et ainsi de suite jusqu’au dernier qui bat le premier. Ce tournoi sera indécis quel que soit le résultat des autres matchs.

Tournois $2$-indécis

Corsons le problème en considérant des paires de joueurs. Si les deux joueurs formant la paire ont été battus par un même troisième joueur, on peut considérer qu’ils ne sont pas les plus forts et ne méritent pas de gagner le tournoi. Une possibilité de déterminer un vainqueur serait de ne retenir que les paires de joueurs n’ayant jamais été battus par un même joueur, et de faire rejouer uniquement ces joueurs-là jusqu’à ce qu’on ait déterminé un champion. Mais est-ce possible ?

Un tournoi avec $3$ joueurs ne peut être $2$-indécis : par exemple, si Roger et Rafael ont été battus par Novak, il ne peut y avoir de joueur ayant battu à la fois Roger et Novak.

Il n’y a pas non plus de tournois $2$-indécis à $4$ joueurs. Si Rafael et Novak ont été battus par Roger, le quatrième joueur (Stan) est le seul susceptible d’avoir battu à la fois Roger et Rafael. Mais il ne reste personne qui aurait pu battre la paire Roger et Stan.

Qu’en est-il des tournois à plus de $4$ joueurs ? La question n’est pas évidente, car en augmentant le nombre de joueurs, on augmente le nombre de joueurs pouvant battre une paire donnée, mais on augmente également le nombre de paires.

Au fait, combien existe-t-il de tournois à $n$ joueurs ? Déterminons tout d’abord le nombre de matchs d’un tel tournoi. Chaque joueur doit affronter les $n-1$ autres joueurs, ce qui nous donne $n(n-1)$ matchs. Mais en faisant cela, on a compté doublement le match d’un joueur A contre le joueur B et celui de B contre A. Il convient donc de diviser le nombre obtenu par $2$, ce qui nous donne
\[ \frac{n(n-1)}{2} \qquad \text{matchs.} \]
Comme chaque match a deux issues possibles, cela nous fait un total de
\[ 2^{n(n-1)/2} \qquad \text{tournois à } n \text{ joueurs.} \]
Par exemple, si $n=3$ nous retrouvons $\frac{3\times 2}{2}=3$ matchs et $2^3=8$ tournois possibles. Si $n=4$, il y a $6$ matchs, et $2^6=64$ tournois possibles. Si $n=9$, le nombre de tournois possibles est $2^{36}$, ce qui équivaut à peu près au nombre de secondes écoulées depuis la naissance d’Hipparque (vers $190$ av. J.-C.) [2].

Tester tous les tournois possibles, même avec un ordinateur très puissant, devient donc vite impraticable.

La méthode probabiliste

Pour déterminer s’il existe des tournois $2$-indécis à plus de $4$ joueurs sans les examiner un par un, la méthode probabiliste s’avère utile. Pour l’appliquer, il faut d’abord définir un espace probabilisé. Dans le cadre qui nous occupe, un tel espace est défini à l’aide de deux ingrédients :

1. Un univers, qui est simplement l’ensemble des éventualités (ou événements élémentaires) envisagées ; dans notre cas, une éventualité sera un tournoi, l’univers étant alors l’ensemble des tournois possibles, pour un nombre donné de joueurs.
2. Une distribution de probabilité sur notre univers ; elle associe à chaque éventualité un nombre entre $0$ et $1$ (sa probabilité), avec pour condition que la somme de toutes les probabilités soit égale à $1$.

Un événement est n’importe quel ensemble d’éventualités [3]. Par exemple, dans le cas de $3$ joueurs, l’événement « Rafael bat Novak » est composé de quatre éventualités, correspondant aux issues possibles des deux matchs opposant Roger à Novak et à Rafael. Sa probabilité est simplement la somme des probabilités des éventualités qui le composent. Nous supposerons que toutes les éventualités ont une probabilité non nulle ; ainsi il en sera de même pour tous les événements non vides.

L’observation simple de Paul Erdős est la suivante :

Si un événement a une probabilité non nulle, alors il existe au moins une éventualité qui le réalise.

On remarquera que ce principe reste vrai quelle que soit la distribution de probabilité choisie. Cette flexibilité nous autorise à choisir la distribution de la manière qui nous arrange le mieux. En fait, nous allons simplement donner la même probabilité à tous les tournois (donc $\frac18$ dans le cas de $3$ joueurs). Cela revient à supposer que chaque match est gagné avec probabilité $\frac12$ par l’un ou l’autre joueur, comme s’ils décidaient du résultat en lançant une pièce de monnaie, et que tous les matchs sont indépendants.

Notre but est donc de montrer que la probabilité qu’un tournoi soit $2$-indécis est strictement positive à partir d’un certain nombre de joueurs. Pour cela, deux règles du calcul des probabilités suffiront :

1. Si $A$ et $B$ sont des événements indépendants, alors $\text{Proba}(A \text{ et } B) = \text{Proba}(A) \times \text{Proba}(B)$ [4].
2. On a toujours $\text{Proba}(A \text{ ou } B) \leq \text{Proba}(A) + \text{Proba}(B)$ [5].

Il s’avère plus facile de majorer la probabilité qu’un tournoi ne soit pas $2$-indécis. Pour cela, nous allons procéder par étapes successives.

• Fixons trois joueurs différents. La probabilité que le troisième batte chacun des deux premiers vaut $\frac12 \times \frac12 = \frac14$. La probabilité que le troisième joueur ne batte pas les deux premiers vaut donc $\frac34$.
• La règle 1 ci-dessus implique \[\text{Proba}\left(\text{Aucun des } n-2 \text{ autres joueurs ne bat deux joueurs fixés}\right) = \left( \frac34 \right)^{n-2}\]
• Considérons deux paires de joueurs, pas forcément disjointes. La règle 2 implique que \[\text{Proba}\left(\text{Au moins l'une des deux paires n'a pas été battue par le même joueur}\right) \leq 2 \left( \frac34 \right)^{n-2}\]
• Pour $3$ paires de joueurs, la probabilité ci-dessus est majorée par $3 \left( \frac34 \right)^{n-2}$, et ainsi de suite. Le nombre total de paires de joueurs est égale au nombre de matchs, soit $\frac{n(n-1)}{2}$. Nous concluons que \[\text{Proba}\left( \text{Au moins un groupe de }2\text{ joueurs n'a pas été battu par le même joueur} \right) \leq \frac{n(n-1)}{2} \left( \frac34 \right)^{n-2}\]

Cette dernière probabilité est précisément celle que le tournoi ne soit pas $2$-indécis. Nous avons donc montré que
\[ \text{Proba} \left( \text{Un tournoi à }n\text{ joueurs est }2\text{-indécis} \right) \geq 1 - \frac{n(n-1)}{2} \left( \frac34 \right)^{n-2} \]
Le graphe ci-dessous représente cette valeur pour différents $n$. Pour $n\leq20$, la valeur est négative, donc notre borne inférieure ne nous apprend rien. En revanche, pour $n=21$, on obtient une valeur positive de $0.112$. Les $n$ suivants conduisent à des valeurs encore plus grandes.

En appliquant l’observation d’Erdős, nous obtenons donc le résultat suivant.

Le fait de majorer des probabilités d’événements du type « $A$ ou $B$ » par la somme de leurs probabilités peut sembler une approximation grossière. Ce qui nous sauve, c’est que pour des $n$ grands, la décroissance du facteur $(3/4)^{n-2}$ l’emporte sur la croissance du facteur $n(n-1)/2$.

En conséquence de l’approximation, le théorème fournit uniquement une condition suffisante à l’existence d’un tournoi $2$-indécis, mais on n’affirme pas que cette condition est nécessaire. Il se pourrait qu’il existe des tournois $2$-indécis de moins de $21$ joueurs.

Simulations de Monte-Carlo

Une limitation de la méthode probabiliste est que si elle permet de montrer l’existence d’un tournoi $2$-indécis, elle ne permet pas de construire un tel tournoi. On dit que c’est une méthode non constructive.

Ceci dit, on peut tirer parti d’une autre méthode basée sur des probabilités, qu’il convient de distinguer de l’approche d’Erdős, et qu’on appelle la méthode de Monte-Carlo. Puisque pour $21$ joueurs, un tournoi tiré au hasard a une probabilité d’au moins $11\%$ d’être $2$-indécis, il suffit de programmer son ordinateur pour générer des tournois au hasard. Avec un peu de chance, on finira bien par tomber sur un tournoi $2$-indécis.

En fait, cette approche ne nous limite pas aux $n$ plus grands que $21$. N’oublions pas que la valeur trouvée ci-dessus n’est qu’une borne inférieure à la probabilité cherchée, qui peut être considérablement plus grande.

J’ai donc demandé à mon ordinateur de faire une suite de simulations Monte-Carlo,
en diminuant progressivement le nombre de joueurs. Les plus petits tournois $2$-indécis qu’il a trouvés sont des tournois de $7$ joueurs. En voici un :

On pourra vérifier qu’effectivement il existe, pour chaque paire de joueurs, un autre joueur les ayant battus tous les deux. Par exemple, les joueurs 1 et 2 ont été battus par le joueur 5, alors que 1 et 5 ont tous deux été battus par 4.

Voici une autre représentation du tournoi, sous forme de tableau. Une case bleue signifie que le joueur de la ligne correspondante a battu le joueur de la colonne, une case rouge signifie qu’il a été battu. À nouveau, on vérifie facilement que pour chaque paire de colonnes, il existe au moins une ligne ayant des cases bleues dans ces deux colonnes.

Erdős montre dans l’article [E4] qu’il n’existe pas de tournois $2$-indécis avec moins de $7$ joueurs. C’est une preuve par récurrence, qui n’utilise pas de tout d’argument probabiliste comme le résultat d’existence, et je la trouve bien moins transparente. Peut-être qu’une lectrice astucieuse ou un lecteur astucieux saura en fournir une preuve plus élégante ?

Tournois $k$-indécis

Il existe une généralisation naturelle de la notion de tournoi $2$-indécis.

Existe-t-il des tournois $k$-indécis pour $k>2$ ? La réponse est oui. Pour le montrer, il suffit de généraliser le raisonnement fait pour $k=2$. On trouve assez facilement
\[ \text{Proba} \left( \text{Un tournoi à }n\text{ joueurs est }k\text{-indécis} \right) \geq 1 - \frac{n(n-1)\dots(n-k+1)}{k(k-1)\dots1} \left( 1 - \frac{1}{2^k} \right)^{n-k} \]
La fraction dans cette expression est le coefficient binomial $\binom{n}{k}$, qui donne le nombre de manières de choisir $k$ joueurs parmi $n$. Le terme $1-\frac{1}{2^k}$ est la probabilité qu’un même joueur ne batte pas tous les joueurs d’un groupe de $k$ joueurs. On peut montrer que l’expression de droite tend vers $1$ lorsque $n$ tend vers l’infini et que $k$ est fixé (la décroissance du terme à la puissance $n-k$ l’emporte sur la croissance du terme polynomial en $n$). Autrement dit, l’abondance de joueurs pouvant battre ceux d’un groupe donné l’emporte sur l’abondance des groupes.

En conclusion, nous avons montré le résultat suivant.

Lorsque $k=3$, on trouve que $n=91$ convient. Mais il ne s’agit à nouveau que d’une borne supérieure. Le plus petit tournoi $3$-indécis que mon ordinateur a trouvé à l’aide de simulations Monte-Carlo comporte $60$ joueurs. Le voici :

Pour chaque choix de $3$ colonnes, il doit y avoir au moins une ligne ayant des cases bleues dans ces $3$ colonnes (c’est en tous cas ce qu’affirme mon ordinateur, je n’ai pas vérifié).
J’ignore s’il existe des tournois $3$-indécis à moins de $60$ joueurs — avis aux amateurs ! [6]

Pour des $k$ plus grands que $3$, les simulations deviennent vite impraticables. D’où l’intérêt du théorème ci-dessus, qui marche pour n’importe quel $k$. En utilisant la formule de Stirling, on peut montrer que pour $k$ grand, le nombre de joueurs garantissant l’existence d’un tournoi $k$-indécis est d’ordre $\ln(2)k^22^k$.

Pour terminer

En résumé, la méthode probabiliste fonctionne de la manière suivante. On cherche à montrer que parmi une collection d’objets mathématiques (par exemple des graphes ou des nombres), il en existe au moins un ayant une certaine propriété. On attribue alors une probabilité à chacun des objets de la collection, qui peut être la même pour tous ou pas. Si l’on arrive à montrer que la propriété cherchée a une probabilité positive, alors on a gagné. Pour pouvoir minorer cette probabilité, il est utile d’avoir à sa disposition des événements indépendants. C’est le cas dans notre exemple des tournois, où les différents matchs sont considérés comme indépendants, et font office de « briques élémentaires » de l’espace probabilisé. [7]

Insistons sur le fait que malgré l’utilisation de probabilités, la méthode donne des résultats certains.

Il existe toute une série de généralisations de cette méthode, pouvant fournir des résultats plus quantitatifs. Par exemple, on peut se baser sur l’observation élémentaire suivante.

La moyenne d’un ensemble de nombres réels ne peut pas être strictement inférieure à tous ces nombres. Elle ne peut pas non plus leur être strictement supérieure.

En probabilités, les moyennes s’appellent des espérances, et on sait souvent bien les approcher. On trouve un exemple d’application de cette idée en mathématiques financières. Un modèle simpl(ist)e dans ce domaine s’appelle le modèle binomial. L’investisseur y a la possibilité d’investir soit dans un compte d’épargne à taux fixé, soit dans une action, dont la valeur le lendemain peut prendre deux valeurs, l’une plus grande et l’autre plus petite que ce que donne le compte d’épargne. Afin d’établir une stratégie d’investissement, on introduit la probabilité de risque neutre. Celle-ci donne aux deux valeurs possibles de l’action des probabilités telles que son espérance soit égale à la valeur du compte d’épargne, ce qui simplifie énormément les calculs.

D’autres généralisations quantitatives de la méthode probabiliste reposent sur des inégalités telles que l’inégalité de Bienaymé-Tchebychev. On trouvera des exemples aux endroits suivants :

• Dans le chapitre 12 de ces notes de cours d’Yvan Velenik.
• Dans le livre Proofs from the Book de M. Aigner et G. Ziegler, traduit en français sous le titre Raisonnements divins (Springer), plus particulièrement dans le chapitre Les probabilités facilitent (parfois) le dénombrement.
• Dans l’article La méthode probabiliste de Marie Heyvaert et F. Thomas Bruss, paru dans la Gazette des Mathématiciens - n°124, Avril 2010.
• Les lecteurs souhaitant approfondir le sujet pourront consulter l’ouvrage [AS].

Bibliographie

Paul Erdős a utilisé sa méthode probabiliste pour la première fois dans l’article [E1], même s’il n’y fait pas explicitement référence au langage des probabilités. On trouve de telles références dans les articles [E2] et [E3]. Le problème des tournois est considéré dans l’article [E4], et des généralisations se trouvent dans [EM].

[AS]
N. Alon, J. Spencer, The probabilistic method (3ème édition). New York : Wiley-Interscience, (2008).

[E1]
P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294.

[E2]
P. Erdős,
On additive arithmetical functions and applications of probability to number theory. Proceedings of the International Congress of Mathematicians, 1954, Amsterdam, vol. III, pp. 13–19. Erven P. Noordhoff N. V., Groningen ; North-Holland Publishing Co., Amsterdam (1956).

[E3]
P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.

[E4]
P. Erdős, On a problem in graph theory,
Math. Gaz. 47 (1963), 220-223.

[EM]
P. Erdős, L. Moser A problem on tournaments, Canad. Math. Bull. 7 (1964), 351-356