# How does Pinsker's inequality provide "a lower bound for the error of certain hypothesis testing problems"?

Whilst flicking through Concentration Inequalities: A Nonasymptotic Theory of Independence by Boucheron, Lugosi and Massart (2016), I came across the following incidental remark:

The importance of Pinsker's inequality in statistics stems from the fact that it provides a lower bound for the error of certain hypothesis testing problems.

The authors do not specify the hypothesis testing problems whose error can be lower bounded by Pinsker's inequality, presumably because their focus in the book is not statistics. Nor do they specify how this might work. I would therefore greatly appreciate if members of the community could shed some light on the following question:

What are the authors referring to when they say that the utility of Pinsker's inequality "stems from the fact that it provides a lower bound for the error of certain hypothesis testing problems? And how would this work?

Context.

Here is an extract from Section 4.11 Pinsker's inequality of the monograph, where the remark can be found:

Pinsker's inequality relates the relative entropy of two probability distributions to their variational distance. Let $$\mathcal{P}$$ and $$\mathcal{Q}$$ be two probability measures on a measurable space $$(\Omega, \mathcal{A})$$. The total variation or variational distance between $$\mathcal{P}$$ and $$\mathcal{Q}$$ is defined by

$$V(\mathcal{P}, \mathcal{Q}) = \sup_{A \in \mathcal{A}} \vert \mathcal{P}(A) - \mathcal{Q}(A) \vert.$$ It is a well known and simple fact that the total variation is half the $$L_1$$-distance, that is if $$\lambda$$ is the common dominating measure of $$\mathcal{P}$$ and $$\mathcal{Q}$$ and $$p(x) = d\mathcal{P}/d\lambda$$ and $$q(x) = d \mathcal{Q} / d \lambda$$ denote their respective densities, then

$$V(\mathcal{P}, \mathcal{Q}) = \mathcal{P}(A^*) - \mathcal{Q}(A^*) = \frac{1}{2} \int \vert p(x) - q(x) \vert d \lambda(x),$$ where $$A^* = \{x: p(x) \geq q(x) \}$$. We note that another important interpretation of the variational distance is related to the best coupling of the two measures

$$V(\mathcal{P}, \mathcal{Q}) = \min \mathcal{P} \{X \neq Y \},$$ where the minimum is taken over all pairs of joint distributions for the random variables $$(X, Y)$$ whose marginal distributions are $$X \sim \mathcal{P}$$ and $$Y \sim \mathcal{Q}$$. (The proof of these well-known facts is left as Exercise 4.5).

The importance of Pinsker's inequality in statistics stems from the fact that it provides a lower bound for the error of certain hypothesis testing problems [my emphasis]. We use Pinsker's inequality for a completely different purpose, namely for establishing a transportation cost inequality that may be used to prove concentration inequalities. The proof of Pinsker's inequality derives easily from Hoeffding's inequality via the transportation cost bound of Lemma 4.1.8:

Theorem 4.1.9 (Pinsker's inequality) Let $$\mathcal{P}$$ and $$\mathcal{Q}$$ be probability distributions on $$(\Omega, \mathcal{A})$$ such that $$\mathcal{Q} \ll \mathcal{P}$$. Then

$$V(\mathcal{P}, \mathcal{Q})^2 \leq \frac{1}{2} D(\mathcal{Q} || \mathcal{P}).$$ [Proof omitted.]

Say you have two hypothesis - Null hypothesis and an Alternate hypothesis. Under the null hypothesis, your test statistic follows a distribution $$P$$, say $$\mathcal{N}(0,1)$$ and under the alternate hypothesis, it follows a distribution $$Q$$, say $$\mathcal{N}(\mu,1)$$.
Now say you want to calculate the maximum probability of error (between type I and type II). If type I error is when your test statistic falls in the region $$A$$ under Null Hypothesis, then type II error is when your test statistic falls in region $$A^c$$ under alternate hypothesis.
Note that $$1 - V(P,Q) \leq P(A) + Q(A^c)$$ for any $$A$$, by definition of Total variation distance. Hence, the errors can be bounded as follows:
\begin{align} \max (P(A),Q(A^c)) \geq \frac{P(A)+Q\left(A^{c}\right)}{2} & \geq \frac{1}{2} (1 - V) \\ & \geq \frac{1}{2} (1-\sqrt{\frac{D}{2}}) \end{align}
The first inequality follows from $$\max(x,y) \geq \frac{x+y}{2}$$ and the third one follows from Pinskers inequality. For standard distributions, there will be closed form expression to compute the KL-divergence $$D$$.