3 e-Rényi and e-Chernoff divergences

Definition 3.1

✓

The e-Rényi divergence of order \(\alpha \in (0,1)\) between two sets of probability measures \(\mathcal{P}, \mathcal{Q} \subseteq \mathcal{P}(\mathcal{X})\) is defined as

\begin{align*} \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) & = \frac{1}{1 - \alpha } \inf _{R \in \mathcal{P}(\mathcal{X})} \left( \alpha \mathcal{U}(R, \mathcal{P}) + (1 - \alpha ) \mathcal{U}(R, \mathcal{Q}) \right) \: , \end{align*}

for \(\mathcal{U}_{\log }\) the max-utility corresponding to the logarithmic utility.

Definition 3.2

✓

\begin{align*} \operatorname{eC}_\alpha (\mathcal{P}, \mathcal{Q}) & = \inf _{R \in \mathcal{P}(\mathcal{X})} \max \left\{ \mathcal{U}(R, \mathcal{P}), \mathcal{U}_{\log }(R, \mathcal{Q}) \right\} \: . \end{align*}

Lemma 3.3

✓

Let \(\mathcal{P}' \subseteq \mathcal{P}\) and \(\mathcal{Q}' \subseteq \mathcal{Q}\). Then, for all \(\alpha \in (0, 1)\),

\begin{align*} \operatorname{eR}_\alpha (\mathcal{P}’, \mathcal{Q}’) & \ge \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Proof ▶

Lemma 3.4

✓

Let \(\mathcal{P}' \subseteq \mathcal{P}\) and \(\mathcal{Q}' \subseteq \mathcal{Q}\). Then

\begin{align*} \operatorname{eC}_\alpha (\mathcal{P}’, \mathcal{Q}’) & \ge \operatorname{eC}_\alpha (\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Proof ▶

Lemma 3.5

✓

Let \(\kappa : \mathcal{X} \rightsquigarrow \mathcal{Y}\) be Markov kernel. Then

\begin{align*} \operatorname{eR}_\alpha (\kappa \circ \mathcal{P}, \kappa \circ \mathcal{Q}) & \le \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Proof ▶

Lemma 3.6

✓

Let \(f : \mathcal{X} \to \mathcal{Y}\) be a measurable map. Then

\begin{align*} \operatorname{eR}_\alpha (f_*\mathcal{P}, f_*\mathcal{Q}) & \le \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Proof ▶

Lemma 3.7

✓

Let \(\kappa : \mathcal{X} \rightsquigarrow \mathcal{Y}\) be Markov kernel. Then

\begin{align*} \operatorname{eC}_\alpha (\kappa \circ \mathcal{P}, \kappa \circ \mathcal{Q}) & \le \operatorname{eC}_\alpha (\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Proof ▶

Lemma 3.8

✓

Let \(f : \mathcal{X} \to \mathcal{Y}\) be a measurable map. Then

\begin{align*} \operatorname{eC}_\alpha (f_*\mathcal{P}, f_*\mathcal{Q}) & \le \operatorname{eC}_\alpha (\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Proof ▶

Lemma 3.9

For \(\alpha \in (0,1)\), if \(\operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) {\lt} \infty \), then

\begin{align*} \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) & = \frac{1}{1 - \alpha } \inf _{R \in \mathcal{P}(\mathcal{X}), \: R \ll \mathcal{P}, \: R \ll \mathcal{Q}} \left( \alpha \mathcal{U}_{\log }(R, \mathcal{P}) + (1 - \alpha ) \mathcal{U}_{\log }(R, \mathcal{Q}) \right) \: . \end{align*}

That is, the infimum defining \(\operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q})\) can be restricted to measures \(R\) that are absolutely continuous with respect to both \(\mathcal{P}\) and \(\mathcal{Q}\).

TODO: can we drop the finiteness assumption?

Proof ▶

