Bretagnolle-Huber inequality

Short description: Inequality in information theory

In information theory, the Bretagnolle-Huber inequality bounds the total variation distance between two probability distributions $P$ and $Q$ by a concave and bounded function of the Kullback-Leibler divergence $D_{\mathrm{K}\mathrm{L}}(P\parallel Q)$. The bound can be viewed as an alternative to the well-known Pinsker's inequality: when $D_{\mathrm{K}\mathrm{L}}(P\parallel Q)$ is large (larger than 2 for instance.), 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

Formal statement

Preliminary definitions

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

$d_{\mathrm{T}\mathrm{V}}(P,Q)=\underset{A\in {ℱ}}{\sup }\{|P(A)-Q(A)|\}.$

The Kullback-Leibler divergence is defined as follows:

$D_{\mathrm{K}\mathrm{L}}(P\parallel Q)=\{\begin{array}{ll}\underset{{𝒳}}{\int }\log \left(\frac{dP}{dQ}\right)dP& \text{if}P\ll Q,\\ +\mathrm{\infty }& \text{otherwise}.\end{array}$

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

General Statement

The Bretagnolle-Huber inequality says:

$d_{\mathrm{T}\mathrm{V}}(P,Q)\le \sqrt{1-\exp (-D_{\mathrm{K}\mathrm{L}}(P\parallel Q))}\le 1-\frac{1}{2}\exp (-D_{\mathrm{K}\mathrm{L}}(P\parallel Q))$

Alternative version

The following version is directly implied by the bound above but some authors prefer stating it this way. Let $A\in {ℱ}$ be any event. Then

$P(A)+Q(\overline{A})\ge \frac{1}{2}\exp (-D_{\mathrm{K}\mathrm{L}}(P\parallel Q))$

Where $\overline{A}=\mathrm{\Omega }\setminus A$ is the complement of $A$.

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

$\begin{array}{rl}Q(A)-P(A)\le d_{\mathrm{T}\mathrm{V}}(P,Q)& \le 1-\frac{1}{2}\exp (-D_{\mathrm{K}\mathrm{L}}(P\parallel Q))\\ & =Q(A)+Q(\overline{A})-\frac{1}{2}\exp (-D_{\mathrm{K}\mathrm{L}}(P\parallel Q))\end{array}$

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

Proof

We prove the main statement following the ideas in Tsybakov's book (Lemma 2.6, page 89), which differ from the original proof (see C.Canonne's note 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):

$1-d_{\mathrm{T}\mathrm{V}}(P,Q{)}^2\ge {(\int \sqrt{PQ})}^2$

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

${(\int \sqrt{PQ})}^2\ge \exp (-D_{\mathrm{K}\mathrm{L}}(P\parallel Q))$

• Step 1:

First notice that

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

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

$d_{\mathrm{T}\mathrm{V}}(P,Q)=\underset{A^{*}}{\int }\max (P,Q)-\underset{A^{*}}{\int }\min (P,Q)$

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

Then,

$\begin{array}{rl}1-d_{\mathrm{T}\mathrm{V}}(P,Q{)}^2& =(1-d_{\mathrm{T}\mathrm{V}}(P,Q))(1+d_{\mathrm{T}\mathrm{V}}(P,Q))\\ & ={(\int \min (P,Q)\int \max (P,Q))}^2\ge \int {\left(\sqrt{\min (P,Q)\max (P,Q)}\right)}^2\\ & ={(\int \sqrt{PQ})}^2\end{array}$

Because $PQ=\min (P,Q)\max (P,Q)$

• Step 2:

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

$\begin{array}{rl}{(\int \sqrt{PQ})}^2& =\exp (2\log {(\int \sqrt{PQ})}^2)=\exp (2\log {(\int P\sqrt{\frac{Q}{P}})}^2)\\ & \exp (2\log ({\mathbb{𝔼}}_P[\sqrt{\frac{P}{Q}}])\ge \exp ({\mathbb{𝔼}}_P\log (\frac{P}{Q}))=\exp (-D_{KL}(P,Q))\end{array}$

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

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 $p_1=1/2$) and an $ϵ$-biased coin ($p_2=1/2+ϵ$). Then, in order to identify the biased coin with probability at least $1-\delta$ (for some $\delta >0$), at least

$n\ge \frac{1}{2{ϵ}^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 $n$ samples is at least $1-2\delta$. This is because the total variation upper bounds the probability of under- or over-estimating the coins' means. Denote $P_1^n$ and $P_2^n$ the respective joint distributions of the $n$ coin tosses for each coin, then

We have

$\begin{array}{rl}(1-2\delta {)}^2& \le d_{\mathrm{T}\mathrm{V}}{(P_1^n,P_2^n)}^2\\ & \le 1-e^{-D_{\mathrm{K}\mathrm{L}}(P_1^n\parallel P_2^n)}\\ & =1-e^{-n{D}_{\mathrm{K}\mathrm{L}}(P_1\parallel P_2)}\\ & =1-e^{-n\frac{\log (1/(1-4{ϵ}^2))}{2}}\end{array}$

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).

History

The result was first proved in 1979 by Jean Bretagnolle and Catherine Huber (now Huber-Carol), and published in the proceedings of the Strasbourg Probability Seminar. Alexandre Tsybakov's book 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.

See also

• Total variation for a list of upper bounds;