Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Méthode probabiliste
Résumé
La méthode probabiliste est une méthode 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.
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 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.
Bien que d'autres avant lui aient démontré des théorèmes en s'appuyant sur la méthode probabiliste, 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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.