3 6 5 Data Processing Inequality And Generalized Fano Inequa

Our goal in this problem is to show that Fano inequality can be derived from the simple data processing inequality. The latter inequality gives a meaning to the intuitive statement "for any random variable $X$, the image measures $\mathbb{P}^X$ and $\mathbb{Q}^X$ are closer to each other than $\mathbb{P}$ and $\mathbb{Q}$ ". We start by proving the data processing inequality in a general form, before specializing it to the Kullback-Leibler divergence and deriving a generalized version of Fano inequality (3.2), page 57.

A) Data Processing Inequality

Let $f:[0,+\infty) \rightarrow \mathbb{R}$ be any convex function fulfilling $f(1)=0$. For two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ on a common measurable space $(\Omega, \mathscr{F})$, with $\mathbb{P} \ll \mathbb{Q}$, we define the $f$-divergence

(1)

\begin{align} D_f(\mathbb{P}, \mathbb{Q}) := \mathbb{E}_{\mathbb{Q}} \left[ f \left( \frac{d \mathbb{P}}{d \mathbb{Q}} \right) \right] = \int_{\Omega} f \left( \frac{d \mathbb{P}}{d \mathbb{Q}} \right) d \mathbb{Q}, \end{align}

where $\mathbb{E}_{\mathbb{Q}}$ denotes the expectation with respect to $\mathbb{Q}$.

1. Positivity: For any $\mathbb{P}$, we have:

(2)

\begin{aligned} D_f(\mathbb{P}, \mathbb{Q}) \geq_{\text{(Jensen)}} f \left( \mathbb{E}_\mathbb{Q} \left[ \frac{d \mathbb{P}}{d \mathbb{Q}} \right] \right) = f \left( \int_\Omega d \mathbb{P} \right) &= f(1) \geq 0 \end{aligned}

Convexity in the first variable: For any $\mathbb{P}_1, \mathbb{P}_2 \ll \mathbb{Q}$ and $\lambda \in$ $[0,1]$, we have:

(3)

\begin{aligned} D_f \left( \lambda \mathbb{P}_1 + (1 - \lambda) \mathbb{P}_2, \mathbb{Q} \right) &= \mathbb{E}_{\mathbb{Q}} \left[ f \left( \frac{d ( \lambda \mathbb{P}_1 + (1 - \lambda) \mathbb{P}_2 )}{d \mathbb{Q}} \right) \right] \\ &= \mathbb{E}_{\mathbb{Q}} \left[ f \left( \lambda \frac{d \mathbb{P}_1}{d \mathbb{Q}} + (1 - \lambda) \frac{d \mathbb{P}_2}{d \mathbb{Q}} \right) \right] \\ &\leq_{\text{(convexity of } f \text{)}} \mathbb{E}_{\mathbb{Q}} \left[ \lambda f \left( \frac{d \mathbb{P}_1}{d \mathbb{Q}} \right) + (1 - \lambda) f \left( \frac{d \mathbb{P}_2}{d \mathbb{Q}} \right) \right] \\ &\leq \lambda D_f\left(\mathbb{P}_1, \mathbb{Q}\right)+(1-\lambda) D_f\left(\mathbb{P}_2, \mathbb{Q}\right) \end{aligned}

The data processing inequality states that, for any probability distributions $\mathbb{P} \ll \mathbb{Q}$ on a common measurable space $(\Omega, \mathscr{F})$, and any random variable $X:(\Omega, \mathscr{F}) \rightarrow(E, \mathscr{A})$, we have

(4)

\begin{align} D_f\left(\mathbb{P}^X, \mathbb{Q}^X\right) \leq D_f(\mathbb{P}, \mathbb{Q}) \end{align}

where $\mathbb{P}^X$ (respectively $\mathbb{Q}^X$ ) is the distribution of $X$ under $\mathbb{P}$ (resp. $\mathbb{Q}$ ) defined by $\mathbb{P}^X(A)=\mathbb{P}(X \in A)$ for any $A \in \mathscr{A}$. The distribution $\mathbb{P}^X$ is also called the push-forward of $\mathbb{P}$ (resp. $\mathbb{Q})$ by $X$. The intuition behind (3.21), is that the distributions $\mathbb{P}$ and $\mathbb{Q}$ can only become closer after being processed by $X$.

A first step in order to prove (3.21) is to relate the Radon-Nikodym derivative $\frac{d \mathbb{P}^X}{d \mathbb{Q}^X}$ to the conditional expectation $\mathbb{E}_{\mathbb{Q}}\left[\frac{d \mathbb{P}}{d \mathbb{Q}} \mid X\right]$.

