4
$\begingroup$

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) $$
Improve this question
$\endgroup$
7
  • $\begingroup$ I've asked an extended / generalized version of the question here mathoverflow.net/q/349136/78539. $\endgroup$
    – dohmatob
    Dec 26, 2019 at 5:43
  • $\begingroup$ 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). $\endgroup$
    – Clement C.
    Dec 26, 2019 at 13:36
  • $\begingroup$ 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$. $\endgroup$
    – dohmatob
    Dec 26, 2019 at 13:42
  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    Dec 26, 2019 at 13:52
  • $\begingroup$ 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. $\endgroup$
    – dohmatob
    Dec 26, 2019 at 13:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.