Méthode probabiliste

Cet article n'est pas sur les systèmes de preuve interactive qui sont utilisés pour convaincre un vérificateur qu'une démonstration est correcte, ni sur les algorithmes probabilistes, qui donnent la bonne réponse avec une grande probabilité, mais pas avec certitude, ni sur les méthodes de Monte-Carlo.

La méthode probabiliste est une méthode non constructive, initialement utilisée combinatoire et lancée par Paul Erdős, pour démontrer l'existence d'un type donné d'objet mathématique. Cette méthode a été appliquée à d'autres domaines des mathématiques tels que la théorie des nombres, l'algèbre linéaire et l'analyse réelle. Son principe est de montrer que si l'on choisit au hasard des objets d'une catégorie, la probabilité que le résultat soit d'un certain type est plus que zéro. Bien que la démonstration utilise la théorie des probabilités, la conclusion finale est déterminée de façon certaine.

Introduction

Si dans une collection aucun objet ne possède une certaine propriété, alors la probabilité qu'un objet choisi au hasard dans la collection ait cette propriété est nulle. Dit autrement : si la probabilité qu'un objet au hasard ait la propriété est non nulle, cela démontre l'existence d'au moins un objet dans la collection qui a la propriété. Peu importe que la probabilité soit extrêmement faible, il suffit quelle soit strictement positive.

De même, montrer que la probabilité est strictement inférieure à 1 permet de démontrer l'existence d'un objet qui ne satisfait pas la propriété.

Une autre façon d'utiliser la méthode probabiliste est de calculer l'espérance d'une certaine variable aléatoire. Si l'on arrive à démontrer que la variable aléatoire peut prendre une valeur strictement inférieure à l'espérance, cela prouve qu'elle peut également prendre une valeur strictement supérieure à l'espérance.

Certains outils fréquemment utilisés dans la méthode probabiliste sont l'inégalité de Markov, l'inégalité de Chernoff, et le lemme local de Lovász (en).

Deux exemples dus à Erdős

Bien que d'autres avant lui aient démontré des théorèmes en s'appuyant sur la méthode probabiliste^[1], la plupart des démonstrations utilisant cette méthode sont à mettre au crédit d'Erdős. Le premier exemple publié en 1947 donne une démonstration d'une limite inférieure pour le nombre de Ramsey R(r, r; 2).

Premier exemple

Supposons que nous ayons un graphe complet sur n sommets et que nous voulions démontrer (pour les valeurs assez petites de n) qu'il est possible de colorer les arêtes du graphe en deux couleurs (par exemple rouge et bleu), de sorte qu'il n'y ait pas de sous-graphe complet sur r sommets qui soit monochromatique (toutes les arêtes de même couleur).

Pour ce faire, colorions le graphe de façon aléatoire, c'est-à-dire colorions chaque arête de façon indépendante, avec probabilité ½ d'être rouge et ½ d'être bleu. Calculons le nombre de sous-graphes monochromatiques sur r sommets comme suit :

• Pour tout ensemble S de r sommets de notre graphe, affectons à la variable X(S) la valeur 1 si toutes les arêtes entre les r sommets sont de la même couleur et la valeur 0 autrement. Notons que le nombre de r-sous-graphes monochromatiques est la somme des X(S) quand S parcourt tous les sous-ensembles. Pour tout S, l'espérance de X(S) est la probabilité que toutes les ${r \choose 2}$ arêtes de S soient de même couleur,

$2 \cdot 2^{-{r \choose 2}}$

(le facteur 2 provient de ce qu'il y a deux couleurs possibles), et ce, pour chacun des C(n, r) sous-ensembles que l'on peut choisir, si bien que la somme des E[X(S)] sur tous S est

${n \choose r}2^{1-{r \choose 2}}.$

La somme de l'espérance est l'espérance de la somme (même si les variables ne sont pas indépendantes), de sorte que l'espérance de la somme (le nombre moyen de r-sous-graphes monochromatiques) est

${n \choose r}2^{1-{r \choose 2}}.$

Pensez à ce qui se passe si cette valeur est inférieure à 1. Le nombre de r-sous-graphes monochromatiques dans notre coloration aléatoire sera toujours un entier, donc il doit être inférieur à l'espérance, pour au moins un des colorations. Mais le seul entier qui satisfait à ce critère est de 0. Ainsi, si

$C(n,r) < 2^{{r \choose 2} - 1}$,

alors l'une des colorations répond au critère désiré, donc par définition, R(r, r; 2) doit être supérieur à n. En particulier, R(r, r; 2) doit augmenter au moins exponentiellement avec r.

Une particularité de cet argument est qu'il est entièrement non constructif. Même s'il démontre (par exemple) que presque toutes les colorations du graphe complet sur (1.1)^r sommets ne contiennent pas de r-sous-graphe monochromatique, il ne donne pas d'exemple explicite d'une telle coloration. Le problème de trouver une telle coloration est ouvert depuis plus de 50 ans.

Deuxième exemple

Un article d'Erdős de 1959^[2] a abordé le problème suivant de théorie des graphes : étant donnés deux entiers g et k, existe-t-il un graphe G ne contenant que des cycles de longueur au plus g, tel que le nombre chromatique de G soit au moins k ?

On peut démontrer que ce type de graphe existe pour tous g et k, et la démonstation est relativement simple. Soit n très grand et envisageons un graphe aléatoire G sur n sommets, où chaque arête dans G existe avec une probabilité n^(1-g)/g. On peut démontrer que, avec probabilité positive, les deux assertions suivantes sont vraies :

• G ne contient aucun stable de taille $\lceil n/2k \rceil$
• G contient au plus n/2 cycles de longueur au plus g.

Voici ensuite l'astuce : puisque G a ces deux propriétés, on peut supprimer au plus n/2 sommets de G pour obtenir un nouveau graphe G' sur n' sommets qui ne contient pas de cycles de longueur au plus g. On voit que ce nouveau graphe n'a pas un stable de taille $\lceil n'/k \rceil$, donc le nombre chromatique de G' vaut au moins k.

Ce résultat donne une indication sur les raisons pour lesquelles le calcul du nombre chromatique d'un graphe est si difficile : même quand un graphe n'a pas de raisons locales (telles que des petits cycles) pour nécessiter beaucoup de couleurs, son nombre chromatique peut être arbitrairement grand.

Notes et références

Notes

1. ↑ Ainsi, Tibor Szele (en) a montré en 1943 qu'il existe des tournois (en) contenant un grand nombre de cycles hamiltoniens.
2. ↑ (en) Paul Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34–38

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Probabilistic method » (voir la liste des auteurs)
• (en) Noga Alon (en) et Joel Spencer (en), The probabilistic method (2ed). New York: Wiley-Interscience, 2000 (ISBN 0-471-37046-0)
• (en) Jiří Matoušek (de) et Jan Vondrak, The probabilistic method, notes de cours, en format .ps.gz
• (en) Noga Alon et Michael Krivelevich, Extremal and Probabilistic Combinatorics in Princeton Companion to Mathematics, W. T. Gowers, Ed., Princeton University Press 2008, p. 562-575 [lire en ligne][PDF]