Relative information spectra with applications to statistical inference

1.   Introduction

Shortly after the advent of information theory ^[1], Kullback and Leibler ^[2] introduced relative entropy (or Kullback-Leibler divergence) as a means of generalizing to arbitrary alphabets Shannon's foundational information measures——entropy, differential entropy, and mutual information. They recognized that relative entropy could play a pivotal role, not in Shannon's data compression and transmission problems, but in statistical inference, in particular, in the theory of sufficient statistics, which had recently been put on a sound mathematical footing by Halmos and Savage ^[3]. The application of information theory to statistical inference, initiated in ^[2], continued with Fano's inequality ^[4]——a lower bound on error probability in Bayesian $M$-ary hypothesis testing based on conditional entropy. Lindley ^[5] suggested using mutual information to explore sufficiency. Chernoff ^[6] found an asymptotic operational role for relative entropy in another fundamental pillar of statistical inference, the theory of hypothesis testing pioneered by Neyman and Pearson in ^[7]. Soon after, Sanov ^[8] showed that relative entropy plays a pivotal role in the theory of large deviations pioneered two decades earlier by Cramér in ^[9]. For the purpose of statistical modeling, Jaynes ^[10,11] and Kullback ^[12] advocated the maximization of entropy and the minimization of relative entropy with a fixed nominal reference measure, respectively.

Other information theoretic measures would prove useful in statistical inference. Rényi divergence ^[13] and Chernoff information ^[14] emerged as key tools in the asymptotic analysis of non-Bayesian and Bayesian hypothesis testing, respectively. Csiszár ^[15] showed that the role of relative entropy in sufficient statistics, found by Kullback and Leibler, could be extended to $f$-divergences, a much wider collection of discrepancy measures that obey the data processing principle (no processing can increase them). Among the many $f$-divergences that have found widespread applications in statistical inference are total variation distance, $\chi^2$-divergence ^[16], Hellinger distance ^[17], Hellinger divergence ^[14], Vincze-Le Cam divergence ^[18,19], and de Groot statistical information ^[20].

Moving forward to the last decade of the XXth century, ^[21] started a new direction in information theory: The information spectrum approach, whose original goal was to generalize the flagship asymptotic results in information theory without assumptions of discreteness, memorylessness, ergodicity, or even stationarity. Working with very little structure has the benefit of bringing out the essential aspects that allow Shannon's results ^[1] to transcend their original habitat. A price to be paid for the generality of those results is that entropy, relative entropy, and mutual information are no longer sufficient to express the asymptotic fundamental limits. Those information measures are expectations of random variables whose distributions, dubbed information spectra in ^[21], emerge as the crucial ingredients in the solution. Han's monograph ^[22] provides a comprehensive overview of the application of the information spectrum method to the asymptotic fundamental limits in various domains, including lossless and lossy data compression, data transmission, hypothesis testing, channel resolvability, and random number generation. Started in ^[23], another trend in information theory seeks to determine non-asymptotic fundamental limits, e.g., what is the transmission rate compatible with a blocklength of 1000 and a probability of decoding error of $10^{-2}$? Approximate answers to this type of questions can be obtained through upper and lower bounds that depend on the information spectra.

Entropy is a special case of mutual information, which in turn is a special case of relative entropy. The relative entropy, $D(P_X \, \| \, P_Y)$, of probability measures $P_X$ and $P_Y$ defined on the same space is the expectation of the random variable $\imath_{X\|Y} (X)$, where $\imath_{X\|Y} (x)$ stands for the relative information defined as the logarithm of the Radon-Nikodym derivative $\frac{\mathrm{d}P_X}{\mathrm{d}P_Y}(x)$, or more generally, $\log \frac{\mathrm{d}P_X}{\mathrm{d}\mathsf{μ}}(x) - \log \frac{\mathrm{d}P_Y}{\mathrm{d}\mathsf{μ}}(x)$, where $\mathsf{μ}$ dominates both probability measures. The key objects of interest in this paper are the relative information spectra, namely, the cumulative distribution functions of $\imath_{X\|Y} (X)$ and $\imath_{X\|Y} (Y)$. In addition to a number of properties satisfied by the relative information spectra, we show new results in both sufficient statistics and binary hypothesis testing through the application of those properties.

To enhance readability and ease of reference, the rest of this work is organized in one hundred items grouped into eight sections, plus an appendix.

Section 2 contains most of the terminology and notation used throughout the paper, as well as several auxiliary results used in the sequel. As no restrictions (including absolute continuity) are placed on the pairs of probability measures under purview, the notions of relative support and coefficient of absolute discontinuity prove to be of central importance in the subsequent development.

Section 3 deals with the fundamental properties of the relative information, including the change of measure formulas without requiring absolute continuity. It also explores properties of Rényi divergence and information density——a special case of relative information whose expectation is the mutual information, and which proves useful in Section 7.

Section 4 focuses on the interplay of the distributions of the random variables $\imath_{X\|Y} (X)$ and $\imath_{X\|Y} (Y)$. The key notion of equivalent pairs of probability measures, proposed recently in ^[24] in the special case of absolutely continuous probability measures, is given here in full generality, along with several necessary and sufficient conditions involving Rényi divergence and $f$-divergences.

Section 5 shows various ways to express and bound total variation distance as a function of the relative information spectra, a problem initially undertaken by Le Cam ^[19].

A new measure of discrepancy between probability measures, dubbed the NP-divergence, is introduced in Section 6. Although it satisfies the data processing principle, NP-divergence is not an $f$-divergence. Its main operational role, which justifies its name, is revealed in Section 8.

Section 7 presents a new notion of sufficient statistics, $I$-sufficiency, based on equivalent pairs. To put this notion in perspective, Section 7 also includes a discussion of the leading existing definitions of sufficient statistics, such as classical (Fisher) sufficiency, Blackwell sufficiency, and Bayes sufficiency. $I$-sufficiency is a natural bridge between those notions and criteria based on the equality of the data processing inequality for $f$-divergence. All those notions turn out to be equivalent under the assumption that the data model is dominated and defined on a standard space.

Section 8 gives a self-contained solution to the non-asymptotic fundamental tradeoff region consisting of the set of achievable conditional error probabilities in non-Bayesian binary hypothesis testing, at a level of detail apparently not available elsewhere. A scalar proxy is often sought to quantify how well probability measures can be distinguished. In non-Bayesian hypothesis testing, the area of the tradeoff region is arguably the most natural scalar measure. Section 8 demonstrates that this area equals one-half of the NP-divergence. This establishes an interesting relationship between the hypothesis testing problems

The area of the fundamental tradeoff region for $\{{\mathsf{H}_{{\mathtt{0}}}}, {\mathsf{H}_{{\mathtt{1}}}}\}$ is shown to equal $1- 2 \epsilon_{\min} (\mathsf{H}_L, \mathsf{H}_R)$, where $\epsilon_{\min} (\mathsf{H}_L, \mathsf{H}_R)$ is the minimum (Bayesian) error probability when $\{\mathsf{H}_L, \mathsf{H}_R\}$ are equally likely. A new asymptotic operational role is found for the Bhattacharyya distance in the setting of independent identically distributed data.

Section 9 gives a recap of the main new results found in the paper.

2.   Preliminaries

This section introduces basic terminology and notation, along with supporting results used in the remainder of the paper.

1. ${\mathscr{P}_{\!\!\mathcal{{A}}}}$ denotes the set of probability measures defined on the measurable space $(\mathcal{{A}}, \mathscr{F})$.

2. For $P \in {\mathscr{P}_{\!\!\mathcal{{A}}}}$, $X \sim P$ means that $\mathbb{P} [ X \in E] = P(E)$ for all $E \in \mathscr{F}$.

3. A random transformation

is a collection $\{ P_{Y|X = a} \in \mathscr{P}_{\mathcal{{B}}}, \, a\in \mathcal{{A}} \}$ of probability measures defined on the measurable space $(\mathcal{{B}}, \mathscr{G})$, such that for every $B \in \mathscr{G}$, $f_B\colon \mathcal{{A}} \to [0, 1]$ given by $f_B (a) = P_{Y|X = a} (B)$ is a Borel $\mathscr{F}$-measurable function. In the literature, random transformations are also referred to as Markov kernels. The sets $\mathcal{{A}}$ and $\mathcal{{B}}$ are known as the input and output alphabets of the random transformation, respectively. Note that a joint probability measure $P_{XY}$ need not be defined notwithstanding the notation in (2.1). If in addition to the random transformation (2.1), a probability measure $P_X \in {\mathscr{P}_{\!\!\mathcal{{A}}}}$ is defined, then the input/output joint probability measure $P_{XY}$ on $(\mathcal{{A}} \times \mathcal{{B}}, \mathscr{F}\otimes \mathscr{G})$ is given by

The marginal output probability measure, $P_Y$, also known as the response of $P_{Y|X}$ to $P_X$, is denoted by

4. If $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$, $P \ll Q$ means that $Q$ dominates $P$, or alternatively, $P$ is absolutely continuous with respect to $Q$, i.e., $P(A) = 0$ for any $A \in \mathscr{F}$ such that $Q(A) = 0$. More generally, a collection $\mathscr{P} \subset {\mathscr{P}_{\!\!\mathcal{{A}}}}$ is said to be dominated by $Q$ if $P \ll Q$ for all $P \in \mathscr{P}$. If $Q$ dominates $\mathscr{P}$ and $Q(E) = 0$ whenever $E \in \mathscr{F}$ is such that $P(E) = 0$ for all $P \in \mathscr{P}$, $Q$ is said to be equivalent to $\mathscr{P}$. The same terminology applies to general measures on $(\mathcal{{A}}, \mathscr{F})$.

5. If $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $P \ll Q \ll P$, then we write $P \ll \gg Q$ and $P$ and $Q$ are said to be mutually absolutely continuous or equivalent.

6. Lemma 1. [3, Lemma 7] Assume that there exists a $\sigma$-finite measure on $(\mathcal{{A}}, \mathscr{F})$ that dominates the collection $\mathscr{P} \subset {\mathscr{P}_{\!\!\mathcal{{A}}}}$. Then, there exists a probability measure in ${\mathscr{P}_{\!\!\mathcal{{A}}}}$ that is equivalent to the collection $\mathscr{P}$. In fact, there exists a finite or countably infinite collection $\{P_i\in \mathscr{P}, \, i\in \mathcal{{I}}\}$, such that $\sum_{i \in \mathcal{{I}}} \pi_i P_i$ is equivalent to $\mathscr{P}$ for every probability mass function $\pi$ on $\mathcal{{I}}$ with $\pi_i > 0$ for all $i \in \mathcal{{I}}$.

In light of Lemma 1, we frequently refer to a collection of probability measures as being dominated, without specifying the dominating measure, which is understood to be either a probability measure, or not more generally, a $\sigma$-finite measure. Non-$\sigma$-finite measures are of no interest in this paper. Any finite or countably infinite collection of probability measures is dominated. Examples of undominated collections of probability measures on $(\mathbb R, \mathscr{B})$ are:

● $\{ \delta_\theta, \, \theta \in [0, 1]\}$, with $\delta_\theta$ the point mass on $(\mathbb R, \mathscr{B})$ that assigns probability one to $\{\theta\}$.

● $\{ P\colon P(B) = P(\{ \omega \colon -\omega \in B\}), \; \mbox{for all}\; B\in \mathscr{B}\}$.

Despite a contrary claim in ^[25], undominated collections are more often the exception than the rule in most applications commonly encountered in statistical inference and information theory.

7. If $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$, $P$ and $Q$ are said to be mutually singular or orthogonal, $P \perp Q$, if there exists an event $F\in \mathscr{F}$ with $P(F) = 0$ and $Q(F) = 1$.

8. If $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$, the coefficient of absolute discontinuity of $P$ relative to $Q$ is defined as

Note that

9. If $P \in {\mathscr{P}_{\!\!\mathcal{{A}}}}$ and $Q \in {\mathscr{P}_{\!\!\mathcal{{B}}}}$ (the set of probability measures defined on the measurable space $(\mathcal{{B}}, \mathscr{G})$), then $P \otimes Q$ denotes the product measure on the measurable space $(\mathcal{{A}} \times \mathcal{{B}}, \mathscr{F} \otimes \mathscr{G})$. The coefficient of absolute discontinuity for product probability measures is

In fact, equality holds in (2.8) since we can lower bound the left side replacing $\left[{P_{{{\mathtt{1}}}}} \otimes {Q_{{{\mathtt{1}}}}}\right] (A)$ by $\left[ {P_{{{\mathtt{1}}}}} \otimes {Q_{{{\mathtt{1}}}}}\right] (F\times G)$ for any $F\times G \subset A$.

10. If $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $P\ll Q$, then the Radon-Nikodym derivative (or density) of $P$ with respect to $Q$ is the Borel $\mathscr{F}$-measurable nonnegative function

such that any nonnegative Borel $\mathscr{F}$-measurable function $f\colon \mathcal{{A}} \to [0, \infty)$ satisfies the change of measure formula

11. If $(P, Q)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$, define——up to an event of zero $P+Q$——the support of $P$ relative to $Q$ as

where $\mathsf{μ}$ is any measure that dominates $\{ P, Q\}$, such as $P+Q$.

Lemma 2. For any $(P, Q)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$,

Proof. To verify (2.13), simply note that $P (\mathcal{{S}}_{P\|Q}^c) = \int 1\{ a\not\in \mathcal{{S}}_{P\|Q} \} \, \frac{\mathrm{d}P}{\mathrm{d}\mathsf{μ}} (a)\, \mathrm{d}\mathsf{μ}(a) = 0$ for any $\mathsf{μ} \gg \{P, Q\}$. To justify (2.14), we need to show that if $A \in \mathscr{F}$ with $Q(A) < Q(\mathcal{{S}}_{P\|Q})$, then $P(A) < 1$. If $G \in \mathscr{F}$ is such that $G \subset \mathcal{{S}}_{P\|Q}$ and $Q(G) > 0$, then

because $\mathsf{μ} (G) > 0$ and $\frac{\mathrm{d}P}{\mathrm{d}\mathsf{μ}} (a) > 0$ if $a\in G$. Since $Q (\mathcal{{S}}_{P\|Q} \cap A^c) \geq Q (\mathcal{{S}}_{P\|Q}) - Q (A) > 0$, we obtain $0 < P(\mathcal{{S}}_{P\|Q} \cap A^c) = P(A^c)$. □

12. Apart from their essential contribution in our framework, the concepts in Items 8 and 11 merit broader popularity in probability theory. For example, they lead to an elementary constructive proof (cf. the standard proof in [26, p. 135]) of the Lebesgue decomposition theorem: If $(P, Q)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$, there exist probability measures $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ such that ${P_{{{\mathtt{1}}}}} \ll Q$, ${P_{{{\mathtt{0}}}}} \perp Q$, and $P$ is the mixture

for some $\lambda \in [0, 1]$. First, observe that the constructions for the cases $P\ll Q$ and $P\perp Q$ are trivial: If $P\ll Q$, then $({P_{{{\mathtt{1}}}}}, \lambda) = (P, 1)$; if $P\perp Q$, then $({P_{{{\mathtt{0}}}}}, \lambda) = (P, 0)$. In the nontrivial case $P \not \ll Q$ and $P\not \perp Q$, we have

and the law of total probability yields, for any $A \in \mathscr{F}$,

So in (2.16), we have $\lambda = \Pi (P\, \|\, Q)$, ${P_{{{\mathtt{1}}}}} = P(\cdot \mid \mathcal{{S}}_{Q\|P}) \ll Q$, and ${P_{{{\mathtt{0}}}}} = P(\cdot \mid \mathcal{{S}}^c_{Q\|P}) \perp Q$.

13. The moment generating function and cumulant generating function of a $[-\infty, +\infty)$-valued random variable $U$ are defined, respectively, by

