<p><strong>Disclaimer.</strong> 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.</p>

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

<p><span class="math-container">$$
\alpha_\varepsilon := \min_{T \in \mathcal T_\varepsilon} TV(T_{\#}P_0, T_{\#}P_1).
$$</span></p>

<p>Note that by the <em>data-processing inequality</em>, it holds that
<span class="math-container">$$
0 \le \alpha_\varepsilon \le TV(P_0,P_1) \le 1.
$$</span>
Unfortunately, this bound is presumably very loose as it is independent of the parameter <span class="math-container">$\varepsilon$</span>.</p>

<h1>Question</h1>

<ul>
<li>Is there a nontrivial upper bound on <span class="math-container">$\alpha_\varepsilon$</span> in terms of <span class="math-container">$P_0$</span>, <span class="math-container">$P_1$</span> and <span class="math-container">$\varepsilon$</span> ? My wild guess (and hope!) is something of the form 
"<span class="math-container">$\alpha_\varepsilon \le g(\varepsilon)TV(P_0,P_1)$</span>",
where <span class="math-container">$g_\varepsilon:[0,1]\rightarrow [0, 1]$</span> is a nontrivial function such that <span class="math-container">$g_\varepsilon(t) &lt; t$</span> for <span class="math-container">$t \in (0, 1)$</span>.</li>
<li>Same question for the special case <span class="math-container">$X=(\mathbb R^p,\|\cdot-\cdot\|_\infty)$</span>. Note that in this case, <span class="math-container">$\alpha_\varepsilon$</span> can be written as
<span class="math-container">$$
\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)
$$</span></li>
<li>Same question for the Hamming cube <span class="math-container">$X = (\{0, 1\}^p, d_{\text{H}})$</span>. In this case, we can rewrite
<span class="math-container">$$
\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)
$$</span></li>
</ul>

CC BY-SA 4.0
2019-12-26T05:43:24.967Z
I've asked an extended / generalized version of the question here https://mathoverflow.net/q/349136/78539.
dohmatob
CC BY-SA 4.0
2019-12-26T13:36:07.420Z
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.
CC BY-SA 4.0
2019-12-26T13:42:05.897Z
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
CC BY-SA 4.0
2019-12-26T13:52:37.350Z
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.
CC BY-SA 4.0
2019-12-26T13:58:28.030Z
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
CC BY-SA 4.0
2019-12-26T15:08:47.580Z
As a maybe instructive way to start, do you have a nontrivial bound for $P_0$ the standard Gaussian (and $P_1$ an arbitrary Gaussian) in one dimension?
Clement C.
CC BY-SA 4.0
2019-12-26T15:25:51.173Z
Yes, if $P_k = \mathcal N(\mu_k,\sigma^2)$, then quick (and dirty) calculation should give $\alpha_\varepsilon = 2 \Phi(\sigma^{-1}\max(|\mu_0-\mu_1|-\varepsilon, 0))-1$ (exact formula !). Using Pinker's inequality, a similar argument would give good upper bounds for general exponential families.
dohmatob
<pr.probability><it.information-theory><st.statistics><upper-bounds>
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$
dohmatob
# 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$

(Asked by: username_0 on 2019-12-25)

**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)
  $$

**Tags:** pr.probability, it.information-theory, st.statistics, upper-bounds

> **Comments:**
> **username_0**: I've asked an extended / generalized version of the question here https://mathoverflow.net/q/349136/78539.  
> **username_1**: 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).  
> **username_0**: 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$.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: As a maybe instructive way to start, do you have a nontrivial bound for $P_0$ the standard Gaussian (and $P_1$ an arbitrary Gaussian) in one dimension?  
> **username_0**: Yes, if $P_k = \mathcal N(\mu_k,\sigma^2)$, then quick (and dirty) calculation should give $\alpha_\varepsilon = 2 \Phi(\sigma^{-1}\max(|\mu_0-\mu_1|-\varepsilon, 0))-1$ (exact formula !). Using Pinker's inequality, a similar argument would give good upper bounds for general exponential families.  

---

## 0 answers