2. Let $g$ be any measurable function such that $\mathbb{Q}$-almost surely $g(X)=\mathbb{E}_{\mathbb{Q}}\left[\frac{d \mathbb{P}}{d \mathbb{Q}} \mid X\right]$. We have for any $A \in \mathscr{A}$:

(5)

\begin{aligned} \mathbb{P}^X(A) &=\int_\Omega \mathbf{1}_A (X(\omega)) d \mathbb{P} (\omega) \\ &=\int_\Omega \mathbf{1}_A (X(\omega)) \frac{d \mathbb{P}}{d \mathbb{Q}} (\omega) d \mathbb{Q} (\omega) \\ &= \mathbb{E}_\mathbb{Q} \left[ \mathbf{1}_A(X) \frac{d \mathbb{P}}{d \mathbb{Q}} \right] \\ &= \mathbb{E}_\mathbb{Q} \left[ \mathbb{E}_\mathbb{Q} \left[\mathbf{1}_A(X) \frac{d \mathbb{P}}{d \mathbb{Q}} | X \right] \right] \\ &= \mathbb{E}_{\mathbb{Q}}\left[\mathbf{1}_A(X) g(X)\right] \\ &=\int_\Omega \mathbf{1}_A (X(\omega)) g(X(\omega)) d \mathbb{Q} (\omega) \\ &=\int_E \mathbf{1}_A g \, d \mathbb{Q}^X \\ \mathbb{P}^X(A) &=\int_A g \, d \mathbb{Q}^X \end{aligned}

3. By the uniqueness in the Radon-Nikodym theorem, we conclude that $\mathbb{P}^X \ll \mathbb{Q}^X$ and that $\mathbb{Q}^X$-almost surely $\frac{d \mathbb{P}^X}{d \mathbb{Q}^X}=g$.

4. We conclude the proof of (3.21) by proving the sequence of inequalities:

(6)

\begin{aligned} D_f\left(\mathbb{P}^X, \mathbb{Q}^X\right) &= \int_E f \left( \frac{d \mathbb{P}^X}{d \mathbb{Q}^X} \right) d \mathbb{Q}^X \\ &= \int_E f(g(X)) \, d \mathbb{Q}^X \\ &= \mathbb{E}_\mathbb{Q} \left[ f \left( g(X) \right) \right] \\ &= \int_\Omega f \left(\mathbb{E}_{\mathbb{Q}}\left[\frac{d \mathbb{P}}{d \mathbb{Q}} \mid X\right]\right) d \mathbb{Q} \\ &\leq_{\text{(Jensen conditionally on } X \text{)}} \int_\Omega \mathbb{E}_{\mathbb{Q}}\left[f\left(\frac{d \mathbb{P}}{d \mathbb{Q}}\right) \mid X\right] d \mathbb{Q} \\ &= \mathbb{E}_\mathbb{Q} \left[ \mathbb{E}_{\mathbb{Q}}\left[f\left(\frac{d \mathbb{P}}{d \mathbb{Q}}\right) | X \right] \right] \\ &= \mathbb{E}_\mathbb{Q} \left[ f \left(\frac{d \mathbb{P}}{d \mathbb{Q}} \right) \right] \\ &= D_f(\mathbb{P}, \mathbb{Q}) \end{aligned}

B) Two Corollaries of the Data Processing Inequality

i) Joint Convexity

We have seen in the warm-up that the divergence $D_f$ is convex in the first variable. We will now prove that it is jointly convex in the two variables. More precisely, we will prove that for any distributions $\mathbb{P}_1 \ll \mathbb{Q}_1$ and $\mathbb{P}_2 \ll \mathbb{Q}_2$ on $(\Omega, \mathscr{F})$, and any $\lambda \in[0,1]$ we have

(7)

\begin{align} D_f\left(\lambda \mathbb{P}_1+(1-\lambda) \mathbb{P}_2, \lambda \mathbb{Q}_1+(1-\lambda) \mathbb{Q}_2\right) \leq \lambda D_f\left(\mathbb{P}_1, \mathbb{Q}_1\right)+(1-\lambda) D_f\left(\mathbb{P}_2, \mathbb{Q}_2\right) \end{align}

We will derive this inequality directly from the data processing inequality. Define the probabilities $\mathbb{P}$ and $\mathbb{Q}$ on $\{1,2\} \times \Omega$ by

(8)