Note that $\lim_{t\downarrow 0} \Lambda_{U}(t)$ is either infinite or equal to $\log \mathbb{P} [ U > -\infty]$. If there exists $t_0 > 0$ such that $\Lambda_{U}(t) = \Lambda_{V}(t) < \infty$ for $t\in (0, t_0)$, then $U$ and $V$ have identical distributions (e.g., [27, p. 337]). Since $\Lambda_{U}(-t) = \Lambda_{-U}(t)$, $U$ and $V$ have identical distributions if $\Lambda_{U}(t) = \Lambda_{V}(t) < \infty$ for $t\in (-t_0, 0)$.

3.   Relative information

14. If $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $P\ll Q$, then the relative information of $P$ with respect to $Q$ is the Borel $\mathscr{F}$-measurable function

More generally, without requiring $P\ll Q$, if ρ is a probability (or $\sigma$-finite) measure which dominates $\{P, Q\}$, and the respective densities are denoted by $p = \frac{\mathrm{d}P}{\mathrm{d}\mathsf{ρ}}$ and $q = \frac{\mathrm{d}Q}{\mathrm{d}\mathsf{ρ}}$, then the (generalized) relative information is defined as

If $a \not\in \mathcal{{S}}_{P\|Q} \cup \mathcal{{S}}_{Q\|P}$, it is immaterial how to define $\imath_{P\|Q} (a)$. Therefore, any identity involving relative informations (or densities) is to be understood almost surely with respect to any measure dominating both probability measures. It follows from (3.2) that relative information satisfies the skew-symmetry property

In the discrete case, i.e., $\mathcal{{A}}$ is finite or countably infinite, if $P(a)+Q(a) > 0$, then

where the (absolute) information is $\imath_P (a) = \log \frac1{P(a)}$. The base of the logarithms in (3.1) and (3.2) determines the units of the relative information. Unless specifically indicated, it can be chosen by the reader. If the chosen base is $\mathrm{b} > 1$, then $\exp (t) = \mathrm{b}^t$. If $b = \mathrm{e}$ [resp., $2$], the unit is called nat [resp., bit]. By convention, $\exp (-\infty) = 0$ and $\log 0 = -\infty$. The generalized relative information in bits is equal to $\imath_{P\|Q} (a) = \upsilon (\imath_{P\|R} (a))$ where $R = \frac12 P + \frac12 Q$, $\imath_{P\|R} (a)$ is also in bits, and $\upsilon\colon[-\infty, 1] \to [-\infty, +\infty]$ is $\upsilon(t) = t - \log_2 (2 - 2^t)$.

15. If $a \in \mathcal{{A}}$, $(P, Q, R) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^3$ and $R$ dominates $\{P, Q\}$, then (3.2) implies the chain rule

16. Often (recall Item 2) we denote $X\sim P_X$ and $Y \sim P_Y$, in which case we abbreviate $\imath_{P_X\|P_Y}$ as $\imath_{X\|Y}$. The same convention applies to the coefficient of absolute discontinuity in Item 8 and the relative support in Item 11, as well as to relative entropy and other information measures (except total variation distance) considered in the remainder of the paper. This notational convention was popularized by ^[28] in the context of the entropy function.

17. It follows from (2.13), (2.14), and (3.2) that

18. Change of measure. Without the assumption of absolute continuity, the basic change of measure formula (2.11) needs to be modified as follows.

Lemma 3. For any nonnegative Borel measurable $f\colon \mathcal{{A}} \to [0, \infty)$,

regardless of whether the expectations are finite or $+\infty$. More generally, if $f\colon \mathcal{{A}} \to \mathbb R$, the random variable on the left side of (3.10) [resp., (3.13)] is integrable if and only if so is the random variable on the right side, in which case (3.10) [resp., (3.13)] holds.

Proof. Identities (3.11) and (3.14) follow from (3.7) and (3.8), respectively. Suppose that ρ dominates $\{P_X, P_Y\}$ and the respective densities are denoted by $p_X$ and $p_Y$. The random variable in the expectation on the left side of (3.10) is equal to zero if $Y \notin \mathcal{{S}}_{X\|Y} \cap \mathcal{{S}}_{Y\|X}$. Therefore, the left side of (3.10) equals

where we have used (3.2). If $P_X \ll P_Y$, then $\mathbb{P} [ \imath_{X\|Y} (X) \in \mathbb R ] = 1$, yielding (3.12). Alternatively, we can prove it directly from the change of measure formula (2.11). To show the claimed result for $f\colon \mathcal{{A}} \to \mathbb R$, we decompose $f = [f]^+ - [- f]^+$, and the desired result follows from the definition of expectation $\mathbb{E} [ f (V) ] = \mathbb{E} [ f^+ (V) ] - \mathbb{E} [ f^- (V) ]$ for any $V$ once we apply (3.10) to both $[f]^+$ and $[- f]^+$. Swapping $X\leftrightarrow Y$ and recalling (3.3) results in (3.13)–(3.15). □

Corollary 1. For any $\beta > 0$, and nonnegative measurable function $g\colon \mathcal{{A}} \to [0, \infty)$,

Proof.

● (3.17) $\Longleftarrow$ (3.10) with $f(a) = g(a)\, 1\{ \log \beta \leq \imath_{X\|Y} (a) \}$.

● (3.18) $\Longleftarrow$ (3.10) with $f(a) = g(a)\, 1\{ -\infty < \imath_{X\|Y} (a) \leq \log \beta \}$.

□

19. Invariance to labeling.

Lemma 4. Fix measurable spaces $(\mathcal{{A}}, \mathscr{F})$ and $(\mathcal{{B}}, \mathscr{G})$, and let the $(\mathscr{F}, \mathscr{G})$-measurable function $f\colon \mathcal{{A}} \to \mathcal{{B}}$ be injective. Then,

Conversely, if the $(\mathscr{F}, \mathscr{G})$-measurable function $g\colon \mathcal{{A}} \to \mathcal{{B}}$ is such that $\imath_{X\|Y} (a)$ depends on $a\in \mathcal{{A}}$ only through $g(a)$, then

Proof. Suppose that $P_Z$ dominates $\{P_X, P_Y\}$. Then,

where

● (3.21) and (3.23) $\Longleftarrow$ $1\{a \in A \} = 1\{ f(a) \in f(A)\}$ for any $A \in \mathscr{F}$ $\Longleftarrow$ $f$ is injective.

● (3.22) $\Longleftarrow$ Lemma 3 with $\varrho (a) = \exp(\imath_{f(X)\|f(Z)} (f(a)))$.

Therefore, $\varrho(a) = \frac{\mathrm{d}P_X}{\mathrm{d}P_Z} (a)$. In particular, $\mathcal{{S}}_{X\|Z} = \{ a\in \mathcal{{A}}\colon f(a) \in \mathcal{{S}}_{f(X)\|f(Z)} \}.$ If $P_X \ll P_Y$, we are done since we can just let $P_Z = P_Y$. Otherwise, we can follow the same reasoning with $X \leftarrow Y$, and (3.19) follows from (3.2). To show the converse part, assume for now that $P_X \ll P_Y$. Suppose that $\frac{\mathrm{d}P_X}{\mathrm{d}P_Y} (a) = \psi (g(a))$. Then, again invoking Lemma 3, we get

and, consequently, $\frac{\mathrm{d}P_{g(X)}}{\mathrm{d}P_{g(Y)}} (t) = \psi (t)$, which implies (3.20). Without assuming $P_X \ll P_Y$, note that $\imath_{X\|Y} (a) = \infty$ implies $a \in \mathcal{{S}}^c_{Y\|X} \subset g^{-1} \left(\mathcal{{S}}^c_{g(Y)\|g(X)} \right)$ and (3.24) continues to hold if $B \subset \mathcal{{S}}_{g(Y)\|g(X)}$. □

20. Relative information of relative informations.

Lemma 5. Let $(P_X, P_Y)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$. Define the extended-valued random variables $W = \imath_{X\|Y}(X)$ and $Z = \imath_{X\|Y}(Y)$. Then, using the same units for all three relative informations,

Proof. Since the relative information need not be an injective function, we cannot invoke Lemma 4. The probability of a Borel set $A \in \mathscr{B}$, $A \subset \mathbb R$ can be expressed as

where (3.27) follows from (3.10). Hence, we are free to choose $\frac{\mathrm{d}P_W}{\mathrm{d}P_Z} (a) = \exp (a)$ for all $a \in \mathbb R$. If $\Pi (X\|Y) = 1 = \Pi (Y\|X)$, i.e., $P_X \ll \gg P_Y$, then $\mathcal{{S}}_{W\|Z} \cup \mathcal{{S}}_{Z\|W} = \mathbb R$ and it is immaterial how to define $\imath_{W\|Z} (\infty)$ and $\imath_{W\|Z} (-\infty)$. If $\Pi (X\|Y) < 1 = \Pi (Y\|X)$, then Item 17 implies

so $\imath_{W\|Z} (\infty) = \infty$ and it is immaterial how to define $\imath_{W\|Z} (-\infty)$. The same reasoning shows that if $\Pi (X\|Y) = 1 > \Pi (Y\|X)$, then $\imath_{W\|Z} (-\infty) = -\infty$ and it is immaterial how to define $\imath_{W\|Z} (\infty)$. If $\Pi (X\|Y) < 1$ and $\Pi (Y\|X) < 1$, then Item 17 gives

which implies that $\imath_{W\|Z} (\infty) = \infty$ and $\imath_{W\|Z} (-\infty) = -\infty$. □

21. If $(P, Q)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$, $D(P\, \|\, Q)$ stands for the relative entropy (or Kullback-Leibler divergence ^[2]), which, with the convention in Item 16, satisfies

The binary relative entropy function is the continuous extension to the domain $[0, 1]^2$ of the function $d(p\, \|\, q) = p \log\frac{p}{q} + (1-p) \log\frac{1-p}{1-q}$. The data processing lemma for relative entropy implies

22. If $P_X \ll P_Y$, the change of measure formula (2.11) implies

Without assuming $P_X \ll P_Y$, we have

To verify (3.37) we let $f(a) = 1$ in (3.11) and recall (3.6). Swapping $X \leftrightarrow Y$ in (3.37) yields (3.38) in light of (3.3). The $\chi^2$-divergence introduced by Pearson in ^[16] is

where (3.40) holds if $P_X \ll P_Y$; otherwise, $\chi^2 (X \, \|\, Y) = \infty$.

23. For $(P_X, P_Y) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $\alpha \in (0, 1)\cup (1, \infty)$, the $\alpha$-order Rényi divergence ^[13] is

where (3.42) holds for $\alpha \in (0, 1)$. Equivalently, if $Z \sim R$, with $R$ a probability measure that dominates $\{P, Q\}$, then

which, using the generalized relative information (3.2), also holds without requiring that $R\gg \{ P, Q\}$. In addition, define

Along with (3.10) specialized to $f(a) = \exp \left((\alpha-1) \imath_{X\|Y} (a) \right)$, the skew-symmetry of relative information (3.3) results in the skew-symmetry of Rényi divergence

The coefficients of absolute discontinuity can be obtained from the Rényi divergence by means of

where (3.48) follows from (3.46) and (3.47). To show (3.47), note that

so the dominated convergence theorem implies that

which is equivalent to (3.47) in view of (3.38) and (3.41).

24. Section 8 shows a new operational role for the Bhattacharyya distance ^[29],

where $p = \frac{\mathrm{d}P}{\mathrm{d}\mathsf{μ}}$, $q = \frac{\mathrm{d}Q}{\mathrm{d}\mathsf{μ}}$ and $\{ P, Q\} \ll \mathsf{μ}$.

25. A couple of properties of Rényi divergence used in the sequel are (e.g., ^[30]):

(a) If $\alpha \geq 1$, then

(b) The following circular implications hold:

26. Given $P_X\in {\mathscr{P}_{\!\!\mathcal{{A}}}}$ and a random transformation $P_{Y|X} \colon (\mathcal{{A}}, \mathscr{F}) \to (\mathcal{{B}}, \mathscr{G})$, the following special case of relative information is known as the information density,

where $P_X \to P_{Y|X} \to P_Y$. We use the same notation in non-Bayesian settings in which $P_X$ need not be defined and $P_Y \in {\mathscr{P}_{\!\!\mathcal{{B}}}}$ on the rightmost term in (3.55) is an arbitrary unconditional probability measure. For future use, we observe that information density satisfies the chain rule

Note that mutual information is $I(X; Y) = \mathbb{E} [ \imath_{X; Y} (X; Y) ]$, with $(X, Y) \sim P_X P_{Y|X}$.

27. Following ^[31], whenever $P_{XY} \ll P_X \otimes P_Y$, the dependence between $X$ and $Y$ is said to be regular. The following result gives sufficient conditions for regularity.

Lemma 6. Fix $P_X \in {\mathscr{P}_{\!\!\mathcal{{A}}}}$ and a random transformation $P_{Y|X}\colon (\mathcal{{A}}, \mathscr{F}) \to (\mathcal{{B}}, \mathscr{G})$.

With $P_X \rightarrow P_{Y|X} \rightarrow P_Y$, the following hold.

Proof. To show (3.57) by contraposition, let $D\in \mathscr{F}\otimes \mathscr{G}$ be such that

and denote

The function $P_{Y|X = x} (D_x) = \mathbb{E} [ f(X, Y)|X = x]$ is Borel $\mathscr{F}$-measurable with mean

Therefore, there exists $A_1 \in \mathscr{F}$ with $P_X (A_1) > 0$ and $P_{Y|X = x} (D_x) > 0$ for all $x\in A_1$. Likewise, the expectation of the Borel $\mathscr{F}$-measurable $P_Y (D_x) = \mathbb{E} [ f(x, Y)]$, with $Y\sim P_Y$ is simply

Consequently, there exists $A_2 \in \mathscr{F}$ with $P_X (A_2) = 1$ and $P_{Y} (D_x) = 0$ for all $x\in A_2$. We conclude that $P_Y (D_x) = 0 < P_{Y|X = x} (D_x)$ and, thus, $P_{Y|X = x}\; \not \ll\; P_Y$, for all $x \in A_1 \cap A_2$ and $P_X (A_1 \cap A_2) > 0$. To show (3.58), we assume without loss of generality that $\{P_{Y|X = x} \, x\in \mathcal{{A}}\} \cup \{P_Y\}$ is dominated by $Q_Y \in {\mathscr{P}_{\!\!\mathcal{{A}}}}$. Denote by $p_{Y|X = x}$ and $p_Y$ the corresponding densities of $P_{Y|X = x}$ and $P_Y$ with respect to $Q_Y$, and define the Borel $(\mathscr{F}\otimes \mathscr{G})$-measurable function $f(x, y) = 1\{ p_Y (y) = 0\}\, p_{Y|X = x} (y)$. If $(X, Y, \widehat{Y}) \sim P_{XY} \otimes Q_Y$, then

where $f_1 (x) = \mathbb{E} [ f(x, \widehat{Y})] = \int 1\{ p_Y (y) = 0\}\, \mathrm{d} P_{Y|X = x} (y)$ and (3.65) follows from Fubini's theorem. The proof of (3.58) is complete since $f_1(x) = 0$ if and only if $P_{Y|X = x} \ll P_Y$. □

4.   Relative information spectra

In Items 21 and 22, we saw that the expectations of the random variables $\imath_{X\|Y} (X)$ and $\imath_{X\|Y} (Y)$, as well as their exponentials, are well-known quantities in probability theory. We now consider the cumulative distribution functions of those $[-\infty, +\infty]$-valued random variables, which, unlike relative entropy, $\chi^2$-divergence, or total variation distance, capture everything that serves to distinguish the probability measures $P_X$ and $P_Y$.

28. Definition 1. The relative information spectra of probability measures $(P_X, P_Y)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ are the cumulative distribution functions of the relative information evaluated at $X$ and $Y$, respectively,

The arguments of $\mathbb{F}_{X\|Y}$ and $\bar{ \mathbb{F}}_{X\|Y}$ have units inherited by the units of the relative information. In ^[22], the relative information spectra are referred to as divergence spectra.

