# Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$

Disclaimer. I've moved this question from MO hoping that here is the right venue. Also, this is my first post on this channel, so please have some patience.

So, Iet $$X = (X,d)$$ be a Polish space, equipped with the Borel sigma-algebra and $$P_0,P_1$$ be probability distributions on $$X$$. Let $$\mathcal M(X,X)$$ be the measurable maps $$X\rightarrow X$$, and for each $$T \in \mathcal M(X,X)$$, let the measure $$T_{\#}P_k$$ be the push-forward of $$P_k$$ by $$T$$. For $$\varepsilon \ge 0$$, let $$\mathcal T_\varepsilon$$ be the set of all $$T \in \mathcal M(X,X)$$ such that $$\sup_{x \in X}d(T(x),x) \le \varepsilon$$. Define $$\alpha_\varepsilon$$ via the optimization problem

$$\alpha_\varepsilon := \min_{T \in \mathcal T_\varepsilon} TV(T_{\#}P_0, T_{\#}P_1).$$

Note that by the data-processing inequality, it holds that $$0 \le \alpha_\varepsilon \le TV(P_0,P_1) \le 1.$$ Unfortunately, this bound is presumably very loose as it is independent of the parameter $$\varepsilon$$.

# Question

• Is there a nontrivial upper bound on $$\alpha_\varepsilon$$ in terms of $$P_0$$, $$P_1$$ and $$\varepsilon$$ ? My wild guess (and hope!) is something of the form "$$\alpha_\varepsilon \le g(\varepsilon)TV(P_0,P_1)$$", where $$g_\varepsilon:[0,1]\rightarrow [0, 1]$$ is a nontrivial function such that $$g_\varepsilon(t) < t$$ for $$t \in (0, 1)$$.
• Same question for the special case $$X=(\mathbb R^p,\|\cdot-\cdot\|_\infty)$$. Note that in this case, $$\alpha_\varepsilon$$ can be written as $$\alpha_\varepsilon := \inf_{T_1,\ldots,T_p \in \mathcal M(\mathbb R^p,\mathbb R) \text{ s.t } x_j - \varepsilon \le T_j(x) \le x_j + \varepsilon\;\forall j \in [\![p]\!]} TV(T_{\#}P_0,T_{\#}P_1)$$
• Same question for the Hamming cube $$X = (\{0, 1\}^p, d_{\text{H}})$$. In this case, we can rewrite $$\alpha_\varepsilon = \inf_{T:\{0, 1\}^p \rightarrow \{0, 1\} \text{ s.t } \sum_{j \mid T(x)_j \ne j} 1 \le \varepsilon,\;\forall x \in \{0, 1\}^p} TV(T_{\#}P_0,T_{\#}P_1)$$
• I've asked an extended / generalized version of the question here mathoverflow.net/q/349136/78539. – dohmatob Dec 26 '19 at 5:43
• Maybe I'm misunderstanding something, but what about $P_0$ and $P_1$ being on disjoint subsets (say, even elements) at distance $\gg \varepsilon$? The TV is one, and for any admissible $T$, the distance between $TP_0$ and $TP_1$ is still one (supports still disjoint). – Clement C. Dec 26 '19 at 13:36
• As you rightly point-out, in case $P_0$ and $P_1$ have disjoint supports separated by a distance $r > 0$, then if $r < \varepsilon$, we have $T(T_{\#}P_0,T_{\#}P_1) = 1$ for all admissible $T$ indeed. This is not an issue, as even in this case, it's interesting to understand what happens when $r \le \varepsilon$. To avoid such issues (?), you may restrict to scenarios where $P_0 \ll P_1 \ll P_0$. – dohmatob Dec 26 '19 at 13:42
• I see. You may still have similar issues when $P_0\ll P_1\ll P_0$, though (so I don't think this assumption makes much difference): e.g., take two distributions supported on the integers, $\mathbb{N}$. For $\varepsilon < 1/2$, any admissible $T$ will preserve the total variation distance. – Clement C. Dec 26 '19 at 13:52
• Sure, those are some nice pathological cases I didn't think of. Under the hood, I'm only interested in nice cases (e.g when $P_0$ and $P_1$ have density w.r.t to some well-behaved reference measure, e.g Lebesgue, when the space allows). For example, as stated in the question results on the space $(X,\|\cdot-\cdot\|_p)$ for $p \in [1,\infty]$ will already be nice to have. – dohmatob Dec 26 '19 at 13:58