Méthode probabiliste

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Probabilité (homonymie).
Page d'aide sur l'homonymie Cet article ne concerne ni les systèmes de preuve interactive qui sont utilisés pour convaincre un vérificateur qu'une démonstration est correcte, ni les algorithmes probabilistes, qui donnent la bonne réponse avec une grande probabilité, mais pas avec certitude, ni enfin les méthodes de Monte-Carlo.

La méthode probabiliste est une méthode non constructive, initialement utilisée en 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[modifier | modifier le code]

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 qu'elle 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[modifier | modifier le code]

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[modifier | modifier le code]

Article connexe : Théorie de Ramsey.

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[modifier | modifier le code]

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émonstration 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[modifier | modifier le code]

Notes[modifier | modifier le code]

  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[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Preuves probabilistes de théorèmes non probabilistes (en)