29. If $X$ and $Y$ are discrete random variables, so are $\imath_{X\|Y} (X)$ and $\imath_{X\|Y} (Y)$. If $X$ and $Y$ are absolutely continuous random variables with probability density functions $f_X$ and $f_Y$, then

which need not be continuous.

30. Due to (3.6)–(3.9),

Although (4.5) is less than 1 if $P_X \not \ll P_Y$ and (4.8) is positive if $P_Y \not \ll P_X$, the relative information spectra are monotonically increasing and right-continuous.

31. As a result of the skew-symmetry (3.3) of the relative information,

32. If $P_X = P_Y$, then ${ \mathbb{F}}_{X\|Y} (\alpha) = \bar{ \mathbb{F}}_{X\|Y} (\alpha) = 1\{\alpha \geq 0\}$.

If $P_X \perp P_Y$, then $\mathbb{F}_{X\|Y} (\alpha) = 0$ and $\bar{ \mathbb{F}}_{X\|Y} (\alpha) = 1$ for all $\alpha \in \mathbb R$.

Lemma 7. Let $(P_X, P_Y) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$. Then,

(a) $P_X \neq P_Y$ $\Longleftrightarrow$ ${ \mathbb{F}}_{X\|Y} (0) < 1$.

(b) If, in addition, $P_X \ll P_Y$, then $P_X \neq P_Y$ $\Longleftrightarrow$ $\bar{ \mathbb{F}}_{X\|Y} (0) < 1$.

Proof.

(a) ${ \mathbb{F}}_{X\|Y} (0) = 1\, \, \Longrightarrow\, \, 0 = \mathbb{E} [ [\imath_{X\|Y} (X)]^+] \geq D(X\, \| \, Y)\, \, \Longrightarrow\, \, P_X = P_Y.$

(b) For any $\alpha > 0$,

where

● (4.11) $\Longleftarrow$ (4.10) with $X \leftrightarrow Y$.

● (4.12) $\Longleftarrow$ (3.12) with $f(a) = 1\{ \imath_{Y\|X} (a) < 0 \} \, \exp (- \imath_{X\|Y} (a))$.

● (4.15) $\Longleftarrow$ (3.3).

On account of (a), (2.5), and (4.5), $\lim_{\gamma \to \infty} { \mathbb{F}}_{X\|Y} (\gamma) = 1 > { \mathbb{F}}_{X\|Y} (0)$. Therefore, there must exist $\alpha > 0$ such that $\mathbb{P} [0 < \imath_{X\|Y} (X) < \alpha ] > 0$.

An example of $P_X \neq P_Y$ with $\bar{ \mathbb{F}}_{X\|Y} (0) = 1$ is $P_X = [\frac12 \; \; \frac12]$, $P_Y = [1 \; \; 0]$. □

33. Example: If $X\sim \mathcal{N}\!\left({{\mu}}, {{\sigma^2}}\right)$, $Y\sim \mathcal{N}\!\left({{0}}, {{\sigma^2}}\right)$, and $\mathrm{Q} (t) = \int_t^\infty \frac1{\sqrt{2 \pi}} \mathrm{e}^{-x^2/2} \mathrm{d}x$, then, with $\alpha$ in nats,

34. Example: Let $\xi = \tfrac12 \log_\mathrm{e} \frac{\sigma_X^2}{\sigma_Y^2}$, with $\sigma_X^2 > \sigma_Y^2 > 0$, $X\sim \mathcal{N}\!\left({{0}}, {{\sigma_X^2}}\right)$, and $Y\sim \mathcal{N}\!\left({{0}}, {{\sigma_Y^2}}\right)$. If $\alpha > - \xi$, then

while $\mathbb{F}_{X\|Y} (\alpha) = \bar{ \mathbb{F}}_{X\|Y} (\alpha) = 0$ if $\alpha \leq -\xi$.

35. Example: ^[24] Suppose that $V$ is standard Cauchy, $\lambda_0 \lambda_1 \neq 0$, $X_1 = \lambda_1 V + \mu_1$, and $X_0 = \lambda_0 V + \mu_0$. Then, $\bar{ \mathbb{F}}_{X_1\|X_0} (\alpha) = 1 - { \mathbb{F}}_{X_1\|X_0} (-\alpha)$ and

36. Example: Suppose that $U$ is uniform on $[0, 1]$. Define the probability measures on $(\mathbb R, \mathscr{B})$,

Then, $\Pi ({P_{{{\mathtt{1}}}}}\, \|\, {P_{{{\mathtt{0}}}}}) = \frac34$, $\Pi ({P_{{{\mathtt{0}}}}}\, \|\, {P_{{{\mathtt{1}}}}}) = \frac49$, and

37. A key aspect of the relative information spectra is that ${ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ determine each other through the following result.

Theorem 1. Fix arbitrary $(P_X, P_Y) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$.

(a) For all $\beta > 0$,

(b) For all $\beta > 0$,

(c) For all $\beta > 0$,

(d) $\imath_{X\|Y}(X) \in (-\infty, +\infty]$ is discrete if and only if $\imath_{X\|Y}(Y)\in [-\infty, +\infty)$ is discrete. $\imath_{X\|Y}(X)$ is absolutely continuous, except for a possible mass at $+\infty$, if and only if $\imath_{X\|Y}(Y)$ is absolutely continuous, except for a possible mass at $-\infty$. Then, the density functions $f_{X\|Y}(x) = \frac{\mathrm{d}}{\mathrm{d}x} \mathbb{F}_{X\|Y}(x)$ and $\bar{f}_{X\|Y} (x) = \frac{\mathrm{d}}{\mathrm{d}x}\bar{ \mathbb{F}}_{X\|Y}(x)$ satisfy

(e)

(f) If $g\colon \mathbb R \to [0, \infty)$, then

(g) The cumulant generating functions of $\imath_{X\|Y} (X)$ and $\imath_{X\|Y} (Y)$ (nats) satisfy

and $\Lambda_{\imath_{X\|Y} (X)} (-1) = \log_{\mathrm{e}} \Pi (Y \| X)$ and $\Lambda_{\imath_{X\|Y} (Y)} (1) = \log_{\mathrm{e}} \Pi (X \| Y)$.

Proof.

(a) Fix $\alpha \in \mathbb R$ and let $P_Z$ dominate $\{P_X, P_Y\}$. Then,

where

● (4.38) $\Longleftarrow$ $\exp(-\infty) = 0$.

● (4.39) $\Longleftarrow$ (3.2) and the random variable in the expectation in the left side can be positive only if $X \in \mathcal{{S}}_{X\|Y} \cap \mathcal{{S}}_{Y\|X}$.

● (4.40) and (4.41) $\Longleftarrow$ change of measure (2.11).

● (4.42) $\Longleftarrow$ (3.8).

Then, we have

where

● (4.43) $\Longleftarrow$ (4.38)–(4.42).

● (4.44) $\Longleftarrow$ $\mathbb{E} [ T] = \int_0^1 \mathbb{P} [T \geq \tau ] \, \mathrm{d}\tau$ if $T\in [0, 1]$.

Rearranging the outer terms in (4.43)–(4.45) with $\alpha = \log \beta$ and changing the integration variable to $t = \frac{\tau}{\beta}$ yields (4.23).

(b) Denote $V = \exp (\imath_{X\|Y} (Y))$. By change of measure on $\mathcal{{S}}_{X\|Y} \cap \mathcal{{S}}_{Y\|X}$, we obtain

(c) $\Longleftarrow$ (3.10) with $f(a) = 1\{\imath_{X\|Y} (a) = \log \beta\}$.

(d) Lemma 5 implies that, when restricted to $\mathbb R$, the probability measures of $W$ and $Z$ are mutually absolutely continuous; therefore, one is discrete [resp., absolutely continuous] if and only if the other one is discrete [resp., absolutely continuous]. Differentiating (4.23) with respect to $t$ yields (4.26).

● (4.27) and (4.31) are (3.9) and (3.6), respectively.

● (4.28) and (4.32) are (3.38) and (3.37), respectively.

● (4.29) $\Longleftarrow$ (4.8) and (4.23).

● (4.33) $\Longleftarrow$ (4.5) and (4.24).

● (4.30) and (4.34) are (4.28) and (4.32), respectively, since those expectations are unchanged when restricted to $\imath_{X\|Y} (X) \in \mathbb R$ and $\imath_{X\|Y} (Y) \in \mathbb R$.

(f) $\Longleftarrow$ Lemma 3 with $f(a) = g\left(\imath_{X\|Y} (a) \right)$.

Note that the left sides of (3.10) and (3.13) are unchanged if the random variables inside the expectations are multiplied by $1\{\imath_{X\|Y} (Y) \in \mathbb R\}$ and $1\{\imath_{X\|Y} (X) \in \mathbb R\}$, respectively.

(g) The formulas for $\Lambda_{\imath_{X\|Y} (X)} (-1)$ and $\Lambda_{\imath_{X\|Y} (Y)} (1)$ follow from (4.28) and (4.32), respectively. In addition to $\Lambda_{\imath_{X\|Y} (X)} (0) = 0 = \Lambda_{\imath_{X\|Y} (Y)} (0)$, the following expressions ($\infty \cdot 0 = 0$) for the moment generating functions at $t \notin \{0, -1\}$ yield (4.37):

□

38. In this item and the next, we upper bound ${ \mathbb{F}}_{X\|Y}$ in terms of $\bar{ \mathbb{F}}_{X\|Y}$.

Lemma 8. For $\beta > 0$,

Proof. Let $L_\beta = \{a \in \mathcal{{A}}\colon \imath_{X\|Y} (a) \leq \log \beta\}$.

● (4.53) $\Longleftarrow$ (3.11) with $f(a) = 1\{a \in L_\beta\}$.

● (4.54) is Lemma 4.1.2 in ^[22]. $P_X (L_\beta) \leq P_X (B^c) + P_X (L_\beta \cap B) \leq P_X (B^c) + \beta\, P_Y (B),$ where the second inequality follows from (3.18) with $g(a) = 1\{a\in B\}$.

● (4.55) $\Longleftarrow$ (4.54) with the suboptimal choice $B = L_\beta$.

● (4.56) $\Longleftarrow$ (4.24) and for $t > 0$, $\bar{ \mathbb{F}}_{X\|Y} (\log t) \geq \lim_{\tau \to 0} \bar{ \mathbb{F}}_{X\|Y} (\log \tau) = 1 - \Pi (Y\|X)$.

● (4.53) $\Longleftarrow$ $\max\{ \bar{ \mathbb{F}}_{X\|Y} (\log \beta), \Pi (Y\| X)\} \leq 1$.

● (4.57) $\Longleftarrow$ (3.6), (4.25), and (3.17) with $g(a) \leftarrow 1$.

● (4.58) $\Longleftarrow$ $\left(1 - \frac1{\beta}\right) { \mathbb{F}}_{X\|Y} (\log \beta) \leq 1 - \frac1{\beta} < \mathrm{e}^{-\frac1\beta}$ and upper bound $\frac1{\beta} { \mathbb{F}}_{X\|Y} (\log \beta)$ by means of (4.56).

□

39. The following bound is instrumental in hypothesis testing (Section 8).

Lemma 9. Let $(P_X, P_Y)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$. For any $\beta > 0$, and measurable function $g\colon\mathcal{{A}} \to [0, 1]$,

Proof. For all $a\in \mathcal{{A}}$, $\beta > 0$, and measurable function $g\colon\mathcal{{A}} \to [0, 1]$,

because when the first factor is positive [resp., negative], then the second factor is $1-g(a)$ [resp., $-g(a)$]. Averaging (4.60) with respect to $a\leftarrow Y$, we obtain (4.59) invoking (3.10) twice with $f(a) \leftarrow 1\{\imath_{X\|Y} (a) \leq \log \beta\}$ and $f(a) \leftarrow g(a)$, respectively, where in the second case the nonnegativity of $g$ yields $\mathbb{E} [ g(X) 1\{\imath_{X\|Y} (X) \in \mathbb R \}] \leq \mathbb{E} [ g(X)]$. □

40. Definition 2. $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{B}}}}^2$ are said to be equivalent pairs, denoted as $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \equiv ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$, if

i.e., $\frac{\mathrm{d}{P_{{{\mathtt{1}}}}}}{\mathrm{d}{P_{{{\mathtt{0}}}}}} ({X_{{{\mathtt{1}}}}})$ and $\frac{\mathrm{d}{Q_{{{\mathtt{1}}}}}}{\mathrm{d}{Q_{{{\mathtt{0}}}}}} ({Y_{{{\mathtt{1}}}}})$ are identically distributed when ${X_{{{\mathtt{1}}}}} \sim {P_{{{\mathtt{1}}}}}$ and ${Y_{{{\mathtt{1}}}}} \sim {Q_{{{\mathtt{1}}}}}$.

A word of caution is that a different notion of equivalence for pairs of real-valued random variables (not pairs of probability measures) was proposed by Halmos and Savage in ^[3]: Suppose $(X_1, Y_1, X_2, Y_2)$ are real-valued random variables such that $\mathbb{P} [ X_i = Y_i = 0] = 0$, $i = 1, 2$; then $(X_1, Y_1)$ and $(X_2, Y_2)$ are equivalent in the sense of ^[3], if there is a fifth random variable such that $\mathbb{P} [F = 0] = 0$ and $\mathbb{P}[ (X_1, Y_1) = (F \cdot X_2, F\cdot Y_2)] = 1$.

41. Definition 2 and Theorem 4.1 result in

The remainder of the section is devoted to finding necessary and sufficient conditions for the equivalence of pairs. The relevance of such conditions will be apparent in Section 7.

42. In view of (4.9) and the fact that the relative information spectra are right-continuous, (4.62)–(4.63) imply

However, $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \equiv ({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})$ is more the exception than the rule. In addition to $\mathbb R^n$-valued random variables that differ by a constant, one of the most notable cases satisfying this property is the Cauchy case described in Item 35.

43. Theorem 4.2. For $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{B}}}}^2$, the following circular implications hold:

Proof. If $D_\alpha ({P_{{{\mathtt{1}}}}}\, \|\, {P_{{{\mathtt{0}}}}}) = D_\alpha ({Q_{{{\mathtt{1}}}}}\, \|\, {Q_{{{\mathtt{0}}}}}) = \infty$ for some $\alpha < 1$, then (4.65) follows from Item 25-(b) since ${P_{{{\mathtt{1}}}}} \perp {P_{{{\mathtt{0}}}}}$ and ${Q_{{{\mathtt{1}}}}} \perp {Q_{{{\mathtt{0}}}}}$ implies $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \equiv ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$. If $D_\alpha ({P_{{{\mathtt{1}}}}}\, \|\, {P_{{{\mathtt{0}}}}}) = D_\alpha ({Q_{{{\mathtt{1}}}}}\, \|\, {Q_{{{\mathtt{0}}}}}) < \infty$ for $0 < \alpha < \alpha_1 < 1$, recall from (3.42) that $(\alpha-1) D_\alpha (X\| Y) = \Lambda_{\imath_{X\|Y} (Y)} (\alpha)$ (assuming nats for convenience). Then, Item 13 implies that the values of $D_\alpha (X\| Y)$ in a neighborhood of the origin determine the function $\bar{ \mathbb{F}}_{X\|Y}$; therefore, (4.63) yields (4.65). On account of (3.41), we have

which shows (4.66) for $\alpha \in (0, 1)\cup (1, \infty)$. For $\alpha = 1$, we recall the definition of relative entropy, or, equivalently,

For $\alpha = \infty$, note that according to (3.45), $D_\infty (P\, \|\, Q) = \inf\{ v \in \mathbb R \colon \mathbb{F}_{P\|Q} (v) = 1 \}$. □

44. The following concentration bound for the relative information spectrum holds as a function of the Rényi divergence of order $\alpha > 1$: If $\delta > 0$, then

To verify (4.69), let $L_\beta = \{a \in \mathcal{{A}}\colon \imath_{P\|Q} (a) \leq \log \beta\}$, and $X\sim P$. Then,

