Méthode probabiliste

La méthode probabiliste est une méthode nonconstructive, essentiellement utilisés dans la combinatoire et lancé par Paul Erdös, pour démontrer l'existence d'un certain type d'objet mathématique.



Catégories :

Analyse combinatoire - Probabilités

Page(s) en rapport avec ce sujet :

  • graphes. Nous travaillons ici avec la définition suivante de graphe. Définition.... Quel est le nombre minimal m d'arrêtes d'un d-hypergraphe... L'observation majeure au cœur de la méthode probabiliste est donnée par le lemme suivant.... Si la probabilité qu'un objet tiré au hasard n'ait pas une certaine pro-... (source : math.ubc)
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 nonconstructive, essentiellement utilisés dans la combinatoire et lancé par Paul Erdös, pour démontrer l'existence d'un certain type d'objet mathématique. Cette méthode a été appliquée à d'autres domaines de mathématiques tels que la théorie des nombres, l'algèbre linéaire et analyse réelle. Il travaille en montrant que si 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. Quoique la démonstration utilise la probabilité, la conclusion finale est déterminée pour certains, sans aucune erreur envisageable.

Introduction

Si chaque objet dans une collection d'objets ne parvient pas à avoir une certaine propriété, alors la probabilité qu'un objet choisi au hasard à partir de la collection a cette propriété est zéro. S'agissant de ce gaz, si la probabilité que l'objet au hasard a la propriété est supérieure à zéro, cela démontre l'existence d'au moins un objet dans la collection qui a la propriété. Il n'a pas d'importance si la probabilité est extrêmement faible; toute probabilité positive est acceptable.

De même, ce qui montre que la probabilité est (strictement) moins de 1 est parfois utilisé pour démontrer l'existence d'un objet qui ne satisfait pas les propriétés.

Une autre façon d'utiliser la méthode probabiliste est par le calcul de l'espérance de certaine variable aléatoire. S'il peut être démontré que la variable aléatoire peut prendre une valeur inférieure à l'espérance, cela démontre que la variable aléatoire peut aussi prendre sur une valeur supérieure à l'espérance.

Certains outils sont souvent 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[1], la majorité 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 envisageable 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 :

2 \cdot 2ˆ{-{r \choose 2}}

(le facteur 2 provient de ce qu'il y a deux couleurs envisageables).

Cela est vrai pour l'une des C (n, r) sous-ensembles nous aurions pu choisir, nous avons par conséquent que la somme de 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 (indépendamment du fait que les variables sont indépendants), de sorte que l'espérance de la somme (l'attendu nombre 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, par conséquent il doit être inférieur à l'espérance, pour au moins un des colorations. Mais l'unique entier qui satisfait à ce critère est de 0. Ainsi, si

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

puis certains colorations répond à notre critère désirée, par conséquent par définition, R (r, r; 2) doit être plus grande que n. Surtout, R (r, r; 2) doit augmenter au moins exponentielle avec r.

Une particularité de cet argument est qu'il est entièrement nonconstructive. Même s'il démontre (par exemple) que presque l'ensemble des colorations de la graphe complet sur (1.1) r sommets ne contient 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 a été ouvert à plus de 50 ans.

Deuxième exemple

Un document 1959 par Erdös (voir références citées ci-dessous) a abordé le problème en suivant dans la théorie des graphes : étant donné entiers g et k, existe-t-il un graphe G contenant cycles de longueur au plus g, tels que le nombre chromatique de G est au moins k?

Il peut être démontré que ce type de graphe existe pour tout g et k, et la démonstation est assez simple. Soit n particulièrement grand et envisager un random graph G sur n sommets, où chaque arête dans G existe avec une probabilité n (1-g) /g. Il peut être démontré que, avec probabilité positive, les deux déclarations suivantes sont vraies :

Voici l'astuce : depuis 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. Nous pouvons voir que cet nouveau graphe n'a pas un stable de taille \lceil n'/k \rceil, par conséquent G' a nombre chromatique au moins k.

Ce résultat donne une indication sur les raisons pour lesquelles le calcul du nombre chromatique d'un graphe est si complexe : même lorsqu'il n'y a pas de raisons locales (telles que les petits cycles) d'un graphe d'exiger énormément de couleurs le nombre chromatique peut être arbitrairement grande.

Notes

  1. Ainsi, Szele's a montré en 1943 qu'il existe des tournois contenant la plupart de cycles hamiltoniens.

Voir aussi

Références

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/M%C3%A9thode_probabiliste.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu