Inégalité de Bretagnolle – Huber

En théorie de l'information, l' inégalité de Bretagnolle – Huber limite la distance de variation totale entre deux distributions de probabilité $P$ et $Q$ par une fonction concave et bornée de la divergence Kullback – Leibler $D_{\mathrm {KL} }(P\parallel Q)$ . La borne peut être considérée comme une alternative à la célèbre inégalité de Pinsker : lorsque $D_{\mathrm {KL} }(P\parallel Q)$ est grand (supérieur à 2 par exemple), l'inégalité de Pinsker n'est pas informative car la borne tend vers l'infini, tandis que Bretagnolle – Huber reste bornée. Elle est utilisée en statistiques et en apprentissage automatique pour prouver les limites inférieures de la théorie de l'information en s'appuyant sur des tests d'hypothèses (l'inégalité de Bretagnolle – Huber – Carol est une variation de l'inégalité de concentration pour les variables aléatoires multinomiales qui délimite la distance de variation totale).

Enoncé

Définitions préliminaires

Soient $P$ et $Q$ deux distributions de probabilité sur un espace mesurable $({\mathcal {X}},{\mathcal {F}})$ . Rappelons que la variation totale entre $P$ et $Q$ est défini par

$d_{\mathrm {TV} }(P,Q)=\sup _{A\in {\mathcal {F}}}\{|P(A)-Q(A)|\}.$

La divergence Kullback-Leibler est définie comme suit :

$D_{\mathrm {KL} }(P\parallel Q)={\begin{cases}\int _{\mathcal {X}}\log {\bigl (}{\frac {dP}{dQ}}{\bigr )}\,dP&{\text{if }}P\ll Q,\\[1mm]+\infty &{\text{otherwise}}.\end{cases}}$

Dans ce qui précède, la notation $P\ll Q$ signifie que P est absolument continue par rapport a Q, et ${\frac {dP}{dQ}}$ représente le dérivée de Radon – Nikodym de $P$ par rapport à $Q$ .

Enoncé général

L'inégalité de Bretagnolle-Huber s'énonce comme suit: Pour deux distributions de probabilités P et Q telles que $P\ll Q$,

$d_{\mathrm {TV} }(P,Q)\leq {\sqrt {1-\exp(-D_{\mathrm {KL} }(P\parallel Q))}}\leq 1-{\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))$

Version alternative

La version suivante est directement impliquée par la limite ci-dessus mais certains auteurs préfèrent l'énoncer de cette façon. Soit $A\in {\mathcal {F}}$ un événement. Alors,

$P(A)+Q({\bar {A}})\geq {\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))$

où ${\bar {A}}=\Omega \smallsetminus A$ est le complément de $A$ .

En effet, par définition de la variation totale, pour tout $A\in {\mathcal {F}}$ ,

${\begin{aligned}Q(A)-P(A)\leq d_{\mathrm {TV} }(P,Q)&\leq 1-{\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))\\&=Q(A)+Q({\bar {A}})-{\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))\end{aligned}}$

En réorganisant, nous obtenons la borne inférieure revendiquée sur $P(A)+Q({\bar {A}})$ .

Preuve

Nous prouvons l'énoncé principal suivant les idées du livre de Tsybakov (Lemme 2.6, page 89), qui diffèrent de la preuve originale (voir la note de C.Canonne pour une retranscription modernisée de leur argument).

La preuve se déroule en deux étapes :

1. Prouver à l'aide de Cauchy – Schwarz que la variation totale est liée au coefficient Bhattacharyya (partie droite de l'inégalité) :

$1-d_{\mathrm {TV} }(P,Q)^{2}\geq \left(\int {\sqrt {PQ}}\right)^{2}$

2. Prouver par une application appropriée de l'inégalité de Jensen que

$\left(\int {\sqrt {PQ}}\right)^{2}\geq \exp(-D_{\mathrm {KL} }(P\parallel Q))$

• Étape 1:

Remarquez d'abord que

$d_{\mathrm {TV} }(P,Q)=1-\int \min(P,Q)=\int \max(P,Q)-1$

Pour voir cela, notez $A^{*}=\arg \max _{A\in \Omega }|P(A)-Q(A)|$ et sans perte de généralité, supposons que $P(A^{*})>Q(A^{*})$ tel que $d_{\mathrm {TV} }(P,Q)=P(A^{*})-Q(A^{*})$ . Ensuite, nous pouvons réécrire

$d_{\mathrm {TV} }(P,Q)=\int _{A^{*}}\max(P,Q)-\int _{A^{*}}\min(P,Q)$