on account of (3.43). Letting $\log \beta = \delta + D_\alpha (P\, \|\, Q)$ yields (4.69).

45. Let $\mathtt{F}$ be the collection of convex functions $f\colon(0, \infty) \to \mathbb R$. For $f\in \mathtt{F}$, the $f$-divergence, introduced and shown to satisfy the data processing principle in ^[15,32,33], can be expressed in terms of the relative information spectrum as

where $f(0) = \lim_{t\downarrow 0} f(t)$ and $f^\dagger (0) = \lim_{t\downarrow 0} t \, f \left(\frac1t \right)$. Other integral representations of $f$-divergence as a function of the relative information spectrum, the deGroot statistical information (Item 48), and the $E_\gamma$-divergence (Item 49), can be found in ^[34], ^[35], and ^[36], respectively.

46. Lemmas 10 and 11 are used in Section 6 to show that the NP-divergence is not an $f$-divergence.

Lemma 10. [37, (9.4)] Suppose that the convex functions $f\colon (0, \infty) \to \mathbb R$ and $g\colon (0, \infty) \to \mathbb R$ are such that $D_f (P\, \|\, Q) = D_g (P\, \|\, Q)$ for all $(P, Q)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$, where $|\mathcal{{A}}| = 2$. Then, $f(t)-g(t) = \alpha \, t - \alpha$ for some $\alpha \in \mathbb R$.

Csiszár showed in [38, Theorem 1] that a discrepancy measure that satisfies the data processing inequality and the property in Lemma 11 must be an $f$-divergence.

Lemma 11. Whenever $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}, {Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^4$ are such that there exists an event $\mathcal{{A}}_{\mathtt{0}} \in \mathscr{F}$ such that ${Q_{{{\mathtt{0}}}}}(\mathcal{{A}}_{\mathtt{0}}) = 1 = {P_{{{\mathtt{0}}}}}(\mathcal{{A}}_{\mathtt{0}})$ and ${Q_{{{\mathtt{1}}}}}(\mathcal{{A}}_{\mathtt{0}}) = 0 = {P_{{{\mathtt{1}}}}}(\mathcal{{A}}_{\mathtt{0}})$,

for all $\lambda\in [0, 1]$ and $f\in \mathtt{F}$.

Proof. Denoting the corresponding densities with respect to a common dominating $\sigma$-finite measure $\mathsf{μ}$ by $p_{\mathtt{0}}$, $p_{\mathtt{1}}$, $q_{\mathtt{0}}$, and $q_{\mathtt{1}}$, we have $p_{\mathtt{0}} (x) = q_{\mathtt{0}} (x) = 0$ if $x \not\in \mathcal{{A}}_{\mathtt{0}}$ and $p_{\mathtt{1}} (x) = q_{\mathtt{1}} (x) = 0$ if $x \in \mathcal{{A}}_{\mathtt{0}}$. Furthermore, we can express the densities of the mixtures by $p_\lambda = \lambda \, p_{\mathtt{1}} + (1 - \lambda) p_{\mathtt{0}}$, and $q_\lambda = \lambda \, q_{\mathtt{1}} + (1 - \lambda) q_{\mathtt{0}}$, respectively. Then, with the usual conventions $0 \cdot f \left(\frac{p}{0} \right) = p \, f^\dagger (0)$ if $p \geq 0$, and $f(0) \cdot 0 = f^\dagger(0) \cdot 0 = 0$,

□

47. The convex functions

result in an important special case of $f$-divergence known as the Hellinger divergence of order $\alpha\in (0, 1)\cup(1, \infty)$,

which use the same notation as in (3.2) and (3.43). Furthermore, we let $\mathscr{H}_1 (P \, \|\, Q) = D(P \, \|\, Q)$. The squared Hellinger distance is

with $B (P \, \| \, Q)$ defined in Item 24, and $f(t) = 1 -\sqrt{t}$ or $f(t) = \frac12 (1 - \sqrt{t})^2$.

Theorem 3. For $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{B}}}}^2$, the following circular implications hold:

Proof.

● (4.82) $\Longleftarrow$ (4.65) because although Rényi divergence is not an $f$-divergence, it can be put in a one-to-one correspondence with $\mathscr{H}_\alpha (P \, \|\, Q)$ by means of

in light of (3.43) and (4.79).

● (4.83) $\Longleftarrow$ (4.73).

□

48. For $p\in (0, 1)$, the deGroot statistical information ^[20] is defined as the $\phi_p$-divergence

with the convex function $\phi_p\colon (0, \infty) \to (-1, \frac12)$,

Theorem 4. For $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{B}}}}^2$,

Proof. $\Longrightarrow$ follows from (4.83). To show $\Longleftarrow$, we use the fact that as long as $f$ is convex and twice differentiable, the $f$-divergence can be expressed as ^{[34,39,40,41]}

Therefore, $\{ \mathcal{I}_p({P_{{{\mathtt{1}}}}}\, \|\, {P_{{{\mathtt{0}}}}}) = \mathcal{I}_p({Q_{{{\mathtt{1}}}}}\, \|\, {Q_{{{\mathtt{0}}}}}), \, p\in (0, 1) \} \Longrightarrow D_f ({P_{{{\mathtt{1}}}}}\, \|\, {P_{{{\mathtt{0}}}}}) = D_f({Q_{{{\mathtt{1}}}}}\, \|\, {Q_{{{\mathtt{0}}}}})$. Since (4.78) is convex and twice differentiable, $\Longleftarrow$ in (4.87) follows from (4.82). Alternatively, we can invoke the representation of the relative information spectrum in [34, Theorem 4]:

and $\mathbb{F}_{P\|Q} (0) = \lim_{\alpha \downarrow 0} \mathbb{F}_{P\|Q} (\alpha)$. □

49. For $\gamma \geq 1$, denote $g_\gamma (t) = [ t - \gamma ]^+$, and define the $E_\gamma$ divergence as the $g_\gamma$-divergence

Theorem 5. For $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{B}}}}^2$,

Proof.

$\Downarrow$ We can invoke (4.64) and either (4.83) or the representation in [34, (112)],

$\Uparrow$ We can rely on Theorem 4 and

Alternatively, we can capitalize on Theorem 3 of ^[34], namely,

□

50. The fact (stated in Item 45) that no random transformation can increase the $f$-divergence between a pair of input probability measures suggests the possibility that the input relative information may stochastically dominate the output relative information. In other words, is it true that

for all $P_{Y|X}\colon \mathcal{{A}} \to \mathcal{{B}}$ and $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$, with ${P_{{{\mathtt{0}}}}} \to P_{Y|X} \to {Q_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}} \to P_{Y|X} \to {Q_{{{\mathtt{1}}}}}$? There are indeed cases in which (4.95) not only holds but holds with strict inequality on an interval of the real line. For example, if $Y$ is independent of the input, then $\mathbb{F}_{{Q_{{{\mathtt{1}}}}}\|{Q_{{{\mathtt{0}}}}}} (x) = 1\{x \geq 0\}$ while $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (x) = 1\{x \geq 1\, \mbox{bit}\}$ if ${P_{{{\mathtt{1}}}}} = [0 \; \; 1], {P_{{{\mathtt{0}}}}} = [\frac12 \; \; \frac12]$. However, as long as ${P_{{{\mathtt{0}}}}} \ll {P_{{{\mathtt{1}}}}}$, it is impossible for (4.95) to hold and be strict in any interval because that would mean

where (4.97) and (4.99) follow from (4.33). Therefore, we reach the contradiction that a coefficient of absolute discontinuity is strictly greater than 1.

5.   Total variation distance

In this section we turn our attention to the interplay between the relative information spectra and total variation distance

51. Theorem 6. The total variation distance between $(P_X, P_Y)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ can be expressed in terms of the relative information spectra through

where the relative information in (5.13) is in nats and $\tanh (\pm \infty) = \pm 1$.

Proof.

● (5.2) Let $\mathcal{{A}}_+ = \{ a\in \mathcal{{A}}\colon \imath_{X\|Y} (a) > 0 \}$. Then,

a) $P_X(\mathcal{{A}}_+) - P_Y(\mathcal{{A}}_+) = \bar{ \mathbb{F}}_{X\|Y} (0) - \mathbb{F}_{X\|Y} (0)$;

b) the absolute value in (5.1) is superfluous $\Longleftarrow$ $P_X(A) - P_Y(A) = P_Y(A^c) - P_X(A^c)$;

c) $\mathcal{{A}}_+$ achieves the maximum in (5.1) because for any $E\in \mathscr{F}$,

● (5.3) $\Longleftarrow$ (4.24) with $\beta = 1$.

● (5.4) $\Longleftarrow$ (4.23) with $\beta = 1$.

● (5.5) $\Longleftarrow$ its right side is the right side of (5.3) $\Longleftarrow$ (4.33).

● (5.6) Let $\mathsf{μ}$ dominate $\{P_X, P_Y\}$ and let $p_X = \frac{\mathrm{d}P_X}{\mathrm{d}\mathsf{μ}}$ and $p_Y = \frac{\mathrm{d}P_Y}{\mathrm{d}\mathsf{μ}}$. Then,

where we have used (3.9).

● (5.7) Swapping $X \leftrightarrow Y$ in (5.17),

where we have used (3.6).

● (5.8) $\Longleftarrow$ its right side is the arithmetic mean of the right sides of (5.6) and (5.7).

● (5.9) $\Longleftarrow$ $X \leftrightarrow Y$ in (5.8) and (3.3).

● (5.10) $\Longleftarrow$ $X \leftrightarrow Y$ in (5.6) and (3.3).

● (5.11) $\Longleftarrow$ $X \leftrightarrow Y$ in (5.7) and (3.3).

● (5.12) $\Longleftarrow$ its right side is the right side of (5.4) $\Longleftarrow$ (4.29).

● (5.13) $\Longleftarrow$ choose $\mathsf{μ} = \frac12 P_X + \frac12 P_Y$ in $|P_X - P_Y | = \int \left| p_X - p_Y \right| \, \mathrm{d}\mathsf{μ}$ and note that

□

52. Under the assumption $P_X \ll P_Y$, several of the representations in Theorem 6 can be found in [36, Theorem 12] and earlier in ^[42]. In addition, [36, Theorem 15] gives upper bounds on total variation distance as a function of the relative information spectrum if $P_X \ll P_Y$. Since those results are based on (5.3)–(5.4), which continue to hold in general, they too hold without restrictions on absolute continuity. In particular, the monotonicity of the relative information spectra and (5.3)–(5.4) result in

which coincide with Le Cam's upper bounds in [19, p. 51], except that he weakens (5.27) by forbidding $\delta > \log 2$. As noted in ^[36], further strengthening of (5.26) [resp., (5.27)] is possible if $\bar{ \mathbb{F}}_{X\|Y} (-\Delta) ] = 0$ [resp., ${ \mathbb{F}}_{X\|Y} (\Delta) ] = 0$] for some $\Delta > 0$.

53. We can also lower bound total variation distance using Theorem 6 and the monotonicity of the relative information spectra. The following result supersedes Le Cam's lower bound in [19, p. 50], as well as the lower bounds in [36, Lemmas 17 and 18] claimed under $P_X \ll P_Y$.

Theorem 7. For arbitrary $(P_X, P_Y) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ and $\delta > 0$,

Proof.

● (5.28) $\Longleftarrow$ (5.4) and ${ \mathbb{F}}_{X\|Y}(t) \leq \Pi (X\|Y) \, 1\{ t\geq \delta\} + (1 - \mathbb{P} [ \imath_{X\|Y} (X) \geq \delta])\, 1\{ t < \delta\}$.

● (5.29) $\Longleftarrow$ (5.12) and ${ \mathbb{F}}_{X\|Y}(t) \geq { \mathbb{F}}_{X\|Y}(- \delta) \, 1\{t \geq -\delta\}$.

● (5.30) $\Longleftarrow$ $X \leftrightarrow Y$ in (5.29) and (4.9).

● (5.31) $\Longleftarrow$ $X \leftrightarrow Y$ in (5.28) and (4.10).

□

54. Even if $P_{X_1}\in {\mathscr{P}_{\!\!\mathcal{{A}}}}$ and $P_{X_2}\in {\mathscr{P}_{\!\!\mathcal{{A}}}}$ are close in total variation distance, their relative informations with respect to a third probability measure may behave quite differently.

Example. [19, p. 50]. Let $\mathcal{{A}} = [0, \infty)$, and suppose that $P_{X_1}$, $P_{X_2}$, and $P_Y$ are uniform on $[0, n^2]$, $[1, n^2]$, and $[0, 1]$, respectively. Then, for all $\alpha \in \mathbb R$,

6.   NP-divergence

55. The NP-divergence between $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$ is defined as

The terminology is motivated by an important operational role for $S (P \, \| \, Q)$ shown in Section 8 in the context of non-Bayesian hypothesis testing. For now, we point out that NP-divergence satisfies a simple Bayesian hypothesis testing operational role. Recall that the minimum average probability of error is equal to $\frac12 - \frac14 | P - Q|$ for equally likely $P$ and $Q$. Now, suppose that we obtain a pair of observations one drawn from $P$ and the other from $Q$, but we do not know the order of the pair and have no reason to favor one ordering over the other. Therefore, we have the equally likely hypotheses

and the minimum probability of erroneous ordering is $\frac12 - \frac14 S (P \, \| \, Q)$.

56. Blind wine tasting. Offered a glass of 1982 Château Pétrus and a glass of 1990 Château Margaux, we are asked to identify which one is which. Suppose that for a given set of environmental conditions (temperature, lighting, etc.), $P$ and $Q$ stand for the probability measures of the respective wines on the space of visual, olfactory, and gustatory sensations. The probability of error is equal to $\frac12 - \frac14 S (P \, \| \, Q)$ since, a priori, the contents of the glasses are equally likely. Wanting to show off, a confident wine connoisseur makes a decision on the basis of tasting only one of the glasses. Then, the probability of error is $\frac12 - \frac14 | P - Q |$. Indeed, as shown below, $| P - Q | \leq S (P \, \| \, Q).$ If we do not condition on a given set of environmental conditions, the tasting sensations of both wines are dependent mainly because of their dependence on temperature. In that case, $S (P \, \| \, Q)$ is generalized to $|P_{XY} - P_{YX}|$, which can be applied whenever $X$ and $Y$ are defined on the same space. The potential utility of such measure of asymmetry of joint probability measures is yet to be explored.

57. Example. If $P = [\, p\; \; 1-p\, ]$ and $Q = [\, q\; \; 1-q\, ]$, then $S \left(P \, \|\, Q\right) = \left| P -Q \right| = 2 \, |p-q|$.

58. Example. If $P = \left[\, \frac12\; \frac12\; 0\, \right]$ and $Q = \left[\, 0\; \frac12\; \frac12\, \right]$, then $|P - Q| = 1$ while $S(P\, \|\, Q) = \frac{3}{2}$.

59. Example. $S \left(\mathcal{N}\!\left({{\mu_1}}, {{\sigma^2}}\right) \, \|\, \mathcal{N}\!\left({{\mu_0}}, {{\sigma^2}}\right) \right) = 2 - 4 \, \mathrm{Q} \left(\frac{|\mu_1 - \mu_0 |}{\sqrt{2} \sigma} \right) = \left| \mathcal{N}\!\left({{\mu_1}}, {{\frac{\sigma^2}{2}}}\right) - \mathcal{N}\!\left({{\mu_0}}, {{\frac{\sigma^2}{2}}}\right) \right|.$

60. The NP-divergence satisfies the following properties.

Theorem 8. Let $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$. Then,

(a) $S(P\, \|\, Q) = S(Q\, \|\, P)$.

(b)

with equality on the left if and only if $P = Q$, and equality on the right if and only if $P \perp Q$.

(c) $S (P\, \|\, Q)$ does not satisfy the triangle inequality.

(d)

(e) If $P \neq Q$, then

where $B(P\| Q)$ is the $\textrm{Bhattacharyya distance}$ in Item 24.

