En théorie des probabilités, l’inégalité de Hoeffding est une inégalité de concentration concernant les sommes de variables aléatoires indépendantes et bornées. Elle tire son nom du mathématicien et statisticien finlandais Wassily Hoeffding. Il existe une version plus générale de cette inégalité, concernant une somme d'accroissements de martingales, accroissements là encore bornés : cette version plus générale est parfois connue sous le nom d'inégalité d'Azuma-Hoeffding.
Dans cette section, nous allons comparer l'inégalité de Hoeffding et l'inégalité de Bienaymé-Tchebychev dans le cas de la loi binomiale. Supposons que pour tout k entre 1 et n, on ait
Alors représente le nombre de piles obtenus à un jeu de pile ou face avec n lancers et où p est la probabilité d'avoir pile sur un lancer. suit la loi binomiale de paramètres n et p. Nous avons les inégalités suivantes, pour tout :
L'inégalité de Bienaymé-Tchebychev donne :
L'inégalité de Hoeffding donne .
On voit que dans ce cas (et c'est assez représentatif de la situation générale) l'inégalité de Hoeffding est beaucoup plus précise pour suffisamment grand.
La démonstration fait usage de la proposition suivante :
D'abord, on peut supposer c < 0 et d > 0. En effet, si , alors Y est une variable aléatoire presque-sûrement positive d'espérance nulle, donc Y=0 presque-sûrement et la proposition est évidente ; le raisonnement est analogue pour Par convexité de la fonction on a, pour
En passant à l'espérance, puisque on en déduit que
On pose
Puisque c < 0 et d > 0, on a bien d'où la pertinence de la notation. Il suit que
On remarque alors que
De plus
Alors, en vertu de la formule de Taylor-Lagrange à l'ordre 1,
On applique ensuite l'inégalité de Markov. Pour cela, on pose:
et on remarque que
Pour tout on a donc, en vertu d'un corollaire de l'inégalité de Markov, de l'indépendance des et donc des et de la proposition précédente :
L'inégalité est en particulier vraie pour
qui réalise le minimum de la borne de droite, ce qui démontre la première inégalité.
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.
L'inégalité de Bennett est une inégalité de concentration donnant une majoration de la fonction génératrice des cumulants de la somme de variables indépendantes majorées centrées et majore en conséquence la probabilité que cette somme dévie avec une quantité donnée. Cette inégalité a été démontrée en 1962 par George Bennett de l'université de Nouvelle-Galles du Sud. Soient des variables aléatoires indépendantes (non nécessairement de même loi) de variance finie et tels que presque-sûrement pour tout et .
Dans la théorie des probabilités, les inégalités de concentration fournissent des bornes sur la probabilité qu'une variable aléatoire dévie d'une certaine valeur (généralement l'espérance de cette variable aléatoire). Par exemple, la loi des grands nombres établit qu'une moyenne de variables aléatoires i.i.d. est, sous réserve de vérifier certaines conditions, proche de leur espérance commune. Certains résultats récents vont plus loin, en montrant que ce comportement est également vérifié par d'autres fonctions de variables aléatoires indépendantes.
Explore l'inégalité de Hoeffding et la distribution binomiale, en mettant l'accent sur la minimisation des erreurs et les lacunes de généralisation dans la sélection des prédicteurs.
Plonge dans la théorie des probabilités avancées, couvrant les inégalités, les essais, les distributions et les calculs pour les probabilités et les attentes.
In this paper, we study the compression of a target two-layer neural network with N nodes into a compressed network with M < N nodes. More precisely, we consider the setting in which the weights of the target network are i.i.d. sub-Gaussian, and we minimiz ...
The lack of detection to date of electromagnetic technosignatures implies either that we have been unable to detect them due to incomplete sampling of the search space or that we cannot detect them because the Earth has been located during the entire histo ...
PERGAMON-ELSEVIER SCIENCE LTD2023
,
We derive confidence intervals (CIs) and confidence sequences (CSs) for the classical problem of estimating a bounded mean. Our approach generalizes and improves on the celebrated Chernoff method, yielding the best closed-form "empirical-Bernstein" CSs and ...