If \(R\) is not absolutely continuous with respect to \(\mathcal{P}\), then \(\mathcal{U}_{\log }(R, \mathcal{P}) = \infty \) by Lemma 2.19. Similarly, if \(R\) is not absolutely continuous with respect to \(\mathcal{Q}\), then \(\mathcal{U}_{\log }(R, \mathcal{Q}) = \infty \). Hence, in both cases, the term \(\alpha \mathcal{U_{\log }(R, \mathcal{P}) + (1 - \alpha ) \mathcal{U}_{\log }(R, \mathcal{Q})}\) is infinite and does not contribute to the infimum defining \(\operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q})\).

Corollary 3.10

For \(\alpha \in (0,1)\), if \(\operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) {\lt} \infty \) and there exists a measurable set \(A\) with \(P(A^c) = 0\) and \(Q(A^c) = 0\) for all \(P \in \mathcal{P}\) and \(Q \in \mathcal{Q}\), then

\begin{align*} \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) & = \frac{1}{1 - \alpha } \inf _{R \in \mathcal{P}(\mathcal{X}), \: R(A^c) = 0} \left( \alpha \mathcal{U}_{\log }(R, \mathcal{P}) + (1 - \alpha ) \mathcal{U}_{\log }(R, \mathcal{Q}) \right) \: . \end{align*}

That is, the infimum defining \(\operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q})\) can be restricted to measures \(R\) supported on \(A\).

Proof ▶

We apply Lemma 3.9 and note that any measure \(R\) that is absolutely continuous with respect to both \(\mathcal{P}\) and \(\mathcal{Q}\) must satisfy \(R(A^c) = 0\).

Lemma 3.11

Let \(\phi : \mathcal{X} \to \mathcal{Y}\) be a measurable embedding. Then

\begin{align*} \operatorname{eR}_\alpha (\phi _*\mathcal{P}, \phi _*\mathcal{Q}) & = \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Proof ▶

By Lemma 3.6, we have \(\operatorname{eR}_\alpha (\phi _*\mathcal{P}, \phi _*\mathcal{Q}) \le \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q})\). Then either both sides are infinite and we are done, or the left hand side is finite.