(f) If $|\mathcal{{A}}| = 2$, then $S (P\, \| \, Q) = | P - Q |$. In general,

$(g)$

(h) Data processing inequality. If $P_{{X_{{{\mathtt{1}}}}}} \to P_{Y|X} \to P_{{Y_{{{\mathtt{1}}}}}}$ and $P_{{X_{{{\mathtt{0}}}}}} \to P_{Y|X} \to P_{{Y_{{{\mathtt{0}}}}}}$, for some random transformation $P_{Y|X}\colon \mathcal{{A}} \to \mathcal{{B}}$, then

(i) No convex $f\colon (0, \infty) \to \mathbb R$ exists so that $D_f (P\, \|\, Q) = S (P\, \|\, Q)$ for all $(P, Q) \in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$.

(j) With $(X, Y) \sim P_X \otimes P_Y$,

(k)

Proof.

(a) $\Longleftarrow$ $|P - Q | = |Q -P|$.

(b) The inequalities follow because $S(P\|Q)$ is a total variation distance. Moreover,

(c) $P = \left[\, \frac12\; \frac12\; 0 \, \right]$, $Q = \left[\, \frac13\; \frac13\; \frac13\, \right]$, $R = \left[\, 0\; \frac12\; \frac12\, \right]$. Then, $S(P\|Q) + S(Q\|R) < S(P\|R)$, since

(d) Total variation distance satisfies the tensorization bound

Letting $(P_{X_i}, Q_{X_i}) \leftarrow (P_{X_i} \otimes Q_{X_i}, Q_{X_i} \otimes P_{X_i})$ yields (6.3).

(e) The proof consists of three building blocks:

ⅰ. As shown by Chernoff ^[14], if $P \neq Q$,

where the Chernoff information is defined as

ⅱ. By relabeling of indices,

ⅲ.

according to (3.51). To show that equality holds in (6.19), note that the function of $\alpha$ within $\{ \}$ is concave (e.g., ^[30]) with derivative

which equals $0$ at $\alpha = \frac12$.

(f) For any joint probability measures $P_{XY}$ and $Q_{XY}$ on the same product space,

Letting $P_{XY} = P \otimes Q$ and $Q_{XY} = Q \otimes P$ yields $S (P\, \| \, Q) \geq | P - Q |$. As we saw in Item 57, equality holds for binary $\mathcal{{A}}$. The right inequality in (6.5) is a special case of

proved in ^[43] in the discrete case by means of the Strassen-Dobrushin coupling representation of total variation ^[44,45], which requires that $({P_{{{\mathtt{0}}}}}, {Q_{{{\mathtt{0}}}}})$ be probability measures on a measurable space $(\mathcal{{A}}_{\mathtt{0}}, \mathscr{F}_{\mathtt{0}})$ such that $\{ (a, a)\colon a \in \mathcal{{A}}_{\mathtt{0}}\} \in \mathscr{F}_{\mathtt{0}} \otimes \mathscr{F}_{\mathtt{0}}$, and analogously for $({P_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{1}}}}})$. This is satisfied by any Polish $\mathcal{{A}}_{\mathtt{0}}$ endowed with its Borel field.

(g) Use the fact that $S(P\, \|\, Q) = D_f (P \otimes Q \, \| \, Q \otimes P)$ with $f(t) = |1-t|$, and dropping the first term on the right side of (4.73), we obtain

where (6.25) follows from Item 9.

(h) Given $P_{Y|X}\colon(\mathcal{{A}}, \mathscr{F}) \to (\mathcal{{B}}, \mathscr{G})$, construct the random transformation

$P_{Y_1 Y_2 | X_1 X_2} \colon (\mathcal{{A}}^2, \mathscr{F}^2) \to (\mathcal{{B}}^2, \mathscr{G}^2)$ defined by

Note that

and

Applying the data processing inequality for total variation distance to $P_{Y_1 Y_2 | X_1 X_2}$ with inputs $P_{{X_{{{\mathtt{0}}}}}}\otimes P_{{X_{{{\mathtt{1}}}}}}$ and $P_{{X_{{{\mathtt{1}}}}}}\otimes P_{{X_{{{\mathtt{0}}}}}}$, we obtain

(i) Let's proceed by contradiction and assume that there exists a convex $f\colon (0, \infty)$ such that $S(P\, \| \, Q) = D_f (P\, \| \, Q)$ for all $(P, Q)\in {\mathscr{P}_{\!\!\mathcal{{A}}}}^2$. Since $S(P\, \|\, Q) = | P - Q|$ in the special case $|\mathcal{{A}}| = 2$, Lemma 10 implies that there exists $\alpha \in \mathbb R$ such that $f(t) = |1-t| + \alpha \, t - \alpha$, i.e., $S(P\, \| \, Q) = | P-Q|$ which contradicts the examples in Items 58 and 59. An alternative route is to verify that NP-divergence fails to satisfy Lemma 11 by considering the special case $\lambda = \frac12$, ${P_{{{\mathtt{1}}}}} = {Q_{{{\mathtt{1}}}}} = [ \, \frac14 \; \frac34\; 0\; 0\, ]$, ${P_{{{\mathtt{0}}}}} = [ \, 0\; 0\; \frac14 \; \frac34\, ]$, ${Q_{{{\mathtt{0}}}}} = [ \, 0\; 0\; \frac34 \; \frac14\, ]$.

(j) With the notation used in the proof of Theorem 6,

Then, (6.8) follows from (5.17) and (6.1).

(k) The terms in the right side of (6.8) are determined by the relative information spectra:

□

Any pair such that $(P, Q) \not \equiv (Q, P)$ provides a counterexample to $\Longleftarrow$ in (6.9).

61. While not an $f$-divergence, Theorem 8–(f) implies that NP-divergence is a $g$-divergence ^[46]. Several properties for the measure of dependence $\inf_{Q_Y\in {\mathscr{P}_{\!\!\mathcal{{B}}}}} S (P_{XY} \, \|\, P_X \otimes Q_Y)$ can be obtained by specializing [46, Theorem 8].

62. It may be useful to generalize the NP-divergence by replacing the total variation distance by any other $f$-divergence, i.e., define

which satisfies $S_f (P\, \|\, Q) = S_f (Q\, \|\, P)$ even if $D_f$ is not symmetric.

7.   Sufficient statistics

Since its inception by Ronald Fisher in ^[47], the concept of sufficient statistics has played a fundamental role in mathematical statistics. This section offers a brief review of the various notions of sufficient statistics proposed in the literature, as well as their interrelationships emphasizing the connections with information theory. Moreover, we propose a new notion of sufficient statistics building upon the notion of equivalent pairs.

63. The basic setup in this section has the following ingredients:

● measurable spaces $(\mathcal{{Y}}, \mathscr{F})$ and $(\mathcal{{Z}}, \mathscr{G})$;

● a parameter set $\Theta$;

● a data model (collection of distributions on $(\mathcal{{Y}}, \mathscr{F})$): $\mathscr{P} = \{ P_{Y|V = \theta} \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}, \theta \in \Theta \}$;

● a random transformation: $P_{Z|Y}\colon (\mathcal{{Y}}, \mathscr{F}) \to (\mathcal{{Z}}, \mathscr{G})$.

An inference on the unknown parameter $\theta \in \Theta$ is made on the basis of the output of the random transformation $P_{Z|Y}$ when its input is distributed according to $P_{Y|V = \theta}$. Recall from Item 3 that no joint distribution $P_{VY}$ is assumed to exist. In fact, the setting is non-Bayesian: No distribution is assumed on the set of parameters $\Theta$, i.e., $P_V$ need not be defined. The question to be formalized is: Under what conditions does the random transformation $P_{Z|Y}$ preserve all the information in $Y$ that is relevant for inferring the parameter? Before proceeding, note that most of the statistical literature restricts attention to deterministic transformations, i.e., $Z = f(Y)$ for a $(\mathscr{F}, \mathscr{G})$-measurable $f\colon \mathcal{{Y}} \to \mathcal{{Z}}$. Allowing random transformations (as in ^[15,48,49]) is practically useful, since sometimes the data is observed through an inherently random mechanism which, nevertheless, does not spoil the relevant information. For example, if $\mathcal{{Y}} = \mathcal{{B}}^n$, and under each $\theta \in \Theta$, $P_{Y|V = \theta} = P_{\theta} \otimes \cdots \otimes P_{\theta}$ with $P_\theta \in {\mathscr{P}_{\!\!\mathcal{{B}}}}$, then a random interleaver $P_{Z|Y} \colon \mathcal{{B}}^n \to \mathcal{{B}}^n$ preserves all the information in the observed $n$-tuple relevant to the inference of $\theta \in \Theta$ because $\{ P_{Y|V = \theta} \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}, \, \theta \in \Theta \} = \{ P_{Z|V = \theta} \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}, \, \theta \in \Theta \}$. At any rate, allowing random transformations is really a matter of mathematical convenience/elegance; in fact it does not widen the scope since the randomness can be incorporated into the data model: Letting $P_{Y|V = \theta} \leftarrow P_{Z|Y}P_{Y|V = \theta}$ and $f(z, y) = z$ subsumes the notion of random transformations as sufficient statistics into the classical deterministic transformations.

64. Fisher's notion ^[47] states that $Z$ is a sufficient statistic of $Y$ for the collection $\mathscr{P} = \{ P_{Y|V = \theta}, \theta \in \Theta \}$ if

where, given that the unknown parameter is $V = \theta$, the joint probability measure of $Y$ and $Z$ is $P_{YZ|V = \theta} = P_{Y|V = \theta} P_{Z|Y}$. Following ^[50], when distinguishing from other notions of sufficient statistics, the sufficiency in the sense of this item is referred to as classical sufficiency.

65. Although $P_{YZ|V = \theta}$ is always well defined, we have to face the unfortunate fact that the conditional probability measure $P_{Y|Z, V = \theta}$ need not exist when $\mathcal{{Y}}$ is uncountable. The existence of such a conditional probability measure requires that for every $B \in \mathscr{F}$, there exist a $\mathscr{G}$-measurable $\phi_B \colon \mathcal{{Z}} \to [0, 1]$ such that for all $(\theta, B_0) \in \Theta\times\mathscr{G}$,

and $\phi_\cdot (z) \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}$ for $z\in \mathcal{{Z}}_\theta$, with $P_{Z|V = \theta} (\mathcal{{Z}}_\theta) = 1$ for all $\theta\in \Theta$. To guarantee that this is the case, it is customary to abide by the restriction that $(\mathcal{{Y}}, \mathscr{F})$ is a standard measurable space (i.e., it is isomorphic to $(E, \mathscr{B}_E)$ for some Borel subset of the real line $E \in \mathscr{B}$). Without such a restriction, Dieudonné ^[51] showed a counterexample where the required conditional probability does not exist, in which case the notion of sufficient statistics in the classical sense is vacuous. Whenever classical sufficiency is considered, it is typically assumed that the observation space is standard, even if this is not explicitly stated. As we see in Item 66, we need to place another restriction on the data model to make the notion of classical sufficiency well-behaved.

66. Bahadur ^[49] introduced the slightly more succinct notion of a sufficient $\sigma$-field $\bar{\mathscr{F}} \subset \mathscr{F}$, meaning that for every $B \in \mathscr{F}$ there exists a $\bar{\mathscr{F}}$-measurable $\varphi_B\colon \mathcal{{Y}} \to [0, 1]$, such that for all $(\theta, B_0) \in \Theta \times\bar{\mathscr{F}}$,

Then, a measurable function $f\colon\mathcal{{Y}}\to \mathcal{{Z}}$ is sufficient if and only if the $\sigma$-field it induces is sufficient. Curiously, the sufficiency of $\bar{\mathscr{F}}$ does not guarantee the sufficiency of every $\sigma$-field $\hat{\mathscr{F}}$ such that $\bar{\mathscr{F}} \subset \hat{\mathscr{F}} \subset \mathscr{F}$ ^[25]. Indeed, there may exist $f (y) = h (g(y))$ that is sufficient even though $g$ is not sufficient. Fortunately, if the data model $\mathscr{P}$ is dominated, not only is that anomalous behavior impossible ^[49], but the notions of sufficient random transformation and sufficient $\sigma$-field are equivalent ^[52] (see also [37, (6.38)]).

67. Due to Halmos and Savage [3, Corollary 1], formalizing earlier ideas of Fisher [47, p. 331] and Neyman [53, Theorem Ⅱ] in restricted settings, the following result is known as the factorization theorem.

Theorem 9. Suppose that $(\mathcal{{Y}}, \mathscr{F})$ is standard, $\mathscr{P}$ is dominated, and $P_{Z|Y}$ is a deterministic transformation, i.e., $P_{Z|Y = y} = \delta_{f(y)}$, for a $(\mathscr{F}, \mathscr{G})$-measurable $f\colon \mathcal{{Y}} \to \mathcal{{Z}}$. Then, $Z$ is a classically sufficient statistic of $Y$ for $\mathscr{P}$ if and only if there exist Borel-measurable $w\colon \mathcal{{Y}}\to [-\infty, \infty)$ and $v\colon \Theta \times \mathcal{{Z}}\to [-\infty, \infty)$ such that, for all $\theta\in\Theta$, $v(\theta, \cdot)$ is Borel-measurable and

where the information density is non-Bayesian (Item 26) with an arbitrary reference measure dominating $\mathscr{P}$.

Since the second term on the right side of (7.3) reflects the choice of the dominating measure, alternatively, we can express the condition for classical sufficiency in Theorem 9 as the existence of a dominating measure $\mathsf{μ}$ such that $\frac{\mathrm{d}P_{Y|V = \theta}}{\mathrm{d}\mathsf{μ}}$ is measurable with respect to the $\sigma$-field generated by $f$, for all $\theta\in\Theta$.

68. An important application of the factorization theorem is the following corollary to Corollary 3 in ^[3].

