Bretagnolle–Huber inequality
In information theory, the Bretagnolle–Huber inequality bounds the total variation distance between two probability distributions  and  by a concave and bounded function of the Kullback–Leibler divergence . The bound can be viewed as an alternative to the well-known Pinsker's inequality: when  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  and  be two probability distributions on a measurable space . Recall that the total variation between  and  is defined by 
 

The Kullback-Leibler divergence is defined as follows:

In the above, the notation  stands for absolute continuity of  with respect to , and  stands for the Radon–Nikodym derivative of  with respect to . General statement 
The Bretagnolle–Huber inequality says:

Alternative version 

The following version is directly implied by the bound above but some authors prefer stating it this way. Let  be any event. Then

 

where  is the complement of . Indeed, by definition of the total variation, for any ,

 

Rearranging, we obtain the claimed lower bound on . 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):

 

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

 

 Step 1:

 First notice that

 

 To see this, denote  and without loss of generality, assume that   such that . Then we can rewrite

 

 And then adding and removing  we obtain both identities. Then

 

 because 

 Step 2:

 We write  and apply Jensen's inequality:
 

 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:

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 ) and an -biased coin (). Then, in order to identify the biased coin with probability at least  (for some ), at least 

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

We have

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, 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

References 

Information theory
Probabilistic inequalities