\begin{align} \mathbb{P}(\{j\} \times B)=\left\{\begin{array}{cc} \lambda \mathbb{P}_1(B) & \text { if } j=1 \\ (1-\lambda) \mathbb{P}_2(B) & \text { if } j=2 \end{array}\right. \end{align}

and the same for $\mathbb{Q}$ with $\mathbb{P}_j(B)$ replaced by $\mathbb{Q}_j(B)$. Let us define the random variable $X:\{1,2\} \times \Omega \rightarrow \Omega$, by $X(j, \omega)=\omega$.

1. First, we check that $\mathbb{P}^X=\lambda \mathbb{P}_1+(1-\lambda) \mathbb{P}_2$ and $\mathbb{Q}^X=\lambda \mathbb{Q}_1+(1-\lambda) \mathbb{Q}_2$.

We simply note that for any $B \in \mathscr{F}$:

(9)

\begin{aligned} \mathbb{P}^X (B) &= \mathbb{P} (X \in B) \\ &= \mathbb{P} (\{1, 2\} \times B) \\ &= \mathbb{P} (\{1\} \times B) + \mathbb{P} (\{2\} \times B) \\ &= \lambda \mathbb{P}_1 (B) + (1 - \lambda) \mathbb{P}_2 (B) \end{aligned}

and the same goes for $\mathbb{Q}^X$ replacing $\mathbb{P}$ (resp. $\mathbb{P}_j$) by $\mathbb{Q}$ (resp. $\mathbb{Q}_j$).

2. If we denote

(10)

\begin{align} g : (j, \omega) \in \{1,2\} \times \Omega \mapsto \mathbf{1}_{j=1} \frac{d \mathbb{P}_1}{d \mathbb{Q}_1} (\omega) + \mathbf{1}_{j=2} \frac{d \mathbb{P}_2}{d \mathbb{Q}_2} (\omega) = \frac{d \mathbb{P}_j}{d \mathbb{Q}_j} (\omega) \end{align}

then for any $j \in \{1,2\}, B \in \mathscr{F}$:

(11)

\begin{aligned} \int_{\{j\} \times B} g \, d \mathbb{Q} &= \mathbf{1}_{j=1} \lambda \int_B g(1, \omega) d \mathbb{Q}_1 (\omega) + \mathbf{1}_{j=2} (1 - \lambda) \int_B g(2, \omega) d \mathbb{Q}_2 (\omega) \\ &= \mathbf{1}_{j=1} \lambda \int_B \frac{d \mathbb{P}_1}{d \mathbb{Q}_1} d \mathbb{Q}_1 + \mathbf{1}_{j=2} (1 - \lambda) \int_B \frac{d \mathbb{P}_2}{d \mathbb{Q}_2} d \mathbb{Q}_2 \\ &= \mathbf{1}_{j=1} \lambda \mathbb{P}_1 (B) + \mathbf{1}_{j=2} (1 - \lambda) \mathbb{P}_2 (B) \\ &= \mathbb{P} (\{j\} \times B) \end{aligned}

so by the uniqueness in the Radon-Nikodym theorem we have $\mathbb{P} \ll \mathbb{Q}$ and:

(12)

\begin{align} \frac{d \mathbb{P}}{d \mathbb{Q}}(j, \omega) = \mathbf{1}_{j=1} \frac{d \mathbb{P}_1}{d \mathbb{Q}_1} (\omega) + \mathbf{1}_{j=2} \frac{d \mathbb{P}_2}{d \mathbb{Q}_2} (\omega) \end{align}

We conclude the proof of (3.22) with the sequence of inequalities:

(13)

\begin{aligned} D_f \left( \lambda \mathbb{P}_1 + (1 - \lambda) \mathbb{P}_2, \lambda \mathbb{Q}_1 + (1 - \lambda) \mathbb{Q}_2 \right) &=_{\text{(B.1)}} D_f \left( \mathbb{P}^X, \mathbb{Q}^X \right) \\ &\leq_{\text{(3.21)}} D_f ( \mathbb{P}, \mathbb{Q} ) \\ &= \int_{\{1, 2\} \times \Omega} f \left( \frac{d \mathbb{P}}{d \mathbb{Q}} \right) d \mathbb{Q} \\ &= \lambda \int_\Omega f \left( \frac{d \mathbb{P}}{d \mathbb{Q}} (1, \omega) \right) d \mathbb{Q}_1 (\omega) + (1 - \lambda) \int_\Omega f \left( \frac{d \mathbb{P}}{d \mathbb{Q}} (2, \omega) \right) d \mathbb{Q}_2 (\omega) \\ &= \lambda \int_\Omega f \left( \frac{d \mathbb{P}_1}{d \mathbb{Q}_1} \right) d \mathbb{Q}_1 + (1 - \lambda) \int_\Omega f \left( \frac{d \mathbb{P}_2}{d \mathbb{Q}_2} \right) d \mathbb{Q}_2 \\ &= \lambda D_f \left( \mathbb{P}_1, \mathbb{Q}_1 \right) + (1 - \lambda) D_f \left( \mathbb{P}_2, \mathbb{Q}_2 \right) \end{aligned}

ii) Variant of the Data Processing Inequality