Theorem 10. If $| \Theta | = 2$ and $(\mathcal{{Y}}, \mathscr{F})$ is standard, then $\imath_{{P_{{{\mathtt{1}}}}}\| {P_{{{\mathtt{0}}}}}} (Y)$ is a sufficient statistic of $Y$ for $\mathscr{P} = \{P_{Y|V = \theta}, \, \theta \in \Theta\} = \{{P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$.

Proof. Define the function $g\colon(0, 1)\times \Theta \times [-\infty, +\infty] \to (0, \infty]$,

We can easily verify that with $\bar{P} = \frac12 {P_{{{\mathtt{0}}}}} + \frac12 {P_{{{\mathtt{1}}}}}$,

Consequently, letting $v (\theta, z) = - \log g(\frac12, \theta, z)$ and $w (y) = \imath_{\bar{P}\|R} (y)$, (7.3) holds if the non-Bayesian information density on the left side is defined with reference measure $R$ that dominates both ${P_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}}$. □

69. Theorem 11. Let $\mathscr{P} = \{P_{Y|V = \theta}, \, \theta \in \Theta\} = \{{P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$ be such that $D ({P_{{{\mathtt{1}}}}} \, \| \, {P_{{{\mathtt{0}}}}}) < \infty$. Fix $P_{Z|Y}$ and denote ${P_{{{\mathtt{0}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{1}}}}}$. A necessary and sufficient condition for $Z$ to be a classically sufficient statistic of $Y$ for $\mathscr{P}$ is

Introducing relative entropy in ^[2], Kullback and Leibler identified Theorem 11 as its most important property. However, they gave the result without the condition $D ({P_{{{\mathtt{1}}}}} \, \| \, {P_{{{\mathtt{0}}}}}) < \infty$, in which case it need not hold.

70. The following generalization of Theorem 11 is due to Csiszár ^[15,32].

Theorem 12. Let $\mathscr{P} = \{P_{Y|V = \theta}, \, \theta \in \Theta\} = \{{P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$ be such that $D_f ({P_{{{\mathtt{1}}}}} \, \| \, {P_{{{\mathtt{0}}}}}) < \infty$, where $f\colon (0, \infty) \to \mathbb R$ is strictly convex. Fix $P_{Z|Y}$ and denote ${P_{{{\mathtt{0}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{1}}}}}$. A necessary and sufficient condition for $Z$ to be a classically sufficient statistic of $Y$ for $\mathscr{P}$ is

71. Since Theorems 11 and 12 exclude pairs such that $D_f ({P_{{{\mathtt{1}}}}} \, \| \, {P_{{{\mathtt{0}}}}}) = \infty$, it is interesting to see if there are any $f$-divergences such that $f\colon (0, \infty) \to \mathbb R$ is strictly convex and $D_f ({P_{{{\mathtt{1}}}}} \, \| \, {P_{{{\mathtt{0}}}}})$ is bounded for any pair $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \in \mathscr{P}_{\mathcal{{Y}}}^2$. The answer is affirmative: In view of (4.80), any order-$\alpha$ Hellinger divergence with $\alpha \in (0, 1)$ (including the squared Hellinger distance (4.81)) is finite regardless of the pair of probability measures. Even though unbounded, the Bhattacharyya distance also qualifies since it is in one-to-one correspondence with the squared Hellinger distance. Also fitting the bill is the $f$-divergence with $f(t) = \frac{(t-1)^2}{t+1}$ known as the Vincze-LeCam divergence ^[18,19],

Although outside of the scope of Theorem 12, could the simpler total variation distance serve the same purpose? The answer is negative as we verify with a simple counterexample in Item 84.

72. The binary case in Items 68–70 is particularly important: $Z$ is said to be a pairwise sufficient statistic of $Y$ for $\mathscr{P} = \{P_{Y|V = \theta}, \, \theta \in \Theta\}$ if it is a sufficient statistic for $\{P_{Y|V = \theta}, P_{Y|V = \vartheta}\}$, for all $\theta \neq \vartheta \in \Theta$. Every sufficient statistic is pairwise sufficient. The converse holds if $\mathscr{P}$ is dominated ^[3,37,52,54]. Therefore, as long as the data model is dominated, we need not wander beyond binary models to deal with classically sufficient statistics.

73. Introduced by Kolmogorov ^[55], $Z$ is said to be a Bayes sufficient statistic of $Y$ for $\mathscr{P}$ if for all $P_V \in \mathscr{P}_\Theta$, $V$ and $Y$ are conditionally independent given $Z$. While in Items 64–66 we did not impose the condition that the collection $\mathscr{P} = \{ P_{Y|V = \theta} \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}, \theta \in \Theta \}$ be a random transformation (Item 3), in this case we are indeed imposing the corresponding measurability requirement for which a $\sigma$-field $\mathscr{H}$ of the subsets of $\Theta$ is also specified. Therefore, in this setting we have the Markov chain

Classical sufficiency (Item 64) implies Bayes sufficiency, because once a probability measure is defined on $V$, $P_{VY|Z} = P_{V|Z} P_{Y|Z, V} = P_{V|Z} P_{Y|Z}$ if the classical criterion (7.1) is satisfied; therefore, $V$ and $Y$ are conditionally independent given $Z$. Conversely, if the collection $\mathscr{P}$ is dominated, then ^[3,50] shows that pairwise Bayes sufficiency implies pairwise sufficiency, which in turn implies classical sufficiency as we saw in Item 72.

72. Theorem 13. Suppose that $\mathscr{P} = \{ P_{Y|V = \theta} \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}, \theta \in \Theta \}$ is dominated. Then, $Z$ is a Bayes sufficient statistic of $Y$ for $\mathscr{P}$ if for all $P_V \in \mathscr{P}_\Theta$,

Proof. Fix $P_V \in \mathscr{P}_\Theta$. We need to show that (7.11) is equivalent to the conditional independence of $V$ and $Y$ given $Z$. Particularizing the chain rule in (3.56),

According to Lemma 6, $P_{VY} \ll P_V \otimes P_Y$; therefore, $\mathbb{P}[ \imath_{V; Y} (V; Y) \in \mathbb R ] = 1$. We conclude that (7.11) is equivalent to $\imath_{V; Y|Z} (V; Y|Z) = 0$ a.s. □

75. In the binary case, Theorem 13 simplifies as follows.

Theorem 14. Let $\mathscr{P} = \{{P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$. Denote ${P_{{{\mathtt{0}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{1}}}}}$ for a fixed $P_{Z|Y}$. Then, $Z$ is a Bayes sufficient statistic of $Y$ for $\mathscr{P}$ if and only if

Proof. For $P_V = [0\; \; 1]$ or $[1\; \; 0]$, both sides of (7.11) are $0$. Fix $P_V (\mathtt{1}) = p \in (0, 1)$, and denote by $p_{ \mathtt{1} }$ and $p_{ \mathtt{0} }$ the densities of ${P_{{{\mathtt{1}}}}}$ and ${P_{{{\mathtt{0}}}}}$, respectively, with respect to the dominating measure $p\, {P_{{{\mathtt{1}}}}} + (1-p) {P_{{{\mathtt{0}}}}}$. Analogously, denote by $q_{ \mathtt{1} }$ and $q_{ \mathtt{0} }$ the densities of ${Q_{{{\mathtt{1}}}}}$ and ${Q_{{{\mathtt{0}}}}}$, respectively, with respect to the dominating measure $p\, {Q_{{{\mathtt{1}}}}} + (1-p) {Q_{{{\mathtt{0}}}}}$. It readily follows that, with the notation in (7.4),

The condition in (7.11) is equivalent to

which in turn is equivalent to (7.13) in view of (7.14)–(7.15) and the strict monotonicity of the function $g\left(p, \theta, \cdot \right)$ for all $(p, \theta)\in (0, 1) \times \{\mathtt{0}, \mathtt{1}\}$. □

76. Theorem 15. Suppose that $\mathscr{P} = \{ P_{Y|V = \theta} \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}, \theta \in \Theta \}$ is dominated. Then, $Z$ is a Bayes sufficient statistic of $Y$ for $\mathscr{P}$ if and only if $I (V; Y) = I (V; Z)$ for all those $P_V$ supported on two elements of $\Theta$.

Proof. Because of the domination assumption, Bayes sufficiency is equivalent to pairwise Bayes sufficiency (Item 73). Therefore, we can restrict attention to those $P_V$ supported on two elements of $\Theta$. Note that $I(V; Y) \leq 1$ bit with those input distributions. Since $I(V; Y)$ is finite and $I (V; Z| Y) = 0$, the chain rule of mutual information

implies that $I (V; Y) = I (V; Z)$ is equivalent to $I (V; Y | Z) = 0$, which, in turn, is equivalent to conditional independence of $V$ and $Y$ given $Z$. □

Without imposing the domination assumption, a related claim can be found in [56, p. 36]. However, note that if $I (V; Y) = I (V; Z) = \infty$, (7.18) does not guarantee $I (V; Y | Z) = 0$. Apparently unaware of the notion of Bayes sufficiency, Lindley ^[5] had proposed $I (V; Y) = I (V; Z)$ for all $P_V$ as a criterion for sufficiency, which he noticed to be implied by classical sufficiency.

77. Following ^{[37,52,57,58]}, $P_{Z|Y}$ is called Blackwell sufficient for $\mathscr{P} = \{ P_{Y|V = \theta}, \, \theta \in \Theta \}$ (sometimes also called exhaustive ^[59]) if there exists $P_{Y|Z}\colon (\mathcal{{Z}}, \mathscr{G}) \to (\mathcal{{Y}}, \mathscr{F})$ (dependent on $P_{Z|Y}$ and $\mathscr{P}$) such that for all $\theta \in \Theta$,

Therefore, $P_{Y|Z}$ acts as an "inverse random transformation" as long as the input to $P_{Z|Y}$ is drawn from $\mathscr{P}$. As shown in ^[60,61], (see also ^[52] and [37, (6.51)]), for dominated collections defined on standard spaces, classical sufficiency is the same as Blackwell sufficiency.

78. Let $\mathscr{P}_{\mathcal{{Z}}}$ stand for the collection of probability measures defined on $(\mathcal{{Z}}, \mathscr{G})$. In the terminology introduced by Blackwell ^[48,57], $\{ P_{Y|V = \theta} \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}, \theta \in \Theta \}$ is at least as informative as $\{ P_{Z|V = \theta} \in \mathscr{P}_{\mathcal{{Z}}}, \theta \in \Theta \}$ if there exists a random transformation $P_{Z|Y}\colon (\mathcal{{Y}}, \mathscr{F}) \to (\mathcal{{Z}}, \mathscr{G})$ such that

So, $P_{Z|Y}$ is Blackwell sufficient if and only if $\{ P_{Z|V = \theta}, \theta \in \Theta \}$ and $\{ P_{Y|V = \theta}, \theta \in \Theta \}$ are equally informative.

79. Taking stock of the various notions of sufficient statistics reviewed so far in this section, the notion of Bayes sufficiency is, in principle, easier to apply than the classical notion in Item 64 and does not require the topological assumption of a standard space. On the other hand, the factorization theorem (Theorem 9) typically provides a convenient method for verifying the sufficiency of deterministic transformations. Although the Blackwell criterion (Item 77) is intuitively appealing, identifying the required inverse random transformation (or showing that none exists) is not always straightforward. Building on Definition 2, next we introduce a new notion of sufficient statistic that is both easy to verify and equivalent to the foregoing notions for dominated models in standard spaces.

Definition 3. Fix $\{{P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$ and $P_{Z|Y}$, and denote ${P_{{{\mathtt{0}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{1}}}}}$. Then, $Z$ is an $I$-sufficient statistic of $Y$ for $\{{P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$ if

More generally, $Z$ is an $I$-sufficient statistic of $Y$ for $\{P_{Y|V = \theta}, \, \theta \in \Theta\}$ if it is $I$-sufficient for every pair $(\theta, \vartheta)$, $\theta \neq \vartheta \in \Theta$.

80. Example. For any $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in {\mathscr{P}_{\!\!\mathcal{{Y}}}}^2$, $\imath_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (Y)$ is an $I$-sufficient statistic of $Y$ for $\{ {P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$ because in view of Lemma 5,

81. Example. Suppose that $\Theta = \mathbb R$, $\mathcal{{Y}} = \mathbb R^n$ and $Y = (Y_1, \ldots, Y_n) = (\theta + X_1, \ldots, \theta + X_n)$, with $(X_1, \ldots, X_n)$ independent geometrically distributed with known parameter $q \in (0, 1)$. To verify that

is an $I$-sufficient statistic of $(Y_1, \ldots, Y_n)$ for this undominated data model, first note that $P_{Y|V = \theta + \ell} \perp P_{Y|V = \theta}$ and $P_{Z|V = \theta + \ell} \perp P_{Z|V = \theta}$, unless $\ell$ is an integer. With $\ell \in \{1, 2, \ldots\}$, we obtain

Moreover, we can easily check that $\imath_{P_{Y|V = \theta + \ell}\|P_{Y|V = \theta}} (y_1, \ldots, y_n) = \imath_{P_{Z|V = \theta + \ell}\|P_{Z|V = \theta}} (\min_{i = 1, \ldots, n} y_i)$.

82. Theorem 16. Assume that the data model $\mathscr{P} = \{P_{Y|V = \theta}, \, \theta \in \Theta\}$ is dominated and fix $P_{Z|Y}$.

(a) If $Z$ is a Bayes sufficient statistic of $Y$ for $\mathscr{P}$, then $Z$ is an $I$-sufficient statistic of $Y$ for $\mathscr{P}$.

(b) Assume that the observation space $(\mathcal{{Y}}, \mathscr{F})$ is standard. If $Z$ is an $I$-sufficient statistic of $Y$ for $\mathscr{P}$, then $Z$ is a classically sufficient statistic of $Y$ for $\mathscr{P}$.

Proof. In view of Items 72 and 73, the domination assumption allows us to restrict attention to the $|\Theta| = 2$ case.

(a) If $Z$ is a Bayes sufficient statistic of $Y$ for $\mathscr{P}$, then Theorem 14 implies that the random variables $\imath_{{P_{{{\mathtt{1}}}}}\| {P_{{{\mathtt{0}}}}}} (Y_{\mathtt{1}})$ and $\imath_{{Q_{{{\mathtt{1}}}}}\| {Q_{{{\mathtt{0}}}}}} (Z_{\mathtt{1}})$ with $Y_{\mathtt{1}} \sim {P_{{{\mathtt{1}}}}}$ and $Z_{\mathtt{1}}\sim {Q_{{{\mathtt{1}}}}}$ must have identical cumulative distribution functions. Therefore, $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ and $({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$ are equivalent pairs.

(b) If $Z$ is an $I$-sufficient statistic of $Y$ for $\mathscr{P}$, then Theorem 3 implies that $D_f ({P_{{{\mathtt{1}}}}}\, \|\, {P_{{{\mathtt{0}}}}}) = D_f ({Q_{{{\mathtt{1}}}}}\, \|\, {Q_{{{\mathtt{0}}}}})$ for all convex $f\colon(0, \infty) \to \mathbb R$. In particular, this encompasses the functions allowed in Theorem 12, and, consequently, $Z$ is a classically sufficient statistic of $Y$ for $\mathscr{P}$. Recall from Item 71 that the set of functions allowed in Theorem 12 is nonempty regardless of $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \in \mathscr{P}_{\mathcal{{Y}}}^2$.

□

83. The notions in Items 40 and 78 are related as follows.

Theorem 17. Suppose that $(\mathcal{{Y}}, \mathscr{F})$ and $(\mathcal{{Z}}, \mathscr{G})$ are standard spaces. For any $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})\in {\mathscr{P}_{\!\!\mathcal{{Y}}}}^2$ and $({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})\in \mathscr{P}^2_{\mathcal{{Z}}}$,

Proof.

$\Uparrow$ $\{ {P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}\}$ and $\{{Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}}\}$ are equally informative $\Rightarrow$ there exists $P_{Z|Y}\colon (\mathcal{{Y}}, \mathscr{F}) \to (\mathcal{{Z}}, \mathscr{G})$ which is Blackwell sufficient for $\{ {P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}\}$, and ${P_{{{\mathtt{1}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{1}}}}}$, ${P_{{{\mathtt{0}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{0}}}}}$. Since the model is dominated and lives in a standard space, Item 77 and Theorem 16 imply that $P_{Z|Y}$ is $I$-sufficient; therefore, $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \equiv ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$.

$\Downarrow$ As we saw in Theorem 10, the deterministic transformation $P_{X|Y}$ that outputs $X = \imath_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (Y)$ is a classically sufficient statistic for $\{{P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}\}$, and, analogously, the deterministic transformation $P_{\bar{X}|Z}$ that outputs $\bar{X} = \imath_{{Q_{{{\mathtt{1}}}}}\|{Q_{{{\mathtt{0}}}}}} (Z)$ is a classically sufficient statistic for $\{{Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}}\}$. Because the spaces are standard and the models are dominated, those statistics are Blackwell sufficient; therefore, there exist $P_{Y|X}$ and $P_{Z|\bar{X}}$ such that

Now by definition of $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \equiv ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$, the response of $P_{X|Y}$ to ${P_{{{\mathtt{1}}}}}$ is the same as the response of $P_{\bar{X}|Z}$ to ${Q_{{{\mathtt{1}}}}}$, and the response of $P_{X|Y}$ to ${P_{{{\mathtt{0}}}}}$ is the same as the response of $P_{\bar{X}|Z}$ to ${Q_{{{\mathtt{0}}}}}$. Therefore,

which implies that $\{{Q_{{{\mathtt{0}}}}}, {Q_{{{\mathtt{1}}}}}\}$ is at least as informative as $\{{P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$. Reversing the roles $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ and $({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$, we conclude that $\{{P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$ is at least as informative as $\{{Q_{{{\mathtt{0}}}}}, {Q_{{{\mathtt{1}}}}}\}$.

□

84. Example. Let $\mathcal{{B}} = \{ -, 0, +\}$, $\mathcal{{C}} = \{-, +\}$, and the random transformation $P_{Z|Y = 0} (+) = \frac12$, $P_{Z|Y = +} (+) = P_{Z|Y = -} (-) = 1$. Furthermore, consider $\{ P_{Y|V = \theta}, \theta \in \Theta \} = \{ {P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}} \}$ with

Then, $| {P_{{{\mathtt{1}}}}} - {P_{{{\mathtt{0}}}}} | = | {Q_{{{\mathtt{1}}}}} - {Q_{{{\mathtt{0}}}}} | = \frac23$. Although $P_{Z|Y}$ preserves total variation distance, $Z$ is not a sufficient statistic of $Y$ because $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \not \equiv ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$.

85. Summarizing the various results in this section as well as the necessary and sufficient conditions for equivalent pairs in Section 4, we have the following result.

Theorem 18. Suppose that the data model $\mathscr{P} = \{ P_{Y|V = \theta} \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}, \theta \in \Theta \}$ is dominated and $(\mathcal{{Y}}, \mathscr{F})$ is a standard space. Fix any random transformation: $P_{Z|Y}\colon (\mathcal{{Y}}, \mathscr{F}) \to (\mathcal{{Z}}, \mathscr{G})$, and denote ${P_{{{\mathtt{0}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}} \to P_{Z|Y} \to {Q_{{{\mathtt{1}}}}}$ for $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$. The following are equivalent.

(a) $Z$ is a classically sufficient statistic of $Y$ for $\mathscr{P}$.

(b) $Z$ is a Bayes sufficient statistic of $Y$ for $\mathscr{P}$.

(c) $Z$ is a Blackwell sufficient statistic of $Y$ for $\mathscr{P}$.

(d) $Z$ is an $I$-sufficient statistic of $Y$ for $\mathscr{P}$.

(e) For all $P_V \in \mathscr{P}_\Theta$,

(f) $I (V; Y) = I (V; Z)$ for all those $P_V\in \mathscr{P}_\Theta$ supported on two elements of $\Theta$.

(g) For all $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$ and $\alpha \in (0, \infty]$,

(h) For all $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$ and convex functions $f\colon(0, \infty)\to \mathbb R$,

(i) For all $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$,

(j) For all $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$,

(k) For all $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$,

(l) For all $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$ and $p\in (0, 1)$,

(m) For all $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$ and $\gamma \geq 1$,

(n) For all $({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})\in \mathscr{P}^2$,

See Item 100 for the justification of Theorem 18-(n).

86. When compelled to choose among various non-sufficient statistics, it is helpful to assign a figure of merit to every random transformation $P_{Z|Y}$ providing an indication of how close it is to being sufficient. Motivated by Theorem 18-(i), a couple of possibilities are

where the inequalities follow from the fact that the both the squared Hellinger distance and the Vincze-Le Cam divergence are $f$-divergences and equality occurs if and only if $P_{Z|Y}$ is a sufficient statistic. Alternatively, Theorem 18-(d) suggests using

where $K(\mathbb{F}, \mathbb{G}) = \sup_{x\in \mathbb R} | \mathbb{F}(x) - \mathbb{G}(x) |$ is the Kolmogorov-Smirnov distance between the cumulative distribution functions $\mathbb{F}$ and $\mathbb{G}$. Then, $P_{Z|Y}$ is a sufficient statistic if and only if (7.44) is zero. Naturally, in (7.44) we can substitute $K ({ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}, { \mathbb{F}}_{{Q_{{{\mathtt{1}}}}}\|{Q_{{{\mathtt{0}}}}}})$ by $| P_{\imath_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}} - P_{\imath_{{Q_{{{\mathtt{1}}}}}\|{Q_{{{\mathtt{0}}}}}}} |$ or any other measure of distance between probability measures.

8.   Hypothesis testing

The information spectra of the absolute information $\imath_X (X)$ and of the information density $\imath_{X; Y} (X; Y)$ prove to be instrumental in determining the fundamental limits of lossless and lossy compression, respectively, as well as data transmission, in the latter case. Unfortunately, explicit solutions are not feasible and we must be contented with bounds, which become tight under stationary/ergodic assumptions in the limit of long data blocks. In contrast, the relative information spectra determine exactly the non-asymptotic fundamental tradeoff in hypothesis testing. This section gives a full detailed solution of that tradeoff in non-Bayesian hypothesis testing including an operational role for the NP-divergence. No restrictions are placed on the pair of probability measures that govern the observation under the respective hypotheses:

Since we place no restrictions on ${P_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}}$, this "single-shot" setting encompasses the popular special case in which the observations are $n$ independent drawings from a given distribution, ${P_{{{\mathtt{0}}}}} = \mathsf{P}^{\otimes n}_0$ and ${P_{{{\mathtt{1}}}}} = \mathsf{P}^{\otimes n}_1$.

87. Let $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}^2$. A (randomized) hypothesis test is a deterministic measurable function $\phi\colon \mathcal{{Y}} \to [0, 1]$, such that $\phi(y)$ is the probability of guessing ${P_{{{\mathtt{1}}}}}$ if $y\in \mathcal{{Y}}$ is observed. A test $\phi$ is said to be deterministic if its range is $\{0, 1\}$, i.e., $\phi (y) = 1\{ y \in A\}$ for some measurable subset $A \subset \mathcal{{Y}}$. The performance of test $\phi$ is determined by the conditional probabilities of error,

88. The hypothesis testing fundamental tradeoff region consists of the set of achievable error probability pairs,

In other words, $({\pi_{{\mathtt{1}} \mid {\mathtt{0}}}}, {\pi_{{\mathtt{0}} \mid {\mathtt{1}}}}) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ if there is a hypothesis test for $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ achieving conditional error probabilities $({\pi_{{\mathtt{1}} \mid {\mathtt{0}}}}, {\pi_{{\mathtt{0}} \mid {\mathtt{1}}}})$. Elementary properties of the fundamental tradeoff region include:

Theorem 19.

(a) $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ is a convex set.

(b) $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ is a closed set.

(c) $(a, b) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \Longleftrightarrow (1-a, 1-b) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}).$

(d) $(a, b) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \Longleftrightarrow (b, a) \in \mathcal{C} ({P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}})$.

Proof.

(a) If $\phi_0$ and $\phi_1$ attain $(a_0, b_0) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ and $(a_1, b_1) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$, respectively, and $\alpha\in (0, 1)$, then the test $(1-\alpha) \phi_0 + \alpha\, \phi_1$ attains $(1-\alpha) (a_0, b_0) + \alpha\, (a_1, b_1)$.

(b) The mapping $\phi \mapsto (\mathbb{E} [ \phi ({Y_{{{\mathtt{0}}}}}) ], 1 - \mathbb{E} [ \phi ({Y_{{{\mathtt{1}}}}}) ])$ is linear.

(c) The test $1-\phi$ achieves $(1 - {\pi_{{\mathtt{1}} \mid {\mathtt{0}}}}, 1-{\pi_{{\mathtt{0}} \mid {\mathtt{1}}}})$ if $\phi$ achieves $({\pi_{{\mathtt{1}} \mid {\mathtt{0}}}}, {\pi_{{\mathtt{0}} \mid {\mathtt{1}}}})$.

(d) Interchanging $\phi \leftrightarrow 1 - \phi$ and ${P_{{{\mathtt{0}}}}} \leftrightarrow {P_{{{\mathtt{1}}}}}$ in (8.3).

□

89. In view of Theorem 19-(c), the set of points in $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ above the $(0, 1)—(1, 0)$ diagonal is redundant. The set of Pareto optimal error probability pairs is the lower boundary of $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ below the diagonal, which we refer to as the fundamental tradeoff function $\{\alpha_\nu \in [0, 1], \nu \in [0, 1]\}$ defined by

As a consequence of Theorem 19-(a), $\alpha_\nu ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ is convex on $[0, 1]$. Although the fundamental tradeoff region $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ and the fundamental tradeoff function $\alpha_\nu ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ determine each other, it is advantageous to work with both simultaneously, as we see below.

90. The diagonal connecting $(0, 1)—(1, 0)$ belongs to the fundamental tradeoff region

since $(p, 1-p)$ is attained by the blind test $\phi (y) = p$, $y \in \mathcal{{Y}}$. If ${P_{{{\mathtt{1}}}}} = {P_{{{\mathtt{0}}}}}$, then blind tests are optimal and equality holds in (8.6). Note that in this case the area of the fundamental tradeoff region satisfies $\left| \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{1}}}}}) \right| = 0$, and the fundamental tradeoff function is $\alpha_\nu ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{1}}}}}) = 1 -\nu$, $\nu \in [0, 1]$.

