Inequality in information theory
In information theory, the Bretagnolle–Huber inequality bounds the total variation distance between two probability distributions formula_1 and formula_2 by a concave and bounded function of the Kullback–Leibler divergence formula_3. The bound can be viewed as an alternative to the well-known Pinsker's inequality: when formula_3 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 formula_1 and formula_2 be two probability distributions on a measurable space formula_7.
Recall that the total variation between formula_1 and formula_2 is defined by 
 formula_10
The Kullback-Leibler divergence is defined as follows:
formula_11
In the above, the notation formula_12 stands for absolute continuity of formula_1 with respect to formula_2, and formula_15 stands for the Radon–Nikodym derivative of formula_1 with respect to formula_2.
General statement.
The Bretagnolle–Huber inequality says:
 formula_18
Alternative version.
The following version is directly implied by the bound above but some authors prefer stating it this way. 
Let formula_19 be any event. Then
 formula_20
where formula_21 is the complement of formula_22.
Indeed, by definition of the total variation, for any formula_23,
 formula_24
Rearranging, we obtain the claimed lower bound on formula_25.
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):
 formula_26
2. Prove by a clever application of Jensen’s inequality that
 formula_27
 First notice that
 formula_28
 To see this, denote formula_29 and without loss of generality, assume that formula_30 such that formula_31. Then we can rewrite
 formula_32
 And then adding and removing formula_33 we obtain both identities.
 Then
 formula_34
 because formula_35
 We write formula_36 and apply Jensen's inequality:
 formula_37
 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 formula_38) and an formula_39-biased coin (formula_40). Then, in order to identify the biased coin with probability at least formula_41 (for some formula_42), at least 
formula_43
In order to obtain this lower bound we impose that the total variation distance between two sequences of formula_44 samples is at least formula_45. This is because the total variation upper bounds the probability of under- or over-estimating the coins' means. Denote formula_46 and formula_47 the respective joint distributions of the formula_44 coin tosses for each coin, then
We have
formula_49
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.
References.
 ;templatestyles src="Reflist/styles.css" / ;