Let \(A = \phi (\mathcal{X}) \subseteq \mathcal{Y}\). Then for all \(P \in \mathcal{P}\) and \(Q \in \mathcal{Q}\), we have \(\phi _* P(A^c) = 0\) and \(\phi _* Q(A^c) = 0\). By Corollary 3.10, we can restrict the infimum defining \(\operatorname{eR}_\alpha (\phi _*\mathcal{P}, \phi _*\mathcal{Q})\) to measures supported on \(A\). Since \(\phi \) is an embedding, every measure supported on \(A\) is of the form \(\phi _* R\) for some \(R \in \mathcal{P}(\mathcal{X})\) (take \(R = \phi ^{-1}_* R'\), in which \(\phi ^{-1}\) is a partial inverse on the range of \(\phi \)).

\begin{align*} \operatorname{eR}_\alpha (\phi _*\mathcal{P}, \phi _*\mathcal{Q}) & = \frac{1}{1 - \alpha } \inf _{R' \in \mathcal{P}(\mathcal{Y}), \: R'(A^c) = 0} \left( \alpha \mathcal{U}_{\log }(R’, \phi _* \mathcal{P}) + (1 - \alpha ) \mathcal{U}_{\log }(R’, \phi _* \mathcal{Q}) \right) \\ & = \frac{1}{1 - \alpha } \inf _{R \in \mathcal{P}(\mathcal{X})} \left( \alpha \mathcal{U}_{\log }(\phi _* R, \phi _* \mathcal{P}) + (1 - \alpha ) \mathcal{U}_{\log }(\phi _* R, \phi _* \mathcal{Q}) \right) \: . \end{align*}

Using then Lemma 2.26, we get

\begin{align*} \operatorname{eR}_\alpha (\phi _*\mathcal{P}, \phi _*\mathcal{Q}) & = \frac{1}{1 - \alpha } \inf _{R \in \mathcal{P}(\mathcal{X})} \left( \alpha \mathcal{U}_{\log }(R, \mathcal{P}) + (1 - \alpha ) \mathcal{U}_{\log }(R, \mathcal{Q}) \right) \\ & = \operatorname{eR}_\alpha (\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Lemma 3.12

✓

\begin{align*} \mathcal{U}(P_1 \otimes P_2, \mathcal{Q}_1 \otimes \mathcal{Q}_2) & = \mathcal{U}(P_1, \mathcal{Q}_1) + \mathcal{U}(P_2, \mathcal{Q}_2) \: . \end{align*}

Proof ▶

Lemma 3.13

✓

\begin{align*} \operatorname{eR}_\alpha (\mathcal{P}_1 \otimes \mathcal{P}_2, \mathcal{Q}_1 \otimes \mathcal{Q}_2) & = \operatorname{eR}_\alpha (\mathcal{P}_1, \mathcal{Q}_1) + \operatorname{eR}_\alpha (\mathcal{P}_2, \mathcal{Q}_2) \: . \end{align*}

Proof ▶

Lemma 3.14

✓

\begin{align*} \operatorname{eC}_\alpha (\mathcal{P}_1 \otimes \mathcal{P}_2, \mathcal{Q}_1 \otimes \mathcal{Q}_2) & \le \operatorname{eC}_\alpha (\mathcal{P}_1, \mathcal{Q}_1) + \operatorname{eC}_\alpha (\mathcal{P}_2, \mathcal{Q}_2) \: . \end{align*}

Proof ▶

Lemma 3.15

✓

Let \(\mathcal{P},\mathcal{Q} \subseteq \mathcal{P}(\mathcal{X})\) be two sets of probability measures. Suppose that there exists a measurable map \(\phi : \mathcal{X} \to \mathcal{X}\) such that \(\phi \circ \phi = \operatorname{id}\) and \(\phi _* \mathcal{P} = \mathcal{Q}\). Then

\begin{align*} \operatorname{eR}_{1/2}(\mathcal{P}, \mathcal{Q}) & = 2 \inf _{R \in \mathcal{P}(\mathcal{X}), \: \phi _* R = R} \mathcal{U}_{\log }(R, \mathcal{P}) \: . \end{align*}

Proof ▶

First consider an arbitrary \(R \in \mathcal{P}(\mathcal{X})\). Then \(R' = \frac{1}{2}(R + \phi _* R)\) satisfies \(\phi _* R' = R'\) and by convexity (Lemma 2.20) and Lemma 2.27,

\begin{align*} \frac{1}{2} \mathcal{U}_{\log }(R’, \mathcal{P}) + \frac{1}{2} \mathcal{U}_{\log }(R’, \mathcal{Q}) & \le \frac{1}{2} \left( \frac{1}{2} \mathcal{U}_{\log }(R, \mathcal{P}) + \frac{1}{2} \mathcal{U}_{\log }(R, \mathcal{Q}) \right) \\ & \quad + \frac{1}{2} \left( \frac{1}{2} \mathcal{U}_{\log }(\phi _* R, \mathcal{P}) + \frac{1}{2} \mathcal{U}_{\log }(\phi _* R, \mathcal{Q}) \right) \\ & = \frac{1}{2} \mathcal{U}_{\log }(R, \mathcal{P}) + \frac{1}{2} \mathcal{U}_{\log }(R, \mathcal{Q}) \: . \end{align*}

Hence we can restrict the infimum defining \(\operatorname{eR}_{1/2}(\mathcal{P}, \mathcal{Q})\) to measures \(R\) such that \(\phi _* R = R\). For such measures, by Lemma 2.27, \(\mathcal{U}_{\log }(R, \mathcal{Q}) = \mathcal{U}_{\log }(\phi _* R, \mathcal{P}) = \mathcal{U}_{\log }(R, \mathcal{P})\) and we get the result.

Lemma 3.16

✓

\begin{align*} \operatorname{eC}(\mathcal{P}, \mathcal{Q}) & = \inf _{R \in \mathcal{P}(\mathcal{X}), \: \phi _* R = R} \mathcal{U}_{\log }(R, \mathcal{P}) \: . \end{align*}

Proof ▶

Similar to the proof of Lemma 3.15.

Lemma 3.17

✓

\begin{align*} \operatorname{eR}_{1/2}(\mathcal{P}, \mathcal{Q}) & = 2 \operatorname{eC}(\mathcal{P}, \mathcal{Q}) \: . \end{align*}

Proof ▶

Use Lemmas 3.15 and 3.16.