91. At the other extreme, if ${P_{{{\mathtt{1}}}}} \perp {P_{{{\mathtt{0}}}}}$, then $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) = [0, 1]^2$, $\alpha_\nu ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) = 0$, $\nu \in [0, 1]$, and the area of the fundamental tradeoff region satisfies $\left| \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \right| = 1$. To see this, recall (Item 7) that there exists an event $F\in \mathscr{F}$ such that ${P_{{{\mathtt{1}}}}} (F) = 1$ and ${P_{{{\mathtt{0}}}}} (F) = 0$. The deterministic test $\phi (y) = 1\{y\in F\}$ achieves the point $(0, 0)$, while the test $\phi (y) = 1\{y\not\in F\}$ achieves the point $(1, 1)$. All other points in the square are achievable because of (8.6) and Theorem 19-(a).

92. Inspired by radar, the function $\nu \mapsto 1 - \alpha_\nu ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ is frequently (e.g., ^[62]) referred to as the receiver operating characteristic, or ROC. In the radar application, ${P_{{{\mathtt{0}}}}}$ is the distribution of the observations under the absence of target return. In fact, this terminology is applied not just to the best possible curve but to the tradeoff between ${{\pi_{{\mathtt{1}} \mid {\mathtt{1}}}}}$ and ${\pi_{{\mathtt{1}} \mid {\mathtt{0}}}}$ achieved by any particular family of tests. The so-called area under the (ROC) curve, commonly abbreviated as AUC,

is frequently used as a scalar proxy to evaluate the degree to which ${P_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}}$ can be distinguished. It ranges from $\frac12$ if ${P_{{{\mathtt{0}}}}} = {P_{{{\mathtt{1}}}}}$ to $1$ if ${P_{{{\mathtt{0}}}}}\perp{P_{{{\mathtt{1}}}}}$.

93. Data processing theorem for the fundamental tradeoff region. If $P_Y \to P_{Z|Y} \to P_Z$ and $Q_Y \to P_{Z|Y} \to Q_Z$, then

since we always have the option of incorporating $P_{Z|Y}$ as a front end of the hypothesis test. Equality holds in (8.8)–(8.9) if $Z$ is a Blackwell sufficient statistic of $Y$ for $(P_Y, Q_Y)$, because from $Z$ (along, with possibly additional randomness) we can synthesize data whose conditional distributions are $P_Y$ and $Q_Y$. Feeding that data to $\phi$ results in the same $({\pi_{{\mathtt{1}} \mid {\mathtt{0}}}}, {\pi_{{\mathtt{0}} \mid {\mathtt{1}}}})$ as feeding the original $Y$ to $\phi$.

94. The minimal error probabilities compatible with zero error probability of the other kind are denoted by ${{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}}$ and ${{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}$, i.e., they are defined by

● $({{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}, 0) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ but $({\pi_{{\mathtt{1}} \mid {\mathtt{0}}}}, 0) \not\in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ if ${\pi_{{\mathtt{1}} \mid {\mathtt{0}}}} < {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}$;

● $(0, {{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}}) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ but $(0, {\pi_{{\mathtt{0}} \mid {\mathtt{1}}}}) \not\in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ if ${\pi_{{\mathtt{0}} \mid {\mathtt{1}}}} < {{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}}$.

By definition,

Theorem 20. For any $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}^2$,

(a) ${{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}} = \Pi ({P_{{{\mathtt{0}}}}}\, \|\, {P_{{{\mathtt{1}}}}})$, achieved by the test $\phi(y) = 1\{ y \in \mathcal{{S}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} \}$;

(b) ${{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}} = \Pi ({P_{{{\mathtt{1}}}}}\, \|\, {P_{{{\mathtt{0}}}}})$, achieved by the test $\phi(y) = 1\{ y \not\in \mathcal{{S}}_{{P_{{{\mathtt{0}}}}}\|{P_{{{\mathtt{1}}}}}} \}$.

Proof. For any test $\phi$ achieving error probabilities $({\pi_{{\mathtt{1}} \mid {\mathtt{0}}}}, {\pi_{{\mathtt{0}} \mid {\mathtt{1}}}})$,

and

where (8.14) holds if ${\pi_{{\mathtt{0}} \mid {\mathtt{1}}}} = 0$ because of (2.4) and (8.12). Furthermore, as we saw in (2.14), if $\phi(y) = 1\{ y \in \mathcal{{S}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} \},$ then the right side of (8.12) is satisfied and (8.13)–(8.14) become identities. Recalling (2.14) completes the proof of (a). The proof of (b) is identical. □

95. Introduced in ^[7], for $(\gamma, \lambda) \in \mathbb R \times [0, 1]$, a Neyman-Pearson test between ${P_{{{\mathtt{1}}}}}$ and ${P_{{{\mathtt{0}}}}}$ is

The tests $\phi_{\gamma, 0}$ and $\phi_{\gamma, 1}$ are known as deterministic Neyman-Pearson tests. The limiting Neyman-Pearson tests are the deterministic tests

96. With ${Y_{{{\mathtt{0}}}}} \sim {P_{{{\mathtt{0}}}}}$ and ${Y_{{{\mathtt{1}}}}} \sim {P_{{{\mathtt{1}}}}}$, the Neyman-Pearson test (8.15) achieves the conditional error probabilities

The randomization serves to obtain convex combinations of the performances obtained by deterministic Neyman-Pearson tests,

where

97. The following venerable result states that the non-limiting Neyman-Pearson tests are Pareto-optimal.

Lemma 12. Neyman-Pearson ^[7]. Let ${Y_{{{\mathtt{0}}}}} \sim {P_{{{\mathtt{0}}}}}$ and ${Y_{{{\mathtt{1}}}}} \sim {P_{{{\mathtt{1}}}}}$. For any $\lambda \in [0, 1]$, $\gamma \in \mathbb R$, and measurable function $\phi\colon \mathcal{{Y}} \to [0, 1]$,

Proof. Invoking (8.18)–(8.19), (4.25), and Lemma 9 with $g(a) = 1 -\phi (a)$, we obtain

□

98. In addition to giving the fundamental tradeoff in terms of the relative information spectra, the following result finds an operational role for the NP-divergence.

Theorem 21. Let $({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) \in {\mathscr{P}_{\!\!\mathcal{{Y}}}}^2$ such that ${P_{{{\mathtt{0}}}}} \not \perp {P_{{{\mathtt{1}}}}}$.

(a) The limiting Neyman-Pearson tests $\phi (y) = 1\{ y \in \mathcal{{S}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}\}$ and $\phi (y) = 1\{ y \not\in \mathcal{{S}}_{{P_{{{\mathtt{0}}}}}\|{P_{{{\mathtt{1}}}}}}\}$ achieve the Pareto-optimal points $({{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}, 0) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ and $(0, {{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}}) \in \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$, respectively.

(b) For any other Pareto-optimal point in $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$, there exist $\gamma \in \mathbb R$ and $\lambda\in [0, 1]$, such that the point is achieved by the Neyman-Pearson test $\phi_{\gamma, \lambda}$.

(c) The intersection of $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ and the triangle $(0, 0)— (0, 1)—(1, 0)— (0, 0)$ is the convex closure of the points

(d) For $\nu \in (0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}})$, the fundamental tradeoff function is given by

where the minimum is achieved by $\gamma^\star$:

● If $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}^{-1} (1- \nu) \neq \varnothing$, $\gamma^\star$ is any solution to

in which case

● If $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}^{-1} (1- \nu) = \varnothing$, then $\gamma^\star$ is the unique scalar such that

Moreover, in this case,

where

(e)

