In information theory, the Bretagnolle–Huber inequality bounds the total variation distance between two probability distributions
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.
[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.)
be two probability distributions on a measurable space
Recall that the total variation between
stands for absolute continuity of
The Bretagnolle–Huber inequality says: The following version is directly implied by the bound above but some authors[2] prefer stating it this way.
Indeed, by definition of the total variation, for any
, Rearranging, we obtain the claimed lower bound on
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).
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 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
Then, in order to identify the biased coin with probability at least
), at least In order to obtain this lower bound we impose that the total variation distance between two sequences of
This is because the total variation upper bounds the probability of under- or over-estimating the coins' means.
the respective joint distributions of the
coin tosses for each coin, then We have The result is obtained by rearranging the terms.
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]).
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.