Et puis ajouter et supprimer $\int _{\bar {A^{*}}}\max(P,Q){\text{ or }}\int _{\bar {A^{*}}}\min(P,Q)$ nous obtenons les deux identités.

Alors

${\begin{aligned}1-d_{\mathrm {TV} }(P,Q)^{2}&=(1-d_{\mathrm {TV} }(P,Q))(1+d_{\mathrm {TV} }(P,Q))\\&=\int \min(P,Q)\int \max(P,Q)\\&\geq \left(\int {\sqrt {\min(P,Q)\max(P,Q)}}\right)^{2}\\&=\left(\int {\sqrt {PQ}}\right)^{2}\end{aligned}}$

parce que $PQ=\min(P,Q)\max(P,Q).$

• Étape 2:

Nous écrivons $(\cdot )^{2}=\exp(2\log(\cdot ))$ et appliquer l'inégalité de Jensen :

${\begin{aligned}\left(\int {\sqrt {PQ}}\right)^{2}&=\exp \left(2\log \left(\int {\sqrt {PQ}}\right)\right)\\&=\exp \left(2\log \left(\int P{\sqrt {\frac {Q}{P}}}\right)\right)\\&=\exp \left(2\log \left(\operatorname {E} _{P}\left[\left({\sqrt {\frac {P}{Q}}}\right)^{-1}\,\right]\right)\right)\\&\geq \exp \left(\operatorname {E} _{P}\left[-\log \left({\frac {P}{Q}}\right)\right]\right)=\exp(-D_{KL}(P,Q))\end{aligned}}$

La combinaison des résultats des étapes 1 et 2 conduit à la limite revendiquée sur la variation totale.

Exemples d'applications

Exemple de complexité de lancers de pièces biaisés

La question est de savoir combien de tirages à pile ou face ai-je besoin pour distinguer une pièce équilibrée d’une pièce biaisée ?

Supposons que vous ayez 2 pièces, une pièce équilibrée (Bernoulli distribué avec une moyenne $p_{1}=1/2$ ) et un pièce $\varepsilon$-biaisée ($p_{2}=1/2+\varepsilon$ ). Ensuite, afin d'identifier la pièce biaisée avec une probabilité d'au moins $1-\delta$ (pour certains $\delta >0$ ), on doit tirer la pièce $n$ fois avec

$n\geq {\frac {1}{2\varepsilon ^{2}}}\log \left({\frac {1}{2\delta }}\right).$

Afin d’obtenir cette borne inférieure nous imposons que la distance totale de variation entre deux séquences de $n$ échantillons soit au moins $1-2\delta$ . En effet, la variation totale limite la probabilité de sous-estimer ou de surestimer les moyennes des pièces. Dénotons $P_{1}^{n}$ et $P_{2}^{n}$ les distributions conjointes respectives des $n$ des tirages au sort pour chaque pièce. Alors nous avons,

${\begin{aligned}(1-2\delta )^{2}&\leq d_{\mathrm {TV} }\left(P_{1}^{n},P_{2}^{n}\right)^{2}\\[4pt]&\leq 1-e^{-D_{\mathrm {KL} }(P_{1}^{n}\parallel P_{2}^{n})}\\[4pt]&=1-e^{-nD_{\mathrm {KL} }(P_{1}\parallel P_{2})}\\[4pt]&=1-e^{-n{\frac {\log(1/(1-4\varepsilon ^{2}))}{2}}}\end{aligned}}$

Le résultat est obtenu en réorganisant les termes.

Borne inférieure théorique pour les jeux de bandits manchots à k bras

Dans le problème du bandit manchot, une limite inférieure du regret minimax de tout algorithme de bandit peut être prouvée en utilisant Bretagnolle – Huber et ses conséquences sur les tests d'hypothèses (voir le chapitre 15 de Bandit Algorithms ).

Histoire

Le résultat a été prouvé pour la première fois en 1979 par Jean Bretagnolle et Catherine Huber, et publié dans les actes du Séminaire de Probabilités de Strasbourg. Le livre d'Alexandre Tsybakov présente une première réédition de l'inégalité et de son attribution à Bretagnolle et Huber. Celle-ci est présentée comme une version ancienne et moins générale du lemme d'Assouad (voir notes 2.8). Une amélioration constante par rapport à Bretagnolle – Huber a été prouvée en 2014 grâce à une extension de l'inégalité de Fano.

Voir également

• Variation totale pour une liste de bornes supérieures
• Inégalité de Bretagnolle – Huber – Carol dans la page Inégalité de concentration