(f)

(g) If $P \neq Q$, then

Proof.

(a) $\Longleftarrow$ Theorem 20, (8.16)–(8.17), and the fact that $({{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}, 0)$ and $(0, {{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}})$ are Pareto optimal by definition.

(b) As a result of Lemma 12, the Neyman-Pearson test $\phi_{\gamma, \lambda}$ is Pareto-optimal for all $(\gamma, \lambda)\in \mathbb R \times [0, 1]$. Moreover, for every value of $\nu \in (0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}})$, there is a (possibly non-unique) pair $(\gamma, \lambda)\in \mathbb R \times [0, 1]$ which yields

To verify this, bearing (8.19) in mind, we have

● If $\bar{ \mathbb{F}}^{-1}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (1-\nu) \neq \varnothing$, then any $\lambda\in [0, 1]$ and $\gamma^\star$ that satisfies (8.30) give a solution to (8.38) since (8.30) implies $\mathbb{P} \left[ \imath_{{P_{{{\mathtt{1}}}}}\| {P_{{{\mathtt{0}}}}}} ({Y_{{{\mathtt{0}}}}}) = \gamma \right] = 0$.

● If $\bar{ \mathbb{F}}^{-1}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (1-\nu) = \varnothing$, then $\gamma^\star$ and $\lambda^\star$ defined by (8.32) and (8.34), respectively, provide a (unique) solution to (8.38). Actually, a solution to (8.38) ensues if $\gamma^\star$ were replaced in (8.34) by any $\gamma$, but $\gamma^\star$ is the only choice that guarantees that $\lambda^\star \in (0, 1)$.

(c) The closure of $\mathcal{{C}}_0 = \cup_{\gamma \in \mathbb R} \left(1 - \bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma), \mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma) \right)$ is $\mathcal{{C}}_0 \cup \{({{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}, 0)\} \cup \{(0, {{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}})\}$, since (4.5), (4.8), and Theorem 8.2 yield

The presence of the points $(0, 1)$ and $(1, 0)$ in (8.28) serves to include the non-Pareto-optimal segments $(0, 1)—(0, {{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}})$ and $(1, 0)—({{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}, 0)$, as well as their convex combinations. Note from (8.22)–(8.23) that the elements in $\mathcal{{C}}_0$ are the error probability pairs achieved by the deterministic Neyman-Pearson tests $\phi_{\gamma, 0}$. Moreover, the error probability pairs achieved by deterministic Neyman-Pearson tests $\phi_{\gamma, 1}$ belong to $\mathrm{cl} (\mathcal{{C}}_0)$ due to (8.24)–(8.25). Finally, as we saw in (8.20)–(8.21), the convex combinations of the pairs achieved by deterministic tests are the error probability pairs achieved by the randomized tests $\phi_{\gamma, \lambda}$, with $\lambda \in (0, 1)$.

(d) Thanks to (4.25), for all $\gamma\in \mathbb R$,

and we can eliminate $\lambda$ from (8.18)–(8.19) to show that the conditional probabilities achieved by the Neyman-Pearson test $\phi_{\gamma, \lambda}$ satisfy the linear relationship

As a result of (b), minimizing (8.42) over $\gamma$ such that $\nu = {\pi_{{\mathtt{1}} \mid {\mathtt{0}}}} (\gamma, \lambda) \in (0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}})$, yields $\alpha_\nu ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ as stated in (8.29). The minimizers of (8.42) were justified in the proof of (b). In particular,

● If $\bar{ \mathbb{F}}^{-1}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (1-\nu) \neq \varnothing$, then, when evaluated at any solution to (8.30), both probabilities in (8.41) are equal to zero and (8.18)–(8.19) yield (8.31). Note that if $\bar{ \mathbb{F}}^{-1}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (1-\nu)$ has more than one element, then not only is $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ constant on an interval but so is ${ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ on the same interval according to Theorem 4.1-(b). Therefore, (8.31) is well-defined.

● If $\bar{ \mathbb{F}}^{-1}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (1-\nu) = \varnothing$, then evaluating (8.18) at $(\gamma^\star, \lambda^\star)$ yields (8.33), since $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma^\star) - \lim_{x\uparrow \gamma^\star} { \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (x) = \mathbb{P} \left[ \imath_{{P_{{{\mathtt{1}}}}}\| {P_{{{\mathtt{0}}}}}} ({Y_{{{\mathtt{1}}}}}) = \gamma^\star \right]$.

(e) Recalling Item 41,

where (8.44) follows from (c). To prove the reverse implication, we must show that the function $\alpha_\nu ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$ determines $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$. The explicit dependence is given in Theorem 22 in the Appendix.

(f) Recalling the symmetry property in Theorem 19-(c),

Because of the convexity of $\alpha_\nu$ (Item 89), its derivative is a non-decreasing function which may have at most a countable number of discontinuities on the interval $[0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}]$. We partition the integral in (8.45) as the finite or countably infinite sum of subintegrals of differentiable sections, distinguishing between the sections in which $\alpha_\nu$ is a straight line (corresponding to jumps in the relative information spectra) and those in which it is not. Recall that the non-straight-line sections are due to portions of the relative information spectra that are strictly monotonically increasing. Flat portions in the spectra only affect the kinks—points of discontinuous derivative—in $\alpha_\nu$, which do not contribute to its integral. Therefore, we have

where $\Gamma$ is the finite, or countably infinite, set of abscissas at which the jumps in the relative information spectra occur, $\alpha_\nu$ is a straight line on the intervals $[ \nu^-(\gamma), \nu^+(\gamma) ]$, and $\alpha_\nu$ is differentiable but not a straight line on the intervals $[\nu_i, \nu_{i+1}]$.

ⅰ. We saw in (d) that each $\gamma \in \Gamma$ contributes a straight line in the fundamental tradeoff function of slope $-\exp (\gamma)$ between the abscissas $\nu^-(\gamma) = 1- \bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma)$ and $\nu^+ (\gamma) = 1- \lim_{x\uparrow \gamma} \bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (x)$. In view of (8.33), observe that

Therefore, the trapezoidal area is

Then, the sum of the subintegrals (8.50) due to the straight-line segments equals

where ${Y_{{{\mathtt{0}}}}}$ and ${Y_{{{\mathtt{1}}}}}$ are independent.

ⅱ. For a section between $\nu_0$ and $\nu_1$ on which $\alpha_\nu$ is differentiable and not a straight line, the parametric solution in (8.18)–(8.19) reduces to

whose definite integral can be written as the Lebesgue-Stieltjes integral

Summing (8.51) and all subintegrals of the non-straight-line portions in (8.54) yields

Plugging (8.56) into (8.45) yields

in light of Theorem 8-(i).

(g) $\Longleftarrow$ (6.4) and (8.37).

□

99. A folk theorem (e.g., ^[63,64]) is that the area under the curve (Item 92) is the "probability that the classifier will rank a randomly chosen positive instance higher than a randomly chosen negative instance". The ambiguity in whether "higher" means $\geq$ or $>$ is inconsequential if the relative information spectra are continuous. Otherwise, we must split the difference as (8.7) together with Theorem 21-(f) yields, with $({Y_{{{\mathtt{0}}}}}, {Y_{{{\mathtt{1}}}}}) \sim {P_{{{\mathtt{0}}}}} \otimes {P_{{{\mathtt{1}}}}}$,

100. A corollary to a result by Pfanzagl ^[61] is that $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) = \mathcal{C} ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$ (in the notation of Theorems 11 and 12) is a sufficient condition for $Z$ to be a sufficient statistic of $Y$ for $\{ {P_{{{\mathtt{0}}}}}, {P_{{{\mathtt{1}}}}}\}$. In fact, Theorems 16 and 21-(e) imply that the preservation of the fundamental tradeoff region in hypothesis testing is an equivalent criterion for pairwise sufficiency. Therefore, Theorem 7.10-(n) will follow from

To justify (8.60), recall from Item 93 that $\mathcal{C} ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}}) \subset \mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})$. Therefore, $|\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}})| > |\mathcal{C} ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})|$ unless $\mathcal{C} ({P_{{{\mathtt{1}}}}}, {P_{{{\mathtt{0}}}}}) = \mathcal{C} ({Q_{{{\mathtt{1}}}}}, {Q_{{{\mathtt{0}}}}})$. Theorem 8.3-(f) implies (8.61).

9.   Conclusions

One of the defining features of information theory is the study of random variables such as $\imath_X (X) = \log \frac1{P_X (X)}$, $\imath_{X\|Y} (X)$ and $\imath_{X\|Y} (Y)$, where the probability mass function of $X$ is evaluated at $X$ and the log density function of $P_X$ with respect to $P_Y$ is evaluated at $X$ or $Y$, respectively. The averages of those random variables, entropy and relative entropy, are the pillars that sustain the asymptotics of the fundamental limits in data compression, hypothesis testing, and data transmission in stationary ergodic models. Beyond averages, the study of the distributions of those random variables, also known as information spectra and relative information spectra, is the key to non-asymptotic fundamental limits.

This paper has studied the relative information spectra for arbitrary pairs of probability measures defined on the same measurable space. To that end, the formalization of the concepts of relative support and coefficient of absolute discontinuity has proven valuable. Particular emphasis has been placed on the interplay of the distributions of $\imath_{X\|Y} (X)$ and $\imath_{X\|Y} (Y)$, which determine each other, as well as their relationships with measures of discrepancy such as total variation distance, relative entropy, Rényi divergence and $f$-divergences. Equivalent pairs of probability measures (possibly belonging to different measurable spaces) are those with identically-distributed relative informations.

The exposition of the applications to statistical inference has emphasized their connections to the literature. Based on equivalent pairs, we have introduced the conceptually simple notion of $I$-sufficiency, which can be checked easily even without the usual assumptions of deterministic statistics and dominated collections on standard spaces. When those assumptions are satisfied, the necessary and sufficient condition given by the Halmos-Savage factorization necessary and sufficient condition (Theorem 9) remains the gold standard for verifying the sufficiency of deterministic transformations.

The non-asymptotic (Neyman-Pearson) fundamental tradeoff region of conditional error probabilities in binary hypothesis testing is a major application of the relative information spectra. We have given a detailed description of the region without any assumptions of absolute continuity. The area of the Neyman-Pearson tradeoff region is a normalized measure of the discrepancy between the probability measures, equal to zero [resp., one] for identical [resp., orthogonal] probability measures, which is popular in applications in a slightly modified form referred to as the area under the curve (AUC). We have shown that the area of the Neyman-Pearson tradeoff region is equal to (one-half) the NP-divergence, $| {P_{{{\mathtt{0}}}}}\otimes {P_{{{\mathtt{1}}}}} - {P_{{{\mathtt{1}}}}} \otimes {P_{{{\mathtt{0}}}}} |$, a new discrepancy measure between probability measures ${P_{{{\mathtt{0}}}}}$ and ${P_{{{\mathtt{1}}}}}$. Along with Chernoff information, it appears to be one of the most interesting divergences among those that satisfy the data processing inequality but are not $f$-divergences. We have shown that the preservation of the NP-divergence is a necessary and sufficient condition for the statistic to be sufficient. An immediate operational role is inherited from total variation distance, as the NP-divergence governs the error probability of the Bayesian test that identifies the order of a pair of observations, one drawn from ${P_{{{\mathtt{0}}}}}$ and the other from ${P_{{{\mathtt{1}}}}}$. A new asymptotic operational role for the Bhattachrayya distance has been shown for independent identically distributed observations: The rate of approach to 1 of the area of the fundamental non-Bayesian tradeoff region decays exponentially in twice the number of observations times the Bhattachrayya distance. In contrast, as shown in ^[14] in the Bayesian setting, the exponential decay of the minimum error probability is governed by the Chernoff information regardless of the values of the nonzero a priori probabilities.

A.   Appendix 1: Relative information spectra from fundamental tradeoff function

On account of the convexity of $\alpha_\nu$, its derivative on $(0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}})$ is negative monotonic non-decreasing with a finite, or countably infinite, number of discontinuities. Those discontinuities determine the locations of the jumps of $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$, which are the same as those of $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$. For $\nu \in (0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}})$, denote the left/right derivatives by

Naturally, we drop the superscript whenever $\dot{\alpha}^-_{\nu} = \dot{\alpha}^+_{\nu}$. The following result gives $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ as a function of $\{ \alpha_\nu, \nu \in [0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}})\}$, with ${{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}} = \max\{ \nu\in [0, 1] \colon \alpha_\nu = 0\}$, as per (8.11). The fact that the relative information spectrum and the fundamental tradeoff region determine each other validates the opening sentence in the abstract.

Theorem 22.

1. $\lim_{t \to \infty} \mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (t) = {{\underline{\pi}_{{\mathtt{0}} \mid {\mathtt{1}}}}} = \alpha_0$.

2. $\lim_{t \to -\infty} \bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (t) = 1- {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}$.

3. Fix $\gamma \in \mathbb R$. To determine $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma)$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma)$, there are two possibilities.

(a) There is a unique $\bar{\nu}_\gamma \in (0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}})$ such that

Then, $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma) = \alpha_{\bar{\nu}_\gamma}$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma) = 1 - {\bar{\nu}_\gamma}$.

(b) Let $(\nu_\gamma^-, \nu_\gamma^+) \subset [0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}}]$ be the largest open interval such that

Then, $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma) = \alpha_{\nu_\gamma^-}$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma) = 1 - {\nu_\gamma^-}$. Furthermore, $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ experiences a jump at $\gamma$ of height $\alpha_{\nu_\gamma^-} - \alpha_{\nu_\gamma^+}$, while the jump at $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma)$ has height $\nu_\gamma^+ - \nu_\gamma^-$.

Proof.

1) $\Longleftarrow$ (8.10) and (8.39).

2) $\Longleftarrow$ (8.40).

3) As we saw in Theorem 21-(d), $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ experience a jump at $\gamma$ if and only if the function $\alpha_\nu$ has a straight line such that case 3b) holds.

3a) Since $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ are continuous at $\gamma$, Theorem 21-(d) gives

At those $\nu \in (0, {{\underline{\pi}_{{\mathtt{1}} \mid {\mathtt{0}}}}})$ such that $\dot{\alpha}^-_{\nu} = \dot{\alpha}^+_{\nu}$, we can differentiate (A.4) and (A.5) with respect to $\nu$ and $\gamma$, respectively, to conclude, with the aid of (4.26), that

If $\dot{\alpha}^-_{\nu} < \dot{\alpha}^+_{\nu}$, the discontinuity in the derivative is caused by the fact that there is an interval of values of $\gamma$ on which both $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma)$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}} (\gamma)$ are constant; therefore, according to (A.4)–(A.5), those values of $\gamma$ result in a single Pareto-optimal point $({\bar{\nu}_\gamma}, \alpha_{\bar{\nu}_\gamma})$. The interval of values of $\gamma$ is indeed (A.2) since any slope strictly lower than $\dot{\alpha}^-_{\bar{\nu}_\gamma}$, or strictly higher than $\dot{\alpha}^+_{\bar{\nu}_\gamma}$, corresponds to Pareto-optimal points other than $({\bar{\nu}_\gamma}, \alpha_{\bar{\nu}_\gamma})$.

3b) Since $\mathbb{F}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ and $\bar{ \mathbb{F}}_{{P_{{{\mathtt{1}}}}}\|{P_{{{\mathtt{0}}}}}}$ experience a jump at $\gamma$, $\alpha_\nu$ has a straight line with slope

according to (8.33)–(8.34) and (8.41). The range of abscissas $\nu$ of that straight line is given by (8.32), thereby indicating that

Again, according to (8.33)–(8.34), the corresponding ordinates of those points are

□

Use of Generative-AI tools declaration

The author declares he has not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

I am indebted to guest-editor Prof. Igal Sason for graciously extending the invitation for this submission and his meticulous reading of the manuscript. Reference ^[43] was kindly brought to my attention by an anonymous reviewer.

Conflict of interest

The author declares no conflict of interest.