Bretagnolle–Huber inequality

In information theory, the Bretagnolle–Huber inequality bounds the total variation distance between two probability distributions ${\displaystyle P}$ and ${\displaystyle Q}$ by a concave and bounded function of the Kullback–Leibler divergence ${\displaystyle D_{\mathrm {KL} }(P\parallel Q)}$. The bound can be viewed as an alternative to the well-known Pinsker's inequality: when ${\displaystyle D_{\mathrm {KL} }(P\parallel Q)}$ is large (larger than 2 for instance.^[1]), Pinsker's inequality is vacuous, while Bretagnolle–Huber remains bounded and hence non-vacuous. It is used in statistics and machine learning to prove information-theoretic lower bounds relying on hypothesis testing^[2]　 (Bretagnolle–Huber–Carol Inequality is a variation of Concentration inequality for multinomially distributed random variables which bounds the total variation distance.)

Formal statement

Preliminary definitions

Let ${\displaystyle P}$ and ${\displaystyle Q}$ be two probability distributions on a measurable space ${\displaystyle ({\mathcal {X}},{\mathcal {F}})}$. Recall that the total variation between ${\displaystyle P}$ and ${\displaystyle Q}$ is defined by

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

The Kullback-Leibler divergence is defined as follows:

${\displaystyle 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}}}$

In the above, the notation ${\displaystyle P\ll Q}$ stands for absolute continuity of ${\displaystyle P}$ with respect to ${\displaystyle Q}$, and ${\displaystyle {\frac {dP}{dQ}}}$ stands for the Radon–Nikodym derivative of ${\displaystyle P}$ with respect to ${\displaystyle Q}$.

General statement

The Bretagnolle–Huber inequality says:

${\displaystyle 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))}$

Alternative version

The following version is directly implied by the bound above but some authors^[2] prefer stating it this way. Let ${\displaystyle A\in {\mathcal {F}}}$ be any event. Then

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

where ${\displaystyle {\bar {A}}=\Omega \smallsetminus A}$ is the complement of ${\displaystyle A}$.

Indeed, by definition of the total variation, for any ${\displaystyle A\in {\mathcal {F}}}$,

${\displaystyle {\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}}}$

Rearranging, we obtain the claimed lower bound on ${\displaystyle P(A)+Q({\bar {A}})}$.

Proof

We prove the main statement following the ideas in Tsybakov's book (Lemma 2.6, page 89),^[3] which differ from the original proof^[4] (see C.Canonne's note ^[1] for a modernized retranscription of their argument).

The proof is in two steps:

1. Prove using Cauchy–Schwarz that the total variation is related to the Bhattacharyya coefficient (right-hand side of the inequality):

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

2. Prove by a clever application of Jensen’s inequality that

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

• Step 1:

First notice that

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

To see this, denote ${\displaystyle A^{*}=\arg \max _{A\in \Omega }|P(A)-Q(A)|}$ and without loss of generality, assume that ${\displaystyle P(A^{*})>Q(A^{*})}$ such that ${\displaystyle d_{\mathrm {TV} }(P,Q)=P(A^{*})-Q(A^{*})}$. Then we can rewrite

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

And then adding and removing ${\displaystyle \int _{\bar {A^{*}}}\max(P,Q){\text{ or }}\int _{\bar {A^{*}}}\min(P,Q)}$ we obtain both identities.

Then

${\displaystyle {\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}}}$

because ${\displaystyle PQ=\min(P,Q)\max(P,Q).}$

• Step 2:

We write ${\displaystyle (\cdot )^{2}=\exp(2\log(\cdot ))}$ and apply Jensen's inequality:

${\displaystyle {\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}}}$

Combining the results of steps 1 and 2 leads to the claimed bound on the total variation.

Examples of applications

Sample complexity of biased coin tosses

Source:^[1]

The question is How many coin tosses do I need to distinguish a fair coin from a biased one?

Assume you have 2 coins, a fair coin (Bernoulli distributed with mean ${\displaystyle p_{1}=1/2}$) and an ${\displaystyle \varepsilon }$-biased coin (${\displaystyle p_{2}=1/2+\varepsilon }$). Then, in order to identify the biased coin with probability at least ${\displaystyle 1-\delta }$ (for some ${\displaystyle \delta >0}$), at least

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

In order to obtain this lower bound we impose that the total variation distance between two sequences of ${\displaystyle n}$ samples is at least ${\displaystyle 1-2\delta }$. This is because the total variation upper bounds the probability of under- or over-estimating the coins' means. Denote ${\displaystyle P_{1}^{n}}$ and ${\displaystyle P_{2}^{n}}$ the respective joint distributions of the ${\displaystyle n}$ coin tosses for each coin, then

We have

${\displaystyle {\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}}}$

The result is obtained by rearranging the terms.

Information-theoretic lower bound for k-armed bandit games

In multi-armed bandit, a lower bound on the minimax regret of any bandit algorithm can be proved using Bretagnolle–Huber and its consequence on hypothesis testing (see Chapter 15 of Bandit Algorithms^[2]).

History

The result was first proved in 1979 by Jean Bretagnolle and Catherine Huber, and published in the proceedings of the Strasbourg Probability Seminar.^[4] Alexandre Tsybakov's book^[3] features an early re-publication of the inequality and its attribution to Bretagnolle and Huber, which is presented as an early and less general version of Assouad's lemma (see notes 2.8). A constant improvement on Bretagnolle–Huber was proved in 2014 as a consequence of an extension of Fano's Inequality.^[5]

See also

• Total variation for a list of upper bounds
• Bretagnolle–Huber–Carol Inequality in Concentration inequality

References