We next explain how the data processing inequality (3.21) can be used to upper bound the difference between two expectations $\mathbb{E}_{\mathbb{P}}[Z]$ and $\mathbb{E}_{\mathbb{Q}}[Z]$ in terms of $D_f(\mathbb{P}, \mathbb{Q})$.

More precisely, we will prove the following corollary of the data processing inequality (3.21). Let $\mathscr{B}(q)$ denote the Bernoulli distribution with parameter $q$. For any random variable $Z: \Omega \rightarrow[0,1]$ and any probability distributions $\mathbb{P} \ll \mathbb{Q}$ on $\Omega$, we have

(14)

\begin{align} D_f\left(\mathscr{B}\left(\mathbb{E}_{\mathbb{P}}[Z]\right), \mathscr{B}\left(\mathbb{E}_{\mathbb{Q}}[Z]\right)\right) \leq D_f(\mathbb{P}, \mathbb{Q}) \end{align}

1. Let $\ell$ be the Lebesgue measure on $[0,1]$ and let $A$ be any event on $\Omega \times[0,1]$.

Let us notice that the push-forward measure $(\mathbb{P} \otimes \ell)^{\mathbf{1}_A}$ (resp. $(\mathbb{Q} \otimes \ell)^{\mathbf{1}_A}$) is the Bernoulli distribution $\mathscr{B} (\mathbb{P} \otimes \ell(A))$ (resp. $\mathscr{B} (\mathbb{Q} \otimes \ell(A))$).

Moreover, we notice that for any $(\omega, x) \in \Omega \times [0,1]$:

(15)

\begin{align} \frac{d (\mathbb{P} \otimes \ell)}{d (\mathbb{Q} \otimes \ell)} (\omega, x) = \frac{d \mathbb{P}}{d \mathbb{Q}} (\omega) \end{align}

Then, applying the data processing inequality (3.21) with $X = \mathbf{1}_A$ we get:

(16)

\begin{aligned} D_f (\mathbb{P}, \mathbb{Q}) &= D_f(\mathbb{P} \otimes \ell, \mathbb{Q} \otimes \ell) \\ &\geq D_f (\mathscr{B} (\mathbb{P} \otimes \ell(A)), \mathscr{B} (\mathbb{Q} \otimes \ell(A))) \end{aligned}

2. Let us consider the event $A = \{ (\omega, x) \in \Omega \times [0,1]: x \leq Z(\omega) \}$. We have by Fubini's theorem:

(17)

\begin{aligned} \mathbb{P} \otimes \ell (A) &= \int_{\Omega \times [0,1]} \mathbf{1}_A (\omega, x) \, d (\mathbb{P} \otimes \ell) (\omega, x) \\ &= \int_\Omega \left( \int_{[0,1]} \mathbf{1}_{x \leq Z (\omega)} \, d \ell (x) \right) d \mathbb{P} (\omega) \\ &= \int_\Omega Z (\omega) \, d \mathbb{P} (\omega) \\ \mathbb{P} \otimes \ell (A) &= \mathbb{E}_{\mathbb{P}}[Z] \end{aligned}

and the same goes for $\mathbb{Q}$. Therefore, we can simply apply last question's inequality to this choice of event $A$ to conclude the proof of (3.23).

C) Generalized Fano Inequalities

We specialize the above results for $f(x)=x \log (x)$. For this choice of $f$, we have $D_f(\mathbb{P}, \mathbb{Q})=K L(\mathbb{P}, \mathbb{Q})$. For $p, q \in[0,1]$, we define

(18)

\begin{align} k l(p, q):=K L(\mathscr{B}(p), \mathscr{B}(q))=p \log \left(\frac{p}{q}\right)+(1-p) \log \left(\frac{1-p}{1-q}\right) \end{align}

1. First inequality: Let us prove that for $p \in [0,1]$:

(19)

\begin{align} \varphi (p) := p \log (p)+(1-p) \log (1-p) \geq-\log (2) \end{align}

First, we have $\varphi (p) = f(p) + f(1-p)$. Since $f' (p) = 1 + \log (p)$, $\varphi$ reaches its minimum at $p = \frac{1}{2}$ and we conclude by observing that $\varphi \left( \frac{1}{2} \right) = - \frac{1}{2} \log 2 - \frac{1}{2} \log 2 = - \log 2$.

Second inequality: Let us prove that:

(20)

\begin{align} kl (p, q) \geq p \log \left(\frac{1}{q}\right) - \log (2) \end{align}

We have:

(21)

\begin{align} kl (p, q) = \varphi (p) + p \log \left( \frac{1}{q} \right) + (1 - p) \log \left( \frac{1}{1 - q} \right) \end{align}

For $q < 1$, $(1 - p) \log \left( {1 - q} \right) \leq 0$, then we deduce the second inequality from the first.

2. Let $Z_1, \ldots, Z_N$ be $N$ random variables taking values in $[0,1]$ and let $\mathbb{P}_j \ll \mathbb{Q}_j$, for $j=1, \ldots, N$ be distributions on $\Omega$.

By the joint convexity (3.22) of $kl$ applied $N$ times:

(22)

\begin{align} kl \left(\frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{P}_i}\left[Z_i\right], \frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{Q}_i}\left[Z_i\right]\right) \leq \frac{1}{N} \sum_{i=1}^N kl (\mathbb{E}_{\mathbb{P}_i} [Z_i], \mathbb{E}_{\mathbb{Q}_i} [Z_i]) \end{align}

which is justified by the fact (proven by A.3 and B.ii) that for $1 \leq i \leq N$:

(23)

\begin{align} \mathscr{B} (\mathbb{E}_{\mathbb{P}_i} [Z_i]) \ll \mathscr{B} (\mathbb{E}_{\mathbb{Q}_i} [Z_i]) \end{align}

Then by the variant (3.23) of the data processing inequality, for each $1 \leq i \leq N$:

(24)

\begin{align} kl (\mathbb{E}_{\mathbb{P}_i} [Z_i], \mathbb{E}_{\mathbb{Q}_i} [Z_i]) \leq KL \left(\mathbb{P}_i, \mathbb{Q}_i\right) \end{align}

Putting these inequalities together:

(25)

\begin{align} kl \left(\frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{P}_i}\left[Z_i\right], \frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{Q}_i}\left[Z_i\right]\right) \leq \frac{1}{N} \sum_{i=1}^N KL \left(\mathbb{P}_i, \mathbb{Q}_i\right) \end{align}

3. Combining the two previous questions:

(26)

\begin{aligned} &- \left( \frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{P}_i}\left[Z_i\right] \right) \log \left(\frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{Q}_i}\left[Z_i\right]\right) - \log 2 \\ \leq \,& kl \left(\frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{P}_i}\left[Z_i\right], \frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{Q}_i}\left[Z_i\right]\right) \\ \leq \,& \frac{1}{N} \sum_{i=1}^N K L\left(\mathbb{P}_i, \mathbb{Q}_i\right) \end{aligned}

from which we deduce the generalized Fano inequality:

(27)

\begin{align} \frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{P}_i}\left[Z_i\right] \leq \frac{\frac{1}{N} \sum_{i=1}^N K L\left(\mathbb{P}_i, \mathbb{Q}_i\right)+\log (2)}{-\log \left(\frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{Q}_i}\left[Z_i\right]\right)} \end{align}

4. In the special case where $\mathbb{Q}_i = \mathbb{Q}$ for $i=1, \ldots, N$ and $Z_1+\ldots+Z_N \leq 1, \mathbb{Q}$-almost surely, we get that:

(28)

\begin{align} \log \left(\frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{Q}_i}\left[Z_i\right]\right) = \log \left( \frac{1}{N} \mathbb{E}_\mathbb{Q} \left[ \sum_{i=1}^{N} Z_i \right] \right) \leq - \log N \end{align}

from which we prove Inequality (3.24):

(29)

\begin{align} \frac{1}{N} \sum_{i=1}^N \mathbb{E}_{\mathbb{P}_i}\left[Z_i\right] \leq \frac{\frac{1}{N} \sum_{i=1}^N K L\left(\mathbb{P}_i, \mathbb{Q}\right)+\log (2)}{\log N} \end{align}

The Fano inequality can be recovered from (3.24) as follows. Let $A_1, \ldots, A_N$ be $N$ disjoint events in $\Omega$ and let $\mathbb{P}_1, \ldots, \mathbb{P}_N \ll \mathbb{Q}$ be $N+1$ probability distributions on $\Omega$. Then, taking $Z_i=\mathbf{1}_{A_i}$ the Inequality (3.24) gives

(30)

\begin{align} \frac{1}{N} \sum_{i=1}^N \mathbb{P}_i\left(A_i\right) \leq \frac{\frac{1}{N} \sum_{i=1}^N K L\left(\mathbb{P}_i, \mathbb{Q}\right)+\log (2)}{\log N} \end{align}