Soit [formule] des v.a. i.i.d. de loi de Bernoulli [formule] avec [formule]. En utilisant l'inégalité de Hoeffding, montrer que [formule]. Application : combien de lancers faut-il pour estimer [formule] à 0,01 près avec confiance 95% ?
Hoeffding : si [formule], alors [formule].
L'application de la formule est mécanique. Ce que l'exercice permet de comprendre, c'est ce qu'on achète en payant [formule] lancers plutôt que [formule] : une garantie valable pour tout [formule], au lieu d'une approximation asymptotique. La comparaison chiffrée des trois outils disponibles est l'objet de la seconde moitié. Rappel — inégalité de Hoeffding. Si [formule] sont indépendantes avec [formule] presque sûrement, alors pour tout [formule] L'hypothèse est la bornitude, pas la normalité ni même l'existence de moments d'ordre supérieur — c'est ce qui en fait un outil si général. Application aux Bernoulli. Chaque [formule] vit dans [formule], donc [formule] et [formule]. L'inégalité devient [formule] Noter que [formule] a disparu de la borne : elle est uniforme en [formule], ce qui est précisément ce qu'il faut quand [formule] est le paramètre inconnu qu'on cherche à estimer. Le dimensionnement. On veut [formule] avec [formule], soit [formule], donc [formule] d'où [formule]. Contrôle : [formule], tandis que [formule] donne exactement [formule] — le seuil est bien franchi au bon entier. Les trois outils, sur la même question. Pour la même précision et la même confiance : [formule] La hiérarchie est celle des hypothèses. Tchebychev n'utilise que la variance, majorée par [formule]. Hoeffding utilise la bornitude, ce qui donne une décroissance exponentielle en [formule] au lieu de [formule]. Le TCL, lui, utilise la forme limite de la loi — mais ce n'est plus une garantie. Combien Hoeffding sur-protège-t-il ? La question se tranche par un calcul exact. La probabilité binomiale véritable, pour [formule], vaut [formule] Le dimensionnement par le TCL atteint donc presque exactement la cible de [formule], alors que celui de Hoeffding est sept fois plus protecteur que nécessaire. Doubler l'échantillon n'achète ici aucune précision supplémentaire : cela achète la certitude que la borne est vraie sans hypothèse asymptotique. ⚠️ Et c'est ce qui décide du choix, pas le nombre. Le TCL donne une approximation dont l'erreur n'est pas contrôlée : [formule] n'est pas un nombre de lancers garantissant [formule], c'est un nombre pour lequel on espère y être. Ici le calcul exact confirme qu'on y est — mais on ne le sait qu'en ayant fait ce calcul, qui suppose [formule] connu. Hoeffding, lui, est non asymptotique et uniforme en [formule] : sa borne est vraie pour [formule] comme pour [formule], quelle que soit la valeur inconnue. 💡 À retenir. Une borne de concentration se choisit sur ce qu'elle garantit, pas sur le nombre qu'elle produit. Retenir la forme [formule] pour des variables dans [formule] : elle donne directement la taille d'échantillon [formule], et c'est elle qui fonde les garanties de l'apprentissage statistique, où l'on a besoin d'énoncés valables à [formule] fini.