Probabiliser

Piste rouge 10 mai 2015  - Ecrit par  Nils Berglund Voir les commentaires (1)

Cet article fait suite aux articles Algébriser et Géométriser de Patrick Popescu-Pampu parus dans cette rubrique. On illustre comment résoudre un problème avec la méthode probabiliste, en montrant l’existence de tournois « indécis », dans lesquels tout groupe de joueurs de taille donnée est battu par un autre joueur.

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 . 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 ?

Définition : On dira que le tournoi est $2$-indécis si pour chaque paire de joueurs, il existe un troisième joueur ayant battu chacun de ces deux joueurs.

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
[
\fracn(n-1)2
\qquad
\textmatchs.
]
Comme chaque match a deux issues possibles, cela nous fait un total de
[
2^n(n-1)/2
\qquad
\texttournois à 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.

Théorème : Il existe des tournois $2$-indécis dès que le nombre de joueurs est au moins égal à $21$.

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.

Définition : Soit $k$ un entier strictement positif. Un tournoi est $k$-indécis si pour chaque groupe de $k$ joueurs, il existe un joueur (n’appartenant pas à ce groupe) ayant battu chacun des joueurs de ce groupe.

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.

Théorème : Pour tout $k\geq1$, il existe des tournois $k$-indécis dès que le nombre $n$ de joueurs est assez grand. Plus précisément, de tels tournois existent dès que \[ \frac{n(n-1)\dots(n-k+1)}{k(k-1)\dots1} \left( 1 - \frac{1}{2^k} \right)^{n-k} < 1 \]

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 :

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

Post-scriptum :

Merci aux relecteurs Laurence Broze, TheBarber, Thierry Barbot et Maxime Bourrigan pour leurs critiques constructives, et à Patrick Popescu-Pampu pour l’invitation et les conseils avisés.

Article édité par Patrick Popescu-Pampu

Notes

[1La lectrice ou le lecteur pourra bien entendu remplacer ces prénoms par ceux qu’elle ou il souhaite. Il semblerait, et on peut le regretter, que la notoriété des champions de tennis soit plus importante que celle des championnes. Mais, tout comme en mathématiques, cette situation peut évoluer.

[2Si $n=14$, le nombre de tournois possibles vaut $2^{91}$, ce qui dépasse le nombre d’Avogadro, dont l’ordre de grandeur est décrit ici.

[3Si l’univers est un ensemble non dénombrable, il devient nécessaire de spécifier l’ensemble des événements qu’on considère en même temps que l’espace probabilisé. On appelle cet ensemble une tribu. Mais nous pourrons nous passer de cette notion ici.

[4Comment, me direz-vous, sait-on si $A$ et $B$ sont indépendants ? En fait, on définit l’indépendance de $A$ et $B$ par la condition $\text{Proba}(A \text{ et } B) = \text{Proba}(A) \times \text{Proba}(B)$. Mais il se trouve que dans de nombreuses situations, il existe des événements qui sont indépendants de manière évidente. Dans notre cas, deux événements sont indépendants dès qu’ils ne font pas intervenir de matchs communs.

[5L’égalité $\text{Proba}(A \text{ ou } B) = \text{Proba}(A) + \text{Proba}(B)$ a lieu si et seulement si $\text{Proba}(A \text{ et } B)=0$, on dit alors que $A$ et $B$ sont incompatibles. Sinon, on a $\text{Proba}(A \text{ ou } B) = \text{Proba}(A) + \text{Proba}(B) - \text{Proba}(A \text{ et } B)$.

[6Dans l’article [E4], Erdős montre qu’il n’y a pas de tournoi $k$-indécis de moins de $2^{k+1}-1$ joueurs. Un tournoi $3$-indécis a donc nécessairement au moins $2^4-1=15$ joueurs, mais cela laisse beaucoup de marge par rapport aux $60$ joueurs fournis par la simulation.

[7Dans l’exemple des tournois, nous avons construit l’espace probabilisé en attribuant la même probabilité à tous les tournois. Une autre manière de faire, qui conduit au même résultat, est de partir d’un petit espace probabilisé décrivant un seul match, et d’augmenter petit à petit l’espace en ajoutant les différents matchs un par un. Si l’on veut que tous les matchs soient indépendants et équitables, on aboutit automatiquement à des tournois de même probabilité.

Partager cet article

Pour citer cet article :

Nils Berglund — «Probabiliser» — Images des Mathématiques, CNRS, 2015

Commentaire sur l'article

  • Probabiliser

    le 12 mai 2015 à 02:21, par TheBarber

    SPOILER ALERT : Je propose une courte démonstration pour le fait qu’il n’existe pas de tournoi 2-indécis à n joueurs pour n=4,5,6 (pour 3 c’est évident).

    Soit un tournoi 2-indécis à n joueurs. A chaque paire de joueurs A,B on peut associer un joueur f(A,B) qui gagne contre A et contre B. f est une application d’un ensemble à n(n-1)/2 éléments vers un ensemble à n éléments, donc il existe, par le lemme des tiroirs, deux paires différentes battues par le même joueur. Deux paires différentes, ça fait au moins trois joueurs, A, B et C, battus par D.

    Si n=4, D n’est battu par personne, absurde.

    Si n=5, appelons E le dernier joueur. Alors il doit exister un joueur qui bat D et E, ce qui n’est pas possible ni pour A, ni pour B, ni pour C qui ne battent même pas D, absurde.

    Si n=6, appelons E et F les deux autres joueurs. Alors, forcément, F bat D et E, et dans ce cas, personne ne peut battre à la fois D et F : A, B, et C perdent contre D et E perd contre F, absurde.

    J’ai bon ?

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM