Minimising the f-divergence to a conditional probability constraint

Question

Let $P$ be a probability distribution and let $A$ and $B$ be some events, and suppose that we want to minimise an $f$-divergence between $P$ and the set of all distributions $Q$ that satisfy that constraint that $Q(B|A) = q$ for some fixed $q \geq P(B|A)$. Let $P_{f}$ denote the result of minimising a given $f$-divergence with this constraint. Is it always true, for any $f$, that $P_{f}(A) \leq P(A)$? I know that this holds for several examples (Kullback Leibler divergence, Hellinger distance, Inverse Kullback Leibler divergence), but is it true in general?

Answer 1

After having some trouble understanding this question, I have come to interpret it as follows: Let $P$ be a probability measure on a measurable space $(S,\Sigma)$. Suppose that $A$ and $B$ are in $\Sigma$, and $P(A)>0$. Fix any $q\in[P(B|A),1]$. Let $f\colon[0,\infty]\to(-\infty,\infty]$ be a function that is convex and continuous on $[0,\infty]$ and finite on $(0,\infty)$. Let $Q_f$ be a minimizer of the $f$-divergence $$D_f:=D_f(P||Q):=\int_S f\Big(\frac{dP}{dQ}\Big)\,dQ$$ over the set of all probability measures $Q$ on $(S,\Sigma)$ such that $Q(B|A)=q$. Is it then necessarily true that $Q_f(A)\le P(A)$?

The answer to this question is no. Indeed, let $S=\{1,2,3\}$, $A=\{1,2\}$, $B=\{2,3\}$, $P(\{i\})=p_i$ where $(p_1,p_2,p_3)=(1,1,2)/4$, $q=4/5$, and $f(x)=(4-3x)_++(1-2x)_+$, where $u_+:=\max(0,u)$.

Introducing now $k_i:=Q(\{i\})/P(\{i\})$, rewrite the conditions that $Q(B|A)=q$ and that $Q$ is a probability measure as $\frac{k_2}{k_1+k_2}=\frac45$ and $\frac14\,(k_1+k_2)+\frac12\,k_3=1$, which can be further rewritten as $k_1=\frac45\,(1-k_3/2)$ and $k_2=\frac{16}5\,(1-k_3/2)$, with the restriction $0\le k_3\le2$ to ensure that $k_1,k_2,k_3$ are all nonnegative. So, we can write \begin{equation} D_f(P||Q)=F(k_3):=\sum_1^3 f(1/k_i)k_i p_i = \begin{cases} \frac{2}{5} (7-6 k_3) & \text{if } k_3\le\tfrac18, \\ \frac{11}{4}-2 k_3 & \text{if } \frac{1}{8}\leq k_3\leq \frac{3}{4} \\ \frac{1}{20} (8 k_3+19) & \text{if } \frac{3}{4}\le k_3\le\frac{49}{32}, \\ 2 k_3-\frac{3}{2} & \text{if } \frac{49}{32}\le k_3. \end{cases} \end{equation} Thus, the minimization of $D_f(P||Q)$ in $Q$ such that $Q(B|A)=q$ here reduces to the minimization of the (convex) function $F$ on the interval $[0,2]$. It is obvious that the unique minimizer here is $k_3=\frac34$, which then leads to $k_1=\frac12$, $k_2=2$, and $Q_f(A)=k_1p_1+k_2p_2=\frac18+\frac12>\frac12=P(A)$. So, the inequality $Q_f(A)\le P(A)$ fails to hold.

---

Remark. It may be of interest how the above counterexample was obtained; that was based on a few not so straightforward observations. The difficulty here is that the convex function $f$ and the measures $P$ and $Q$ are, in general, infinite-dimensional objects. We minimize $D_f(P||Q)$ in $Q$ subject to the restriction $Q(B|A)=q$, which can be rewritten as $Q(A\cap B)=qQ(A)$. Note that this restriction is (i) linear in $Q$ and (ii) depends on $Q$ only through its restriction to the small sigma algebra $\Sigma_0$ generated by the partition $(A\setminus B,A\cap B,S\setminus A)$ of $S$.

On the other hand, $D_f(P||Q)=\int_S g(K)\,dP$, where $K:=\frac{dQ}{dP}$ and \begin{equation*} g(k):=k\,f(\tfrac1k),\quad\text{with }g(0):=g(0+),\ g(\infty):=g(\infty-). \tag{1} \end{equation*} The latter formula defines a map of the set of all functions $f\colon[0,\infty]\to(-\infty,\infty]$ that are convex and continuous on $[0,\infty]$ and finite on $(0,\infty)$ onto the same set (in fact, this map is an involution and hence bijective). So, by Jensen's inequality, \begin{equation*} D_f(P||Q)=E_P g(K)=E_P\,E_P(g(K)|\Sigma_0)\ge E_P g(K_0),\quad\text{where } K_0:=E_P(K|\Sigma_0) \end{equation*} and $E_P$ denotes the expectation with respect to the measure $P$. So, without loss of generality (wlog) $K$ is $\Sigma_0$-measurable and hence takes constant values, say $k_1,k_2,k_3$, on the sets $A\setminus B,A\cap B,S\setminus A$. That is, wlog $S=\{1,2,3\}$, as in the above counterexample. Thus, the measures $P$ and $Q$ are no longer infinite-dimensional objects; they are now completely represented by their values on the sets $A\setminus B,A\cap B,S\setminus A$: say $p_1,p_2,p_3$ for $P$ and hence $k_1p_1,k_2p_2,k_3p_3$ for $Q$. Accordingly, now we can write \begin{equation*} D_f(P||Q)=\sum_1^3 g(k_i)p_i. \end{equation*} We need to minimize this in $k_1,k_2,k_3\ge0$ subject to the linear restrictions $k_1p_1+k_2p_2+k_3p_3=1$ and $k_2p_2=q(k_1p_1+k_2p_2)$, the latter restriction representing $Q(A\cap B)=qQ(A)$. The condition $q \geq P(B|A)$ can now be rewritten as $vp_2=q(p_1+p_2)$ for some $v\ge1$. Writing the Lagrange multipliers system, we see that the dependence on the convex function $g$, an infinite-dimensional object, is reduced to the dependence on just the three numbers $h_i:=g'(k_i)$, such that the function $k_i\mapsto h_i$ is nondecreasing, that is, $(h_i-h_j)(k_i-k_j)\ge0$ for all $i,j$ in $\{1,2,3\}$.

The inequality $Q_f(A)\le P(A)$ in question in the (now justified) reduced setting can be rewritten as $k_1p_1+k_2p_2\le p_1+p_2$. Thus, it remains to check whether the latter inequality is implied by the system of algebraic equations and inequalities described above, involving the 10 real variables $p_1,p_2,p_3,k_1,k_2,k_3,v,h_1,h_2,h_3$. With the help of a computer algebra package, we find the above counterexample showing that the implication in question fails to hold in general. (Given the numbers $h_i$ such that $(h_i-h_j)(k_i-k_j)\ge0$ for all $i,j$, we can find any number of convex functions $g$ such that $h_i=g'(k_i)$ for $i=1,2,3$; I took one of such functions $g$ and then obtained $f$ from $g$ using the involution formula (1).)