Gelfand–Yaglom–Perez Theorem for product space

Question

In On a Gel'fand-Yaglom-Peres theorem for f-divergences, Gilardoni proved the Gelfand–Yaglom–Perez Theorem for general $f$-divergence, i.e. $f$-divergence between two probability measures $P$ and $Q$ equals the supremum of the same $f$-divergence computed over all finite measurable partitions of the original space.

To be precise, let $P$, $Q$ be two probability measures on $\mathbf{X}$ with a $\sigma$-algebra $\mathbf{F}$. Given a $\mathbf{F}$-measureable partitions $E = \{E_1,E_2,\dotsc, E_n\}$, define the distribution $P_E$ on $[n]= \{1,2,\dotsc, n\}$ by $P_E(i) = P(E_i)$ and $Q_E(i) = Q(E_i)$. Then we have $$D_f(P|| Q) = \sup_{E} D_f(P_E||Q_E),$$ where the supremum is over all finite $\mathbf{F}$-measurable partitions $E$ and $D_f$ is $f$-divergence.

If we are working on a product space, say $\mathbf{X}^2$ with $\sigma$-algebra $\mathbf{F}\otimes \mathbf{F}$ and assume $P$, $Q$ are probability measures on $\mathbf{X}^2$, by directly using the above theorem, we know that $D_f(P||Q)$ could be approached by $D_f(P_E||Q_E)$ on finite partition $E$ on $\mathbf{X}^2$ (meaning that for any $\epsilon > 0$, we can find a partition $E$ such that $D_f(P_E||Q_E) > D_f(P||Q) - \epsilon$). But this partition may not be induced by partition on $\mathbf{X}$, i.e. there may not exist a partition $I = \{I_1,I_2,\dotsc,I_m\}$ on $\mathbf{X}$ such that $E = \{I_k\times I_l\}_{k,l=1}^m$. I am wondering that can we guarantee that $D_f(P||Q)$ could be approached by the "rectangular partition" I just mentioned?

Answer 1

I think yes.

Given any measurable partition $\mathcal{E} = \{E_1, \dots, E_n\}$ of $(\Omega_1 \times \Omega_2, \mathcal{F}_1 \otimes \mathcal{F}_2)$ with $D_f(P_\mathcal{E}||Q_\mathcal{E}) \geq D_f(P||Q) - \epsilon$.

We can for all $\delta > 0$ find another partition $\widetilde{\mathcal{E}} = \{\widetilde{E}_1, \dots, \widetilde{E}_n\}$ such that $\widetilde{E}_j = \dot{\bigcup}_{i = 1}^{m_j} A^{(j)}_i \times B^{(j)}_i$ with $A_i^{(j)} \in \mathcal{F}_1$, $B_i^{(j)} \in \mathcal{F}_2$ and $ (P+Q)(E_j \Delta \widetilde{E}_j) < \delta$ for all $1 \leq j \leq n$.

This is possible, because of the basic measure-theoretic fact that we for every $\delta > 0$ and $E \in \mathcal{F}_1 \times \mathcal{F}_2$ there is a $F = \dot{\bigcup}_{i = 1}^{m} A_i \times B_i$ such that $(P+Q)(E\Delta F) < \delta$. Begin constructing a measurable partition of rectangle unions by selecting a rectangle union $\widetilde{E}_1$ such that $(P+Q)(E_1 \Delta \widetilde{E}_1) < \delta$. Then select a rectangle union $E_2^*$ such that $P(E_2^* \Delta E_2) < \delta$. Set $\widetilde{E}_2 = E_2^* \setminus \widetilde{E}_1$ (which is again a rectangle union!) and observe that $(P+Q)(\widetilde{E}_2 \Delta E_2) < 2\delta$. Now just continue like this and at the end add $\widetilde{E}_n = \Omega \setminus (\widetilde{E}_1 \cup \dots \cup \widetilde{E}_{n-1})$ (which is also a rectangle union!).

But then for $\delta$ small enough $$ D_f(P_\mathcal{E}||Q_\mathcal{E}) = \sum_{j = 1}^{n} Q(E_j) \,f\Bigl(\frac{P(E_j)}{Q(E_j)}\Bigr) \leq \epsilon + \sum_{j = 1}^{n} Q(\widetilde{E}_j) \,f\Bigl(\frac{P(\widetilde{E}_j)}{Q(\widetilde{E}_j)}\Bigr)\\ \leq \epsilon + \sum_{j = 1}^{n} \sum_{i = 1}^{m_j} Q(A^{(j)}_i \times B^{(j)}_i) \,f\Bigl(\frac{P(A^{(j)}_i \times B^{(j)}_i)}{Q(A^{(j)}_i \times B^{(j)}_i)}\Bigr)\\ = \epsilon + D_f(P_\hat{\mathcal{E}}||Q_\hat{\mathcal{E}}) $$ where in the last inequality we used convexity of $f$ and denoted $\hat{\mathcal{E}} := \{A^{(j)}_i \times B^{(j)}_i \,\vert\, 1 \leq j \leq n, 1 \leq i \leq m_j \}$.

The partition $\hat{\mathcal{E}}$ on the RHS of course is still just a measurable partition of $\Omega_1 \times \Omega_2$ into rectangles, and in general not induced by a partition on $\Omega = \Omega_1 = \Omega_2$. But we can remedy this by refining the partition to $\mathcal{E}^* := \{I \times J \,\vert\, I, J \in \mathcal{I} \}$ with $\mathcal{I} = \{\bigcap_{j = 1}^{n} \bigcap_{i = 1}^{m_j} C^{(j)}_i \cap D^{(j)}_i \,\vert\, C^{(j)}_i \in \{A^{(j)}_i, (A^{(j)}_i)^c\}, D_i \in \{B^{(j)}_i, (B^{(j)}_i)^c\} \}$ a partition of $\Omega$. Then the same inequality as above, which used the convexity of $f$, shows $$D_f(P_\hat{\mathcal{E}}||Q_\hat{\mathcal{E}}) \leq D_f(P_{\mathcal{E}^*}||Q_{P_{\mathcal{E}^*}})$$.