Méthode probabiliste

En mathématiques , la méthode probabiliste est une méthode non constructive , principalement utilisée en combinatoire et initiée par Paul Erdős , pour démontrer l'existence d'un type donné d'objet mathématique. Elle consiste à montrer que si l'on choisit aléatoirement des objets parmi une classe spécifiée, la probabilité que le résultat appartienne au type prescrit est strictement supérieure à zéro. Bien que la démonstration repose sur les probabilités, la conclusion finale est établie avec certitude, sans aucune possibilité d'erreur.

Cette méthode a maintenant é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 , ainsi qu'en informatique (par exemple, l'arrondi aléatoire ) et en théorie de l'information .

Si aucun objet d'une collection ne possède une certaine propriété, alors la probabilité qu'un objet choisi au hasard dans la collection possède cette propriété est nulle. Par contraposition , si la probabilité qu'un objet choisi au hasard dans la collection possède cette propriété est non nulle, alors au moins un objet de la collection possède nécessairement cette propriété.

De même, démontrer que la probabilité est (strictement) inférieure à 1 peut être utilisé pour prouver l'existence d'un objet qui ne satisfait pas les propriétés prescrites.

Une autre application de la méthode probabiliste consiste à calculer l' espérance d'une variable aléatoire . Si l'on peut démontrer que cette variable aléatoire peut prendre une valeur inférieure à son espérance, cela prouve qu'elle peut également prendre une valeur supérieure à son espérance.

Par ailleurs, la méthode probabiliste peut également être utilisée pour garantir l'existence d'un élément souhaité dans un espace d'échantillonnage dont la valeur est supérieure ou égale à la valeur attendue calculée, car la non-existence d'un tel élément impliquerait que chaque élément de l'espace d'échantillonnage est inférieur à la valeur attendue, ce qui est contradictoire.

Les outils couramment utilisés dans la méthode probabiliste comprennent l'inégalité de Markov , la borne de Chernoff et le lemme local de Lovász .

Bien que d'autres avant lui aient démontré des théorèmes par la méthode probabiliste (par exemple, le résultat de Szele en 1943 sur l'existence de tournois contenant un grand nombre de cycles hamiltoniens ), nombre des démonstrations les plus célèbres utilisant cette méthode sont dues à Erdős. Le premier exemple ci-dessous décrit un tel résultat de 1947 qui fournit une borne inférieure pour le nombre de Ramsey.

Supposons que nous ayons un graphe complet sur

Pour ce faire, nous colorons le graphe aléatoirement. Chaque arête est colorée indépendamment avec une probabilité

Pour tout ensemble

(le facteur de

Cela est valable pour n'importe lequel des

La somme des espérances est l'espérance de la somme ( que les variables soient indépendantes ou non ), donc l'espérance de la somme (le nombre attendu de tous les monochromatiques)

Considérez ce qui se passe si cette valeur est inférieure à

(ce qui est vrai, par exemple, pour

Par définition du nombre de Ramsey , cela implique que

L'un des points faibles de cet argument est son caractère totalement non constructif . Le problème de la recherche d'une telle coloration reste ouvert depuis plus de 50 ans.

Un article d'Erdős de 1959 (voir référence citée ci-dessous) abordait le problème suivant en théorie des graphes : étant donné des entiers positifs g et k , existe-t-il un graphe G contenant uniquement des cycles de longueur au moins g , tel que le nombre chromatique de G soit au moins k ?

On peut démontrer qu'un tel graphe existe pour tous g et k , et la preuve est relativement simple. Soit n très grand et considérons un graphe aléatoire G à n sommets, où chaque arête de G existe avec une probabilité p = n ^{1/ g −1} . Nous montrons qu'avec une probabilité non nulle, G satisfait les deux propriétés suivantes :

Propriété 1. G contient au plus n /2 cycles de longueur inférieure à g .

Démonstration. Soit X le nombre de cycles de longueur inférieure à g . Le nombre de cycles de longueur i dans le graphe complet à n sommets est :

et chacun d'eux est présent dans G avec une probabilité p i . Par conséquent, d'après l'inégalité de Markov, nous avons

$\{\; frac\; \{n\}\{2\}\}\; ight)\backslash leq\; \{\backslash frac\; \{2\}\{n\}\}E[X]\backslash leq\; \{\backslash frac\; \{1\}\{n\}\}\backslash sum\; \_\{i=3\}^\{g-1\}p^\{i\}n^\{i\}=\{\backslash frac\; \{1\}\{n\}\}\backslash sum\; \_\{i=3\}^\{g-1\}n^\{\backslash frac\; \{i\}\{g\}\}\backslash leq\; \{\backslash frac\; \{g\}\{n\}\}n^\{\backslash frac\; \{g-1\}\{g\}\}=gn^\{-\{\backslash frac\; \{1\}\{g\}\}\}=o(1).Pr\left(X>\frac{n}{2}\right)\le \frac{2}{n}E\left[X\right]\le \frac{1}{n}\sum _{\mathrm{je}=3}^{g-1}{p}^{\mathrm{je}}{n}^{\mathrm{je}}=\frac{1}{n}\sum _{\mathrm{je}=3}^{g-1}{n}^{\frac{\mathrm{je}}{g}}\le \frac{g}{n}{n}^{\frac{g-1}{g}}=g{n}^{-\frac{1}{g}}=o\left(1\right).${ frac {n}{2}} ight)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).

Ainsi, pour n suffisamment grand , la propriété 1 est vérifiée avec une probabilité supérieure à 1/2 .

Propriété 2. G ne contient aucun ensemble indépendant de taille

Démonstration. Soit Y la taille du plus grand ensemble indépendant de G. Clairement, nous avons

quand

n suffisamment grand , la propriété 2 est vérifiée avec une probabilité supérieure à 1/2 .

Pour n suffisamment grand , la probabilité qu'un graphe de la distribution possède les deux propriétés est positive, car les événements pour ces propriétés ne peuvent pas être disjoints (s'ils l'étaient, leurs probabilités totaliseraient plus de 1).

Voici l'astuce : puisque G possède ces deux propriétés, on peut supprimer au plus n /2 sommets de G pour obtenir un nouveau graphe G′ surg . On peut voir que ce nouveau graphe ne possède pas d'ensemble indépendant de tailleG′ ne peut être partitionné qu’en au moins k ensembles indépendants et, par conséquent, a un nombre chromatique d’au moins k .

Ce résultat donne un indice sur la raison pour laquelle le calcul du nombre chromatique d'un graphe est si difficile : même lorsqu'il n'y a pas de raisons locales (telles que de petits cycles) pour qu'un graphe nécessite de nombreuses couleurs, le nombre chromatique peut encore être arbitrairement grand.