Voir la source de Méthode probabiliste

{{Voir homonymie|Probabilité (homonymie)}}
{{Ébauche|mathématiques}}
{{confusion|texte=Cet article ne concerne ni les [[Système de preuve interactive|systèmes de preuve interactive]] qui sont utilisés pour convaincre un vérificateur qu'une démonstration est correcte, ni les [[Algorithme probabiliste|algorithmes probabilistes]], qui font entrer des probabilités dans la qualité de la réponse donnée par un algorithme, ni enfin les [[Méthode de Monte-Carlo|méthodes de Monte-Carlo]].}}

La '''méthode probabiliste''' est une méthode [[Démonstration constructive|non constructive]], initialement utilisée en [[combinatoire]] et popularisé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 prend 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 pris 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 mathématique|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]].

== 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<ref>Ainsi, [[Tibor Szele]] a montré en 1943 qu'il existe des [[Tournoi (graphe)|tournois]] contenant un grand nombre de [[Graphe hamiltonien|cycles hamiltoniens]].</ref>, la plupart des démonstrations utilisant cette méthode sont à mettre au crédit d'Erdős<ref>{{lien web|url=http://images.math.cnrs.fr/Probabiliser.html|titre=Probabiliser|site=[[Images des maths]]|auteur=Nils Berglund|date=10 mai 2015}}</ref>. Le premier exemple publié en 1947 donne une démonstration d'une limite inférieure pour le [[Théorie de Ramsey|nombre de Ramsey]] ''R''(''r'', ''r''; 2).

=== Premier exemple ===
{{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'', [[Espérance mathématique|l'espérance]] de ''X''(''S'') est la probabilité que toutes les <math>{r \choose 2}</math> arêtes de ''S'' soient de même couleur,

:<math>2 \cdot 2^{-{r \choose 2}}</math>

(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

:<math>{n \choose r}2^{1-{r \choose 2}}.</math>

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

:<math>{n \choose r}2^{1-{r \choose 2}}.</math>

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

:<math>C(n,r) < 2^{{r \choose 2} - 1}</math>,

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 [[Croissance exponentielle|augmenter au moins exponentiellement]] avec ''r''.

Une particularité de cet argument est qu'il est entièrement [[Démonstration constructive|non constructif]]. Même s'il démontre (par exemple) que presque toutes les colorations du graphe complet sur ''(1.1)<sup>r</sup>'' 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<ref>{{en}} [[Paul Erdős]], ''Graph theory and probability'', Canad. J. Math. '''11''' (1959), 34–38</ref> 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 [[Coloration de graphe|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''<sup>(1-''g'')/''g''</sup>. On peut démontrer que, avec probabilité positive, les deux assertions suivantes sont vraies :

* ''G'' ne contient aucun [[Stable (théorie des graphes)|stable]] de taille <math>\lceil n/2k \rceil</math>
* ''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 <math>\lceil n'/k \rceil</math>, donc le [[Coloration de graphe|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.

== Autres applications ==

La méthode probabiliste est utilisée dans de nombreux cadres. Par exemple : 
* pour des problèmes d'ensembles, comme le [[théorème d'Erdős-Ko-Rado]]
* en [[théorie des nombres]], comme le [[théorème d'Erdős-Kac]]
* en [[théorie des graphes extrémaux]], comme le [[théorème de Turán]]
* en géométrie, pour dénombrer des triangles<ref>{{lien web|url=http://www.unige.ch/math/folks/velenik/papers/LN-PS.pdf|titre=Probabilités et statistiques : La méthode probabiliste (p. 227)|auteur=Yvan Velenik | date=2012|site=Université de Genève}}.</ref>. 

== Notes et références ==
<references />

== Bibliographie ==
{{Traduction/Référence|en|Probabilistic method|287019670}}
* {{en}} [[Noga Alon]] et [[Joel Spencer]], ''The probabilistic method'' (2ed). New York: Wiley-Interscience, 2000 {{ISBN|0-471-37046-0}}
* {{en}} [[Jiří Matoušek]] et Jan Vondrak, ''The probabilistic method'', notes de cours, [http://kam.mff.cuni.cz/~matousek/prob-ln-2pp.ps.gz en format .ps.gz]
* {{en}} Noga Alon et Michael Krivelevich, ''Extremal and Probabilistic Combinatorics'' in ''[[The Princeton Companion to Mathematics]]'', W. T. Gowers, Ed., Princeton University Press 2008, p. 562-575 {{lire en ligne|url=http://www.math.tau.ac.il/~nogaa/PDFS/epc7.pdf}}{{pdf}}

== Voir aussi ==
=== Article connexe ===
{{Lien|trad=Probabilistic proofs of non-probabilistic theorems|langue=en|fr=Preuves probabilistes de théorèmes non probabilistes}}

{{portail|mathématiques|statistiques}}

{{DEFAULTSORT:Methode probabiliste}}
[[Catégorie:Combinatoire]]
[[Catégorie